열혈 자료구조 - 10.2 복잡하지만 효율적인 알고리즘(3)

기수 정렬

- 정렬순서의 앞서고 뒷섬을 비교하지 않음

- 정렬 알고리즘의 한계로 알려진 O(log2n)을 뛰어넘을 수 있음

- 적용할 수 있는 대상이 매우 제한적

- 길이가 동일한 데이터들의 정렬에 용이

    -> {1,3,7,4,6,9} 기수 정렬 OK

    -> {"red","why,"zoo","box"} 기수 정렬 OK

    -> {21,9,125,-9} 기수 정렬 No

    -> {"book", "world", "test", "a"} 기수 정렬 No

    -> 3,4번째 경우 기수 정렬을 사용할 순 있지만 따로 가공(연산)해서 해야 하기 때문에 적절하지 않음

 

- 정렬 원리 : 비교를 진행하지 않음

    -> 기수 : 데이터를 구성하는 기본 요소

    -> 버킷 : 기수의 수에 해당하는 만큼의 공간

- 각 버킷은 해당하는 기수를 저장

- 오름차순, 내림차순에 따라 위에서부터 혹은 아래서부터 꺼내면 됨

 

- 기수 정렬의 방법

    -> LSD(List Significatn Digit) 가장 낮은 자리 수를 시작으로 정렬을 시작

    -> 버킷에 꺼내온 수를 다시 기준을 한칸 위로 옮겨 버킷에 담음

    -> MSD(Most Significatn Digit) 가장 높은 자리 수를 시작으로 정렬을 시작

        * LSD처럼 진행하면 제대로 정렬이 되지 않음

        * 앞의 결정 기준을 두번째가 다시 정렬시켜 버림

        * 그렇기 때문에 선별해서 진행을 해야 함