[DB-28] 자료구조 - 정렬

1. 내부 정렬 기법

• 데이터량이 적을 때 주기억장치 내에서 정렬하는 방법
• 속도는 빠르나, 정렬할 자료의 양이 많은 경우 부적합

2. 내부 정렬 기법 종류

• 히프 정렬(heap sort)
• 기수 정렬(radix sort)
• 선택 정렬(selection sort)
• 버블 정렬(bubble sort)
• 퀵 정렬(quick sort)
• 삽입 정렬(insertion sort)
• 쉘 정렬(shell sort)

3. 외부 정렬 기법

• 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에, 테이프나 디스크 내에서 각 서브 파일을 합병하는 방법
• 속도는 느리지만 정렬하고자 하는 자료의 양이 많을 경우 효과적(보조기억장치 많이 사용)

4. 외부 정렬 기법 종류

• 진동 병합 정렬(oscillating merge sort)
• 밸런스 병합 정렬(balanced merge sort)
• 캐스케이드 병합 정렬(cascade merge sort)
• 폴리파즈 병합 정렬(polyphase merge sort)

5. 정렬 기법의 종류 

- 버블 정렬(bubble sort)

• 인접한 두 키를 비교한 결과로 정렬하는 방법

- 삽입 정렬(insertion sort)

• 새로운 하나의 레코드를 추가하여 순서에 맞게 배치

- 선택 정렬(selection sort)

• 최솟값을 찾아 첫 번째 위치에 놓고 다음 최소값을 찾아 두 번째 위치에 놓는 방법

- 히프 정렬(heap sort)

• 전이진 트리(complete tree)를 이용한 정렬 방식
• 연산 시간이 최악과 평균의 경우, 모두 0(nlogn)으로 빠른 속도를 가짐

- 퀵 정렬(quick sort)

• 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽에 모이도록 서로 교환시키는 부분 교환 정렬

- 기수 정렬(radix sort)

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

- 2-way 합병 정렬

• 주어진 입력 파일을 크기가 2인 서브 파일로 나누어서 각 서브 파일을 정렬

6. 정렬 알고리즘의 선택 시 고려사항

• 키 값들의 분포 상태
• 소요 공간 및 작업시간
• 정렬에 필요한 기억공간의 크기
• 데이터의 양
• 초기 데이터의 배열상태
• 사용 컴퓨터 시스템의 특성