2-1 030 정렬(Sort) [A]

삽입 정렬(Insertion Sort)

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

• n번째 키를 앞의 n-1개의 키와 비교하여 순서 맞추기
• 시간 복잡도: O(n²)

---

쉘 정렬(Shell Sort)

삽입정렬을 확장한 개념

1. 어떤 매개변수(h)의 값으로 서브파일 구성
2. 각 서브파일을 Insertion 정렬 방식으로 순서 배열
3. 반복하여 모든 서브파일 순서 배열

• 임의의 레코드 키와 h값 만큼 떨어진 곳의 키를 비교하여 배열하는 것을 반복함
• 부분적으로 정렬되어 있으면 유리함
• 평균 O(n^1.5), 최악 O(n²)

---

선택 정렬(Selection Sort)

n개의 레코드 중 최소값부터 찾아서 정렬하는 방식

• 평균과 최악 시간 복잡도 O(n²)

---

버블 정렬(Bubble Sort)

주어진 파일에서 인접한 두 개의 키 값을 비교하여 그 크기에 따라 위치를 서로 교환하는 정렬 방식

• 정렬 여부를 플래그로 계속 결정
• 평균 최악 시간 복잡도 O(n²)

---

퀵 정렬(Quick Sort)

레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법
키(피봇)를 기준으로 작은 값은 외쪽에, 큰 값은 오른쪽으로 분해시키는 방식

• 정렬 방식 중에서 가장 빠름
• 스택이 필요함
• 분할(Divide)과 정복(Conquer)을 통해 자료 정렬
• 평균 O(nlog₂n), 최악 시간 복잡도 O(n²)

---

힙 정렬(Heap Sort)

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

1. 값을 위→아래, 왼쪽→오른쪽으로 채움
2. 최하위→상위, 오른쪽→왼쪽 순으로 비교
3. 최상위 값을 출력 후 최하위 오른쪽 값을 최상위 값으로 삽입
4. 2,3 반복

• 평균 최악 시간 복잡도 O(nlog₂n)

---

2-Way 합병 정렬(Merge Sort)

이미 정렬된 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

1. 두 개의 값을 한 쌍으로 각 쌍에 대하여 순서 정함
2. 각 쌍의 값들을 합병하고 정렬
3. 위 합병을 반복

• 평균 최악 시간 복잡도 O(nlog₂n)

---

기수 정렬(Radix Sort) = Bucket Sort

Queue를 이용하여 자릿수(Digit)별로 정렬하는 방식

• 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 값을 꺼내서 정렬
• 평균 최악 시간 복잡도 O(dn)