9. 정렬 알고리즘 정리

#정렬 알고리즘

	Best	Worst	Average	Stable	In-place
Selection Sort	O(n*n)	O(n*n)	O(n*n)	X	O
Bubble Sort	O(n*n)/ O(n)	O(n*n)	O(n*n)	O	O
Insertion Sort	O(n)	O(n*n)	O(n*n)	O	O
Quick Sort	O(n log n)	O(n*n)	O(n log n)	X	X
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O	X
Heap Sort	O(n log n)	O(n log n)	O(n log n)	X	O

Merge Sort의 경우 병합할 때 O(n)의 스텍 메모리가 필요하다. // O(log n)

Quick Sort의 경우 O(n)의 stack 메모리가 필요하다. 하지만 pivot에 의해 분할된 부분 중 작은 부분을 먼저 정렬한다면 O(log n)으로 메모리를 줄일 수 있다.

 

#정렬 알고리즘의 하한계

두 원소를 비교해서 정렬하는 알고리즘에서 최악의 경우가 O(n log n)보다 적게 나오는 경우는 없다.

why?

모든 원소를 비교해서 나타내는 정렬 알고리즘은 원소 비교 하나에 대해 노드를 만들어 판단 트리로 나타낼 수 있다. 이 경우 판단 트리의 leaf노드는 n!개이며 leaf노드에는 각각의 경우에 대한 결과값이 존재해야 한다. 판단 트리를 이용한 삽입 정렬의 최악의 경우 비교횟수는 판단트리의 높이이다. 

*m개의 leaf노드를 가지는 이진트리의 높이

 -제일 큰 경우: 한쪽으로 치우친 경우

 -제일 작은 경우: 완전이진트리

 즉, [log m]==[log n!] <= h

 log n! ≒ log(n/2)^(n/2) = (n/2) * log(n/2)

 => O((n/2) * log(n/2)) = O(n log n)

따라서 키 비교에 의한 정렬알고리즘에서는 Merge Sort, Heap Sort는 최악의 경우 최적의 알고리즘이라고 할 수 있다.

 

그렇다면 정렬을 할 때 꼭 원소를 비교해야 하는가? 그렇지 않다. 다음장부터 두 원소를 비교하지 않고 정렬하는 방법을 살펴볼 것이다.