정렬(Sorting)

• 정렬의 정의
  • 정렬은 주어진 레코드들을 특정한 순서대로 나열하는 것
  • 레코드의 정렬 순서에 따라 오름차순 또는 내림차순으로 구분
  • 정렬하려는 속성에 대해 인덱스가 구축된 경우, 해당 인덱스를 통해 정렬된 순서에 따라 접근 가능
       
• 내부 정렬(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개의 테이프를 이용하여 병합 정렬하는 방법