Counting sort, bucket sort and radix sort

When comparing counting sort, bucket sort and radix sort, it’s important to know it’s about trade off between memory, time, and simplicity of data structure. Counting sort, bucket sort and radix sort can essentially all be considered as bucket sorting.

Radix sort: n log_r(k). Essentially radix sort performs bucket sort log_r(K) times. It can deal with larger key range (than bucket sort).    r is the base here. the larger is r the better time complexity we got.  but it also means more memory. remember the bucket   array in radix sort is of length r (smaller than n or maximum value of K)  If we use n as the base, it becomes a normal bucket sort. why?   cuz now we have only one ‘digit’, so we only do one bucket sort/counting sort.

Bucket sort: is a generalization of counting sort. The number of bucket sort used  is n. and range can be larger than n. thus we saved some space than in counting sort. but it loses the worse case of O(n+K).  Also the data has to be uniformly distributed.

Counting sort: O(n+k) time and O(K) space

 

Reference:

https://www.ics.uci.edu/~eppstein/161/960123.html

http://stackoverflow.com/questions/14368392/radix-sort-vs-counting-sort-vs-bucket-sort-whats-the-difference

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s