정렬 알고리즘 비교

다음은 여러 가지 정렬 방법의 이론적 성능을 비교한 것이다.

최적 정렬 방법은 정렬해야 할 레코드의 수, 크기, 타입 등에 따라 달라지므로,

정렬 방법들의 장단점을 잘 이해하여 적합한 정렬 방법을 사용할 수 있어야 한다.

정수 60000개를 각 정렬 알고리즘으로 정렬할 때 소요되는 시간을 측정한 결과이다.

빨간 글씨로 색칠되어 있는 Insertion / Merge / Quick Sort는

Arrays.sort()에서 사용하는 정렬 알고리즘이므로 중요하다 생각되어 표시.

실제로는 Tim Sort(Insertion + Merge), Dual-Pivot Quick Sort(Quick Sort 변형) 2가지를 쓰지만 기본 베이스는 3가지이다.

알고리즘	Time Complexity			실행시간 (sec)	Space	Stable	Comments
	Best	Average	Worst
삽입 정렬 (Insertion Sort)				7.438	O(1)	O	최선 : 이미 정렬된 배열을 정렬할 때  최악 : 반대로 정렬된 배열을 또 다시 반대로 정렬할 때
선택 정렬 (Selection Sort)				10.842		X
버블 정렬 (Bubble Sort)				22.894		O
셸 정렬 (Shell Sort)				0.056		X
퀵 정렬 (Quick Sort)				0.014	O(1)		최선 : 데이터가 완전히 랜덤일 때 (상대적으로 최고의 성능)  최악 : 이미 정렬되어있거나 역순정렬된 배열을 정렬하면서 피벗을 양쪽 끝으로 설정할 때. (중간 값을 pivot으로 설정하면 Worst는 면할 수 있다.)
히프 정렬 (Heap Sort)				0.034
합병 정렬 (Merge Sort)				0.026	O(n)	O
기수 정렬 (Radix Sort)

 

Stable Sorting : MIB (Merge, Insertion, Bubble)

Not Stable Sorting : QSS (Quick, Selection, Shell)