1. 삽입 정렬(Insertion Sort)

• 가장 간단한 정렬
• 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬
• 평균과 최악 모두 수행 시간 복잡도는 $O(n^2)$

  

2. 선택 정렬(Selete Sort)

• 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬 하는 방식
• 평균과 최악 모두 수행 시간 복잡도는 $O(n^2)$

  

3. 버블 정렬(Bubble Sort)

• 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 거호 교환하는 정렬 방식
• 평균과 최악 모두 수행 시간 복잡도는 $O(n^2)$

  

4. 쉘 정렬(Shell Sort)

• 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식
• 삽입 정렬의 확장 개념
• 평균 수행 복잡도는 $O(n^{1.5})$
• 최악 수행 시간 복잡도는 $O(n^2)$

5.퀵 정렬(Quick Sort)

• 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해 시키는 과정을 반복하는 정렬 방식
• 레코드의 많은 자료 이동을 없애고 하난의 파일을 부분적으로 나누어 가면서 정렬
• 평균 수행 시간 복잡도는 $O(nlog_2n)$
• 최악 수행 시간 복잡도는 $O(n^2)$

6. 힙 정렬(Heap Sort)

• 전 이진 트리를 이용한 정렬 방식
• 전이진 트리를 힙 트리로 변환하여 정렬
• 평균, 최악 모두 시간 복잡도는 $O(nlog_2n)$

7. 2-Way 합병 정렬(Merge Sort)

• 이미 정렬되어 있는 두개의 파일을 한 개의 파일로 합병하는 정렬 방식
• 평균과 최악 모두 시간 복잡도는 $O(nlog_2n)$

8. 기수 정렬(Radix Sort)

• Quene를 이용하여 자릿수 별로 정렬하는 방식
• 레코드의 키 값을 분석하여 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
• Bucket Sort라고도 함
• 평균과 최악 모두 시간 복잡도는 $O(dn)$

연습 문제

1. 다음 자료를 선택정렬을 이용하여 오름차순으로 정렬한다고 했을때 3회전 후의 결과는?

37, 14, 17, 40, 35

정답
14, 17, 35, 40, 37

2. 다음 자료를 버블 정렬을 이용해서 오름차순으로 정리할때 3회전 후의 결과는?

9, 6, 7, 3, 5

정답
3, 5, 6, 7, 9