Radix Sort

https://m.blog.naver.com/PostView.nhn?blogId=itperson&logNo=220847283030&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

기수 정렬

  • 원소들이 있을 때 각각의 자리수 별로 정렬을 하여 완벽히 정렬된 배열을 만들어 내는 알고리즘
  • 일의 자리부터 정렬하면서 최고 자리 수 까지 정렬 해 간다
  • 가령 56 , 59가 있으면 1의 자리에서 6이 작으니까 앞에 오고, 10의자리 비교 시 5로 값이 같더라도, stable sort가 보장되기 때문에 순서가 바뀌지 않고 그대로 56, 59 순서가 유지 된다. 이런식으로 최고 자리수 까지 정렬해가면 stable sort라는 속성 덕분에 전체적으로 정렬이 됨
  • 카운팅 소트가 O(n+k)인데 자리수 d만큼 카운팅 소트를 하므로, 시간 복잡도는 O(d (n+k))
  • 정렬 자체는 카운팅 소트(stable sort)로 하면 됨

  • t1, t2는 각 자리수를 구하여 counting 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