-
정렬의 정의
-
내부 정렬(Internal sort)
- 데이터 양이 적어서 주기억 장치 내에서만 수행되는 정렬
- 정렬하기 전에 모든 데이터가 주기억 장치에 올라와 있어야 함
- 내부 정렬의 종류
| 종류 |
설명 |
힙 정렬
(Heap Sort) |
- 힙이란, 모든 단말 노드가 루트에서부터 거리가 h 또는 h-1 인 완정 이진 트리를 말함
- 정렬되지 않은 레코드로 구성된 파일을 트리 구조인 힙 형태로 변환하고, 가장 큰 레코드 키값을 가지는 루트 노드를 출력하고, 나머지 트리를 다시 힙으로 구성하는 과정을 반복 수행 하는 방법
|
선택 정렬
(Selection Sort) |
- 가장 작은(오름차순일 때) 값을 갖는 레코드를 맨 앞에 위치시키고, 맨 앞 레코드를 제외한 나머지 전체 레코드가 정렬될 때까지 다음 레코드들에 대하여 같은 과정을 반복 수행하는 방법
|
삽입 정렬
(Insertion Sort) |
- 다음 레코드를 왼쪽 것과 비교하여 작은 레코드를 왼쪽에 위치시키는 과정을 반복 수행하는 방법
- 레코드 양이 많고 레코드 크기가 클 경우에는 적합하지 않음
|
셀 정렬
(Shell Sort) |
- 삽입 정렬을 개선한 방법으로, 한 번에 한 칸씩 이동하는 대신 한 번에 여러 칸을 이동하는 방법
- 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬
|
버블 정렬
(Buble Sort) |
- 가장 큰 레코드가 한 칸씩 오른쪽 끝으로 오는 정렬 방법으로, 한 쌍씩 비교하는 방법
- 플래그를 이용하면 이미 정렬된 상태를 파악할 수 있어 정렬 시간을 줄일 수 있음
|
퀵 정렬
(Quick Sort) |
- 분할 및 정복법(Divide and Conquer)에 기반하여 전체 리스크를 2개의 부분 리스트로 분할하고, 각각의 부분 리스크를 다시 정렬하는 방법
- 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽으로 옮기고, 피벗보다 큰 요소들은 피벗의 오른쪽으로 옮김
- 평균적으로 매우 빠른 수행 속도를 보이는 정렬
|
-
외부 정렬(External Sort)
- 정렬하기 전에 모든 데이터가 한 번에 주기억 장치에 올라오지 못하는 경우, 보조 기억 장치에 대부분의 데이터가 있고 일부만 주기억 장치에 올려놓은 상태에서 수행되는 정렬
- 대량의 데이터를 몇 개의 서브파일(Run)로 나누어 내부 정렬을 한 후 보조 기억 장치에서 정렬된 각 서브파일들을 병합하는 방법 : 외부 정렬/병합(External Sort/Merge) 알고리즘
- 외부 정렬의 종류
| 종류 |
설명 |
균형 병합 정렬
(Balanced Merge sort) |
- 테이프에 저장되어 있는 데이터들을 주기억 장치에 옮겨올 수 있도록 작은 블록으로 나눔
- 나뉘어진 블록들은 각각 주기억 장치에서 정렬된 후에 다시 여러 개의 테이프에 분산되어 저장
- 나머지 과정이 순환적으로 반복되면서 블록의 수는 줄고 블록의 크기는 커지게 되며, 마지막으로 한 개의 블록만이 남게 되면 정렬이 완료
|
다단계 병합 정력
(Poly-phase Merge Sort) |
- 피보나치 수열에 의해 입력 서브파일들을 n개의 테이프 중 n-1개의 테이프에 분배 및 정렬하는 방법
|
계단식 병합 정렬
(Cascade Merge Sort) |
- 복사량을 줄이기 위한 불균형 방법의 다른 형태로, 연속 병합 정렬이라고도 함
- n개의 테이프가 주어졌을 때, 처음에는 (n-1)-원 병합을 수행하고, (n-2)-원 병합, …, 마지막으로 2-원 병합으로 반복적으로 수행하는 방법
|
진동 병합 정렬
(Oscillating Merge Sort) |
- 순방향 읽기와 역방향 읽기가 가능한 테이프 장치에서만 수행이 가능
- N개의 테이프가 주어졌을 때, 테이프 하나는 정렬되지 않은 입력 파일이 저장되어 있고, 비어 있는 n-1개의 테이프를 이용하여 병합 정렬하는 방법
|