정렬 기법 비교

정렬 기법 비교

• Stable : 동일한 값에 대해 순서가 뒤바뀌지 않고 정렬 (먼저 등장한 동일한 값이 정렬 후에도 먼저 등장)
• In-Place : 새로운 배열을 만들 필요 없이 입력 배열 내부에서 정렬
• Comparison : 배열 내 요소값들을 서로 비교하여 정렬
• Bucket 정렬의 경우, 각 Bucket에 대해 어떤 정렬 알고리즘을 사용하느냐에 따라 Comparison 유무가 달라질 수 있다.

 

Algorithm	Stable	In-Place	Comparison	최선 (Best)	평균 (Average)	최악 (Worst)
Bubble	O	O	O	$O(N^2)$	$O(N^2)$	$O(N^2)$
Selection	O	O	O	$O(N^2)$	$O(N^2)$	$O(N^2)$
Insertion	O	O	O	$O(N)$	$O(N^2)$	$O(N^2)$
Shell	O	O	O	$O(N)$	$O(N^2)$	$O(N^2)$
Merge	X	O	O	$O(NlogN)$	$O(NlogN)$	$O(NlogN)$
Heap	O	X	O	$O(NlogN)$	$O(NlogN)$	$O(NlogN)$
Quick	O	X	O	$O(NlogN)$	$O(NlogN)$	$O(N^2)$
Counting	X	O	X	$O(N)$	$O(N)$	$O(N)$
Radix	X	O	X	$O(N)$	$O(N)$	$O(N)$
Bucket	X	O	?	$O(N)$	$O(N)$	$O(N)$