반응형
기본적으로 Merge sort, hearpsort 및 quick같은 NlogN 정렬 알고리즘은 입력 값들에 대한 비교(Comparison)에 기반한 방법이다. 이런 Comparison기반의 소팅들은 기본적으로 최악의 경우 NlogN보다 빠를수 없다는게 증명이 되어 있다.
특정 조건이 주어진다면 수행시간은 Linear Time(O(N))으로 줄일수 있다.
대표적인게 Radix sorting이다.
Radix Sortting
예를 들어 10진수 기수 10(18,45,37,97,34,65,98,10,72,99)개에 대해서 정렬한다고 하면
먼져 1의 자리에 대해서 각 해당 bucket에 넣고 다시 해당 Bucker에서 뽑아서 자료를 만든다
그러면 10,72,34,45,65,37,97,18,98,99가 나오고 다시 이 수를 그 다음 자리에 대해서 각 Bucker에 집어 넣으면 정렬된 값이 나온다.
일반적으로 메모리를 많이 소비한다.
참고..
다음은 Comparison기반의 정렬의 평균적인 수행 시간이다.
다음은 Comparision기반이 아닌 정렬의 평균적 수행 시간이다
반응형
