삽입 정렬 (Insertion Sort)
- 가장 간단한 정렬 방식
- 평균 수행 시간 복잡도 = 최악 수행 시간 복잡도 = O(n^2)
[수행 방법]
(1회전) 두 번째 값과 첫 번째 값을 비교해 순서대로 나열
(2회전) 세 번째 값을 첫 번째, 두 번째 값과 비교해 순서대로 나열
...
(n회전) n-1번째 값을 앞의 값들과 모두 비교하여 알맞은 순서에 삽입하여 정렬
[예제]
초기 상태 : 8 5 6 2 4
1회전 : 8 5 6 2 4 → 5 8 6 2 4
2회전 : 5 8 6 2 4 → 5 6 8 2 4
3회전 : 5 6 8 2 4 → 2 5 6 8 4
4회전 : 2 5 6 8 4 → 2 4 5 6 8
쉘 정렬 (Shell Sort)
- 삽입 정렬을 확장한 개념
- 입력파일을 어떤 매개변수(h)의 값으로 서브파일을 구성하고, 각 서브파일을 삽입 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 임의의 레코드 키와 h값만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복
- 입력 파일이 부분적으로 정렬되어 있는 경우에 유리한 방식
- 평균 수행 시간 복잡도 = O(n^1.5)
- 최악 수행 시간 복잡도 = O(n^2)
선택 정렬 (Selection Sort)
- n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하는 정렬 방식
- 평균 수행 시간 복잡도 = 최악 수행 시간 복잡도 = O(n^2)
[예제]
초기 상태 : 8 5 6 2 4
1회전 : 5 8 6 2 4 → 5 8 6 2 4 → 2 8 6 5 4 → 2 8 5 6 4
2회전 : 2 6 8 5 4 → 2 5 8 6 4 → 2 4 8 5 6
3회전 : 2 4 6 8 5 → 2 4 5 8 6
4회전 : 2 4 5 6 8
버블 정렬 (Bubble Sort)
- 주어진 파일에서 인접한 두 개의 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 계속 정렬 여부를 플래그 비트(f)로 결정
- 평균 수행 시간 복잡도 = 최악 수행 시간 복잡도 = O(n^2)
[예제]
초기 상태 : 8 5 6 2 4
1회전 : 5 8 6 2 4 → 5 6 8 2 4 → 5 6 2 8 4 → 5 6 2 4 8
2회전 : 5 6 2 4 8 → 5 2 6 4 8 → 5 2 4 6 8
3회전 : 2 5 4 6 8 → 2 4 5 6 8
4회전 : 2 4 5 6 8
퀵 정렬 (Quick Sort)
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법
- 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분해시키는 방식으로 정렬
- 위치에 관계없이 임의의 키를 분할 원소로 사용할 수 있음
- 정렬 방식 중에서 가장 빠른 방식
- 프로그램에서 되부름을 이용하기 때문에 스택이 필요
- 분할과 정복을 통해 자료를 정렬
- 분할 : 기준 값인 피봇을 중심으로 정렬할 자료들을 2개의 부분집합으로 나눈다
- 정복 : 부분집합의 원소들 중 피봇보다 작은 원소들은 왼쪽, 피봇보다 큰 원소들은 오른쪽 부분집합으로 정렬
- 부분집합의 크기가 더 이상 나누어질 수 없을 때까지 분할과 정복을 반복 수행
- 평균 수행 시간 복잡도 = O(nlog2의n)
- 최악의 수행 시간 복잡도 = O(n^2)
힙 정렬 (Heep Sort)
- 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리를 힙 트리로 변환하여 정렬
- 평균 수행 시간 복잡도 = 최악 수행 시간 복잡도 = O(nlog2의n)
[예제] 17, 14, 13, 15, 16, 19, 11, 18, 12를 힙 트리로 구성하시오.
(1) 주어진 파일의 레코드들을 전이진 트리로 구성한다.
(2) 전이진 트리의 노드의 역순으로 자식 노드와 부모 노드를 비교하여 큰 값을 위로 올린다
(3) 교환된 노드들을 다시 검토하여 위의 과정을 반복한다.
2-way 합병 정렬 (Merge Sort)
- 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균 수행 시간 복잡도 = 최악 수행 시간 복잡도 = O(nlog2의n)
[수행 방법]
- 두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정한다
- 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브리스트로 만든다
- 위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복한다
[예제] 71, 2, 38, 5, 7, 61, 11, 26, 53, 42를 2-way 합병 정렬로 정렬하시오
- 1회전 : 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다
(71, 2) (38, 5) (7, 61) (11, 26), (53, 42) → (2, 71) (5, 38) (7, 61) (11, 26) (42, 53)
- 2회전 : 묶여진 묶음을 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다
((2, 71) (5, 38)) ((7, 61) (11, 26)) (42, 53) → (2, 5, 38, 71) (7, 11, 26, 61) (42, 53)
- 3회전 : 묶여진 묶음을 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다
(2, 5, 38, 71) (7, 11, 26, 61) (42, 53) → (2, 5, 7, 11, 26, 38, 61, 71) (42, 53)
- 4회전 : 묶여진 묶음 두 개를 하나로 묶은 후 정렬한다
2, 5, 7, 11, 26, 38, 45, 53, 61, 71
기수 정렬 (Radix Sort, Bucket Sort)
- Queue를 이용하여 자릿수별로 정렬하는 방식
- 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균 수행 시간 복잡도 = 최악 수행 시간 복잡도 = O(dn)