정렬
¹ 삽입 정렬 Insertion Sort
🖍️ 이미 순서화된 파일에 하나의 레코드를 순서에 맞게 삽입시켜 정렬
🖍️ n번째 키를 처음 ~ n-1번째 키와 비교
- 가장 간단한 정렬 방식
- 평균, 최악 시간복잡도: O(n²)
- swap이 아니라 비교 대상 앞에 삽입하는 것
² 쉘 정렬 Shell Sort
🖍️ 삽입 정렬을 확장한 개념
🖍️ 입력 파일을 어떤 매개변수(h)의 값으로 서브파일을 구성하고, 각 서브파일을 삽입 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 입력 파일이 부분적으로 정렬되어 있는 경우에 유리
- 평균 시간복잡도: O(n¹﹒⁵)
- 최악 시간복잡도: O(n²)
³ 선택 정렬 Selection Sort
🖍️ n개의 레코드 중에서 최소값을 찾아 첫번째 위치 부터 놓는 방식
- 평균, 최악 시간복잡도: O(n²)
⁴ 버블 정렬 Bubble Sort
🖍️ 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 위치를 서로 교환
1회전 후: 가장 큰 수가 마지막 위치에 있음
2회전 후: 두번째 큰 수가 n-1 위치에 있음
...
- 평균, 최악 시간복잡도: O(n²)
⁵ 퀵 정렬 Quick Sort
🖍️ 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 임의의 키를 분할 원소로 사용 가능
- 가장 빠른 정렬 방식
- 스택 필요
- 분할 정복을 통해 자료 정렬
- 분할: 피봇을 중심으로 자료를 2개의 부분집합으로 나눔
- 정복: 피봇을 중심으로 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 정렬
- 부분집합이 더이상 나누어질 수 없을 때까지 분할정복 반복 수행
- 평균 시간복잡도: O(nlogn)
- 최악 시간복잡도: O(n²)
⁶ 힙 정렬 Heap Sort
🖍️ 전 이진트리를 이용한 정렬 방식
- 평균, 최악 시간복잡도: O(nlogn)
⁷ 2-Way 합병 정렬 Merge Sort
🖍️ 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬
- 두 개의 키를 한 쌍으로 하여 각 쌍에 대해 순서를 정함
- 순서대로 정렬된 각 쌍의 키드를 합병하여 하나의 정렬된 서브리스트로 만듦
- 반복..
- 평균, 최악 시간복잡도: O(nlogn)
⁸ 기수정렬 Radix Sort(=Bucket Sort)
🖍️ 큐를 이용하여 자릿수(digit)별로 정렬하는 방식
🖍️ 키 값을 분석하여 같은 수나 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균, 최악 시간복잡도: O(dn)
왕왕