1. 선택정렬
키 값의 크기 순으로 리스트에서 제일 작은 원소를 찾아 첫번째 위치에 있는 원소와 교환하고 다음에는 두번째로 작은 원소를 찾아 두번째 위치에 있는 원소와 교환한다. 이런 방법으로 반복적으로 수행하는 방식
5 |
2 |
8 |
3 |
1 | min | 비교회수 |
1 |
2 |
8 |
3 |
5 | 5번방 | 4 |
1 |
2 |
8 |
3 |
5 | 2번방 | 3 |
1 |
2 |
3 |
8 |
5 | 4번방 | 2 |
1 |
2 |
3 |
5 |
8 | 5번방 | 1 |
기억공간 : s = n
수행시간 : O(n^2)
5 |
2 |
8 |
3 |
1 |
비교회수 |
1 |
5 |
8 |
3 |
2 |
4 |
1 |
2 |
8 |
5 |
3 |
3 |
1 |
2 |
3 |
8 |
5 |
2 |
1 |
2 |
3 |
5 |
8 |
1 |
2. 셸정렬
주어진 리스트를 적당한 매개변수 값만큼 서로 떨어진 레코드들과 비교하여 교환하는 과정을 매개변수 값을 바꾸어가며 반복한다.
매개변수 h = (1, 3, 5)
초기상태 h = 5
3. 퀵정렬
주어진 입력 리스트를 피봇(pivot)이라는 특정 키 값보다 작은 값을 가지는 레코드들의 리스트와 큰 값을 가지는 레코드들의 리스트로 분리한 다음, 이러한 두개의 서브 리스트들을 재귀적으로 각각 재배열하는 과정을 수행하는 방식
기억공간 : s = n + stack
수행시간 O(n^2), 평균 O(nlog2n)
특징
평균 연산 시간에 있어서 내부 정렬 방법 중 가장 우수
스택 공간을 사용
재귀 호출을 기반으로 동작
4. 히프정렬
입력된 레코드들로서 히프를 구성한 다음, 가장 큰 키값을 가지는 루트 노드를 삭제하는 과정을 계속해서 반복하는 방식
기억공간 s = n + pointer
수행시간 O(nlog2n)
특징
최소히프, 최대 히프
초기이진트리, 초기히프 상태