Algorithm 6 - Comparison based sorting

 Comparison based sorting algorithm
input sequence의 ordered information을 element의 comparison으로 얻는 알고리즘. 따라서 time complexity는 comparison 횟수에 의해 결정된다.
이제껏 살펴본 sorting method가 모두 이 방법

- Lower bound of comparison sorting
worst case : Big-omega(nlgn) (이미 증명된 값) 따라서 이 것보다 더 빠른 sorting은 불가능함. 즉, merge sort, heap sort가 comparison 방법의 최적 방법이다.

non-comparison base sorting
상기한 문제점에 의해 더 빠른 정렬이 불가능하므로, 다른 방식을 사용한 정렬 알고리즘을 생각한다.


Counting Sort
counting sort는 각 element의 frequency를 count 함으로써 input array를 정렬하는 방법이다.

예를 들어 어떤 배열의 값 x가 있고, x보다 작은 값이 7개가 있다면, x는 8번째에 넣으면 된다. 이런 방식을 통해 크거나 작은 값이 몇 개나 있는지를 세서 정렬하는 방식이 된다.

count the frequency of each element -> determine the number of elements that less or equal to the specific element to find the correct place

* array A : 입력, array B : 출력, array C : frequency store working storage.
추가적인 공간 C가 필요하므로 counting sort는 in place 방법이 아니다. (space complexity of O(n))
이 array C에 각 index의 개수를 먼저 써넣고, 축적된 합계로 변환하면, 어떤 index (number)보다 작거나 같은 element가 몇개가 있는지 바로 확인할 수 있다.

input array A의 마지막 element부터 시작하여 array C의 해당 값과 동일한 index에 저장된 값을 확인하면 그 element의 올바른 위치를 바로 찾을 수 있다.
예를 들어A[i] = 3 , C[3] =7 이라면, 3의 위치는 7번째가 된다.

그리고, 올바른 위치를 찾은 index의 저장값은 하나씩 줄여가야 한다. (올바른 위치를 찾았으므로 unsorted part의 개수 = array C의 개수)
이를 반복하면 비교하는 과정 없이 세는 것 만으로 올바른 위치로 정렬할 수 있다.

counting sort method는 input array의 마지막 element부터 개수를 확인하여 올바른 위치를 찾아가므로 stable한 sorting 방법이다. (올바른 위치를 찾은 다음 index 값을 하나 줄이므로 그 앞에 있는 원소는 더 앞에 위치하게 된다.)

counting sort의 time complexity는 O(n+k)가 된다. (n은 input array size, k는 input array의 range=size of array C)
따라서 linear time인 O(n)로 비교 기반의 이전 방법보다 훨씬 빠르다는 것을 알 수 있다.

그러나, space complexity 측면에서 볼 때, 가장 큰수와 작은수의 차이가 매우 큰데도 불구하고, 그 사이에 값이 많이 존재하지 않는다면, Array C 공간의 대부분이 0으로 낭비되게 된다.
따라서 일반적으로 메모리 효율성을 위해 k가 n과 비교하여 작을 때 효과적이다.


Radix sort
sorting algorithm by sorting elements digit by digit. place value (자릿수) 를 이용하여 한 자리씩 정렬하면 결국 원하는 sorting 결과를 얻을 수 있다. (단, stable sort일 때 만 가능)

그리고 각 자릿수를 sorting 할 때 counting sort를 활용할 수 있다. 왜냐하면 십진법을 사용할 때 k=10이므로 n에 비해 작다는 것이 자명하여 매우 효과적이기 때문이다. 또한 stable sorting 방법이다. (물론 stable한 다른 방식을 사용해도 무방하다)

따라서 radix sort방식은 낮은 자리수부터 stable sorting 방법을 반복적으로 적용하고, 이를 완료하면 전체 정렬된 결과를 얻을 수 있다.
이를 위해 먼저 가장 큰 element를 찾고, 그 것을 자릿수를 확인하여 반복횟수를 결정한다. 그리고 각 반복마다 자릿수를 한자리씩 올려가며 정렬하면 된다.

앞서 counting sort와 동일하게, (그리고 일반적으로 각 자릿수 sorting에 counting sort를 사용하므로) time complexity는 O(d(n+k)) 가 된다. (d = 자릿수 개수, k=일반적으로 10) 따라서 radix sort도 O(n)의 linear time complexity를 가진다는 것을 알 수 있다.
또한 stable 해야만 자릿수에 따른 sorting이 가능하므로, radix sort도 stable 하다는 것을 알 수 있다. 그러나 sorting을 위한 추가 공간이 필요하므로 (counting sort의 array B & C) in-place하지는 않다. 또한 integer, alphabet 등 특정 type data에만 적용 가능하며(low flexibility) floating point 등을 정렬하기는 좋지 않다.