Counting Sort

http://bowbowbow.tistory.com/8#counting-sort

계수 정렬

  • 각각의 원소가 몇 개 존재하는지 counting 한 후 개수를 센 배열을 통해서 정렬된 배열을 뽑아내는 방법
  • 배열에 index에 해당하는 값 counting하는거라 데이터는 무조건 양의 정수, O~K 범위 일때, K가 너무 크면 안되기 때문에 데이터 제한이 존재. 가령 0, 2, 0, 200 만 해도 index 200까지 있어야하니까 메모리낭비.
  • counting sort 는 아래 예시처럼 정렬 숫자가 작은 범위 안에 있을때 주로 사용. O(n+k)으로 범위가 작을 경우, 퀵소트보다도 유리
  • ori array : 5, 5, 3, 4, 5, 1, 0, 4, 1 ,3 0, 2, 4, 2, 3, 0 이면
  • counting array의 0~5 index 값은 3, 2, 2, 3, 3, 3 이다
counting array
num 0 1 2 3 4 5
cnt 3 2 2 3 3 3
  • sorted array : 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5 로 만드는 방법은
counting array
num 0 1 2 3 4 5
cnt 3 2 2 3 3 3
accumulated 3 5(3+2) 7(5+2) 10(7+3) 13(10+3) 16(13+3)
  • 등장 횟수를 위처럼 누적 시킨다.
  • 정렬할 배열을 뒤에서 앞으로 순회하면서 sorted array에 넣어줌. 위 과정에서 구한 누적 합이 ori array의 숫자가 sorted array의 어디에 위치해야 할지 정확하게 알려줌
  • accumulated가 가리키는 sorted array의 index에 해당 숫자를 위치시키고, 해당 수 accumulated 값을 하나씩 빼준다
  •  http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html
  • 위 애니메이션 처럼 반복하면 정렬 완료
  • 위처럼 뒤에서부터 순환하며 누적합 하나씩 빼주면서 배열하는건,이 순서로 해주어야 stable sort가 되기 때문.
  • stable sort란 , 굳이 소팅 될 필요가 없는 값들(같은 값)은 이전의 순서를 유지해 주는 것. radix sort에서 stable sort가 보장 되어야 하기 때문에 중요한 개념

 

It's only fair to share...Share on Facebook
Facebook
Share on Tumblr
Tumblr
Share on Google+
Google+
Tweet about this on Twitter
Twitter
Email this to someone
email
Musicals, Travel, Photo, Coding, English, Cat