Sorting algorithm 성능비교

그림출처 : http://dev-ahn.tistory.com/39

삽입정렬의 경우, 정렬대상이 완전히 정렬된 상태라면 안쪽 for문에서 걸리지기 때문에 시간복잡도는 O(n)이 된다.

병렬정렬의 경우, 임시메모리가 필요하다는 단점이 있다. 하지만 연결리스트를 정렬할 때는이런한 단점을 극복할 수 있다.

힙정렬의 경우도 힙저장공간이 필요하다는 단점이 있다.

퀵소트의 경우, 최악의 경우는 이미 데이터들이 정렬된 상태이고 pivot이 가장 작은 값으로 결정되는 경우이다. 이 경우 데이터가 둘로 나뉘는 횟수 k = n이고 되고
결과적으로 O(n^2)이 된다.
참고로, pivot값을 가운데에 두면 성능이 개선된다.

Radix(기수)정렬의 경우, 성능은 가장좋지만 적용할 수 있는 범위가 제한적이다.