n: 자료의 개수, d: 수의 자릿수
상태: 정렬된 수 가 다른 수가 정렬되는 과정에서 위치의 변동이 생기는지 여부
알고리즘 | 최선 | 평균 | 최악 | 상태 |
삽입 정렬 | O(n) | O(n^2) | O(n^2) | 안정 |
선택 정렬 | O(n^2) | O(n^2) | O(n^2) | 불안정 |
버블 정렬 | O(n^2) | O(n^2) | O(n^2) | 정렬 |
셸 정렬 | O(n) | O(n^1.5) | O(n^2) | 불안정 |
퀵 정렬 | O(nlogn) | O(nlogn) | O(n^2) | 불안정 |
히프 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | 불안정 |
합병 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | 불안정 |
기수 정렬 | O(dn) | O(dn) | O(dn) | 안정 |
카운팅 정렬 | O(n) | O(n) | O(n) | 안정 |
평균 O(n^2)의 정렬기법 중 삽입정렬이 제일 빠릅니다. 수가 정렬되어있을 시 최대 O(n)을 자랑합니다.
(셸 정렬은 삽입정렬의 변형된 기법으로, 필요한 경우 사용할 수 있도록 연습합니다.)
카운팅 정렬은 한자리 숫자(0~9)들을 정렬하는 등의 특수한 경우에만 사용 할 수 있는 정렬입니다.
기수 정렬에서 d는 기수의 자릿수로 자릿수가 작을 때는 O(n)으로 봐도 무방합니다.
자릿수가 고정되어 있는 수들을 정렬 할 때만 사용할 수 있습니다.
퀵정렬은 정렬기법 중 제일 빠르지만, 최악의 경우(모든 수가 정렬or역정렬되어있을 때)에는 O(n^2)입니다.
프로그래밍 문제를 풀다가 정렬기법을 써야 할 때 해결해야 할 자료의 범위가 큰 경우(1초당 약 1억번의 연산) 퀵정렬은 최선의 방법이 아닐 수 있습니다.