ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Count sort
    알고리즘/자료구조 2016. 7. 23. 19:47

    quicksort나 mergesort처럼 일반적인 sorting알고리즘은 O(NlogN)을 가지나 sorting에 사용되는 값들을 사전에 알고 있는 경우에는 시간복잡도를 O(N)까지 단축 시킬 수 있다. 그중에서도 가장 강력하게 사용되는 알고리즘이 Count sorting이다.


    Count sorting은 정렬에 쓰이는 값이 충분히 작은 경우(배열의 최대 크기가 될 수 있는 값보다 작아야 한다)에 주로 사용할 수 있다. 배열의 인덱스는 이미 자동적으로 정렬되있으니 수열에 포함된 값 각각의 개수를 배열의 인덱스에 해당하는 값에 저장해둔 후 그 그 개수를 참고해서 정렬하는 방식이다.


    글로 설명하기에는 어려우니 예를 들어보자. 


    5 3 6 7 4 5 인 수열을 정렬한다고 하자. 위 수열의 각 값의 개수를 관리하는 배열을 count[10]라 하자. 그러면 count의 값은 다음과 같을 것이다.


    count[0] = 0

    count[1] = 0

    count[2] = 0

    count[3] = 1

    count[4] = 1

    count[5] = 2

    count[6] = 1

    count[7] = 1

    count[8] = 0

    count[9] = 0


    정렬하고자한 수열의 값들은 이미 배열의 index를 통해서 자동적으로 정렬이 되었다. 이제 각각의 개수만큼 표현만 해주면 된다.


    count[0] = 0 -> 수열에 포함 안됨

    count[1] = 0 -> 수열에 포함 안됨

    count[2] = 0 -> 수열에 포함 안됨

    count[3] = 1 -> 3

    count[4] = 1 -> 3, 4

    count[5] = 2 -> 3, 4, 5, 5

    count[6] = 1 -> 3, 4, 5, 5, 6

    count[7] = 1 -> 3, 4, 5, 5, 6, 7

    count[8] = 0 -> 수열에 포함 안됨

    count[9] = 0 -> 수열에 포함 안됨


    생각해보면 정말 자명하고 직관적이어서 쉽다. 구현도 쉬워서 자주자주 써먹을 수 있을 것 같으나 써야할 때를 자주 깜빡한다.


    가장 최근에 푼 문제중에는 좌표상에 표현되는 값을 x, y로 정렬해야 했는데 조건이 x, y < 1000000이었다. 이때도 count sort를 사용해서 정렬 할 수 있었는데 구현도 어려운 quicksort를 구현하느라 시간을 한참 소비했다 ㅡㅡ


    다른분이 정렬한 코드를 참고해서 새롭게 작성한 후 올린다..




    '알고리즘 > 자료구조' 카테고리의 다른 글

    완전순열(교란순열)  (0) 2016.12.04
    LCA(Lowest Common Ancestor)  (0) 2016.07.30
    Segment Tree  (0) 2015.09.07
    SQRT Decomposition  (0) 2015.09.05
    LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27

    댓글

Designed by Tistory.