2. 자료구조

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)

특징

최소히프, 최대 히프

초기이진트리, 초기히프 상태