정렬 알고리즘

* 선택 정렬

 - 입력 배열과 별도의 동일한 크기를 갖는 배열이 필요

기존 배열	정렬된 배열
{ 4, 2, 3, 1, 5 }	{ }
{ 4, 2, 3, 5}	{ 1 }
{ 4, 3, 5 }	{ 1, 2 }
{ 4, 5 }	{ 1, 2, 3 }
{ 5 }	{ 1, 2, 3, 4}
{ }	{ 1, 2, 3, 4, 5 }

- 추가 메모리를 활용하지 않는 제자리 정렬 ( in-place sorting )

4	5	3	1	2
1	5	3	4	2
1	2	3	4	5
1	2	3	4	5
1	2	3	4	5

와

는 SWAP.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 selectSort(A, n) {     for(i = 0, i < n-1; i++)     {         least = i           for(j = i+1; j < n; j++)         {             if(A[j] < A[least])                 least = j         }           if(A[i] > A[least])             swap(A[i], A[least], temp)     } } cs

 

- 문제점 : 값이 같은 레코드가 있는 경우에 상대적 위치가 변경될 수 있다. (안정성을 만족하지 않는다.)

- 개선 : 자신과 least 값이 동일한 경우 swap을 하지 않는다.

- 장점 : 자료이동의 횟수가 미리 결정

* 삽입 정렬

 

5	3	8	1	2	7
5	3	8	1	2	7
3	5	8	1	2	7
3	5	8	1	2	7
1	3	5	8	2	7
1	2	3	5	8	7
1	2	3	5	7	8

 

insertSort(A, n) { for(i = 1; i < n; i++) { key = A[i] for(j = i-1; j >= 0; j--) { if(A[j] > key) A[j+1] = A[j] else break } A[j+1] = key } }

 

 

 

- 문제점 : 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

- 역순으로 정렬 되어 있는 경우 최악의 효율

- 입력 자료가 이미 정렬되어 있을 경우 가장 빠름

- 장점 : 안정된 정렬 방법으로 레코드의 수가 적을 경우에 알고리즘 자체가 매우 간단하므로 다른 복잡한 알고리즘 보다 유리할 수 있다.

- 안정된 정렬 이유 : 같은 원소의 경우에 정렬이 되어도 순서가 유지

 

* 버블 정렬

 

2	5	3	1	4
2	5	3	1	4
2	3	5	1	4

2

3

1

5

4

2

3

1

4

5

2

3

1

4

5

2

1

3

4

5

2

1

3

4

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

 

- 오름차순 정렬을 기준으로 2개씩 비교하여 큰값을 오른쪽으로 이동

- 마지막 값까지 비교 완료되면 마지막 값의 위치를 제외하고 앞에서 부터 반복

 

boubleSort(A, n) { for(i = n-1; i > 0; i--) { for(j = 0; j < i; j++) { if(A[j] > A[j+1]) swap(A[j], A[j+1], temp) } } }

 

 

 

- 비교 횟수는 최상, 평균, 최악 모두 동일

- 역순 정렬일 경우 최악의 이동 횟수

 

 

* 퀵 정렬

 

5	3	8	4	9	1	6	2	7
pivot	low							high
5	3	8	4	9	1	6	2	7
pivot		low					high
5	3	2	4	9	1	6	8	7
pivot			low			high
5	3	2	4	9	1	6	8	7
pivot				low	high
5	3	2	4	1	9	6	8	7
pivot				high	low
low가 high보다 커지면 STOP, pivot과 high swap
1	3	2	4	5	9	6	8	7

 

- 1번 완료. 위와 같은 방법으로 pivot의 왼쪽과 오른쪽을 정렬한다.

 

5	3	8	4	9	1	6	2	7
pivot 1
1	3	2	4	5	9	6	8	7
pivot 2				pivot 1	pivot 3
1	3	2	4	5	7	6	8	9
pivoit 2	pivot 4			pivot 1	pivot 5			pivot 3
1	2	3	4	5	6	7	8	9
pivot 2		pivot 4		pivot 1		pivot 5		pivot 3

 

 

quickSort(list, left, right) { if(left < right) { q = partition(list, left, right) quickSort(list, left, q-1) quickSort(list, q+1, right) } } partition(list, left, right) { low = left high = right pivot = list[left] do{ do{ low++ }while( low <= right && list[low] < pivot) do{ high-- }while( high >= left && list[high] > pivot) }while(low < high) swap(list[left], list[high], temp) return high }

 

 

 

- best case

			n
	n/2				n/2
n/4		n/4		4/n		n/4
n/8	n/8	n/8	8/n	n/8	n/8	n/8	n/8
...

 

 

- worst case

 

n
1		n-1
		1		n-2
				1		n-3
						1		...

 

 

 

- 평균적으로 매우 빠른 속도를 자랑하는 정렬 방법

- 분할정복(divide conquer) 방법에 근거한다.

- 동일한 시간복잡도를 갖는 다른 정렬보다 빠르다.

* 불필요한 데이터 이동을 줄이고 먼거리의 데이터 교환

* 한번 결정된 피봇은 추후 연산에서 제외

- 단점 : 정렬된 리스트에 대해서는 수행시간이 더 많이 걸린다

- 장점 : 빠른 속도와 추가 메모리 공간이 필요 없다.

- 개선 : 피봇 선택에 있어 불균형을 막기 위하여 처음, 중간, 끝 3개의 값중 중간값을 사용한다.