[2과목 소프트웨어 개발] 데이터 입·출력 구현 - 038. ⭐ 정렬 (Sort)

1. 삽입 정렬 (Insertion Sort)

• 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬

[그림 1] 삽입 정렬

2. 쉘 정렬 (Shell Sort)

• Insertion Sort 확장
• 매개변수 값으로 서브파일을 구성 → 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬방식

3. 선택 정렬 (Selection Sort)

• n개 레코드 중 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복

[그림 2] 선택 정렬

4. 버블 정렬 (Bubble Sort)

• 인접한 두 개의 레코드 키 값을 비교해 그 크기에 따라 레코드 위치를 서로 교환하는 정렬방식
• 정렬 여부를 플래그 비트(f)로 결정

[그림 3] 버블 정렬

5. 퀵 정렬 (Quick Sort)

• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법
• 키를 기준으로 작은 값을 왼쪽, 큰 값을 오른쪽으로 분해시키는 방식으로 정렬
• 정렬 방식 중 가장 빠른 방식
• 위치에 관계없이 임의의 키를 분할 원소로 사용
• 프로그램에서 되부름을 이용하기 때문에 스택(Stack)이 필요
• 분할(Divide) : 기준값인 피봇(Pivot)을 중심으로 정렬한 자료들을 2개의 부분집합으로 나눔
• 정복(Conquer) : 부분집합의 원소들 중 피봇(Pivot)보다 작은 원소들은 왼쪽, 큰 원소들은 오른쪽 부분직합으로 정렬
• 부분집합의 크기가 더 이상 나누어질 수 없을 때까지 분할과 정복을 반복 수행

7. 힙 정렬 (Heap Sort)

• 전이진 트리(Complete Binary Tree)를 이용한 정렬방식

[그림 4] 힙 정렬

8. 2-Way 합병 정렬 (Merge Sort)

• 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

1) 두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정함
2) 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브리스트로 만듬
3) 위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복

[그림 5] 2-way 합병 정렬

9. 기수 정렬 (Radix Sort) = Bucket Sort

• Queue를 이용해 자릿수(Digit)별로 정렬하는 방식
• 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬

10. ⭐ 시간복잡도

[그림 6] BigO

 

 

 

📖 Reference

2023 시나공 정보처리기사 필기 : 네이버 도서

 

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog