Count Sort and Radix Sort
Hello Geeks! How have you been? Together,we have completed bubble sort, insertion sort, selection sort, merge sort and quick sort!
Whoa! That’s impressive, right?
Today, we shall discuss a couple of more sorting techniques! Counting sort and Radix sort. These are very, very intriguing and captivating. So, read on!
Count sort
Counting sort is a table sorting technique which is usually used along with radix sort. In this technique, the sorting process is based on the number of occurrences of an element in an array.
Explanation
The best explanation for count sort is possibly through sketches and images. These two images will tell you a thousand words on counting sort! So, no perplexing and puzzling words, and only crystal clear concepts!
Understanding Counting sort:
Once we get this auxiliary table, then we proceed as:
Use
Mostly, counting sort is used along with radix sort to sort a given list of bounded integers. But it can also be used individually, if the range of numbers is small.
Time and space complexity
| Worst-case-performance | O(N+ number of possible values) |
| Best-case-performance | O(N+number of possible values) |
| Average-case-performance | O(N+number of possible values) |
| Worst-case-space complexity | O(N+number of possible values) |
Advantages
- It is a stable sorting algorithm, meaning, it preserves the existing order of equal keys elements
- Takes linear time for operation
Disadvantages
1. Needs more working memory
2. Implementation is a bit more difficult than other sorting techniques
Radix Sort
Radix sort is a linear-time sorting algorithm. It is used to sort elements having larger values.
The idea behind Radix Sort is to sort elements ‘bit-by-bit’, that is sort elements digit by digit starting from least significant digit(LSB) to most significant digit (MSB). Radix sort uses counting sort as a sub-sort.
Understanding Radix sort:
Find maximum number of digits in largest element.
Obtain the required bit (LSB to MSB) using modulus operator(%).
Sort the elements based on their individual bits using count sort.
Repeat for consecutive bits till MSB have been sorted.
Let us understand with an example:
Explanation
The least significant bit of each element is obtained and compared. Elements are sorted by their LSB, using COUNT SORT
Then, the consecutive bits are obtained and compared, and the elemens are sorted by order of their first 2 bits (from lsb).
Depending on the maximum number of digits in the largest elements, the consecutive are compared and sorted.
Finally, the Most significant bit is obtained and sorted using count sort. Now the whole array is in the sorted order.
A point to be noted here is that radix sort works because the order of the elements are taken into account and preserved in each step. This is to ensure that elements are sorted completely, with respect to all their bits.
Time and space complexity
| Worst-case-performance | O( n2 ) |
| Best-case-performance | O(nk) |
| Average-case-performance | O(nk) |
| Worst-case-space complexity | O(n+k) |
*k is the length of the keys
Uses
It is used to create a ‘suffix array’ using the skew DC3 algorithm (Kärkkäinen-Sanders-Burkhardt).
Advantages
- Radix Sort is faster for sorting shorter elements.
- It is stable because it preserves existing order of equals keys.
Disadvantages
It is not efficient on very long elements because the total sorting time is proportional to length of element.
For any doubts or ambiguities, mail us at everythinggeeky.101@gmail.com, or comment below!
Don’t forget to Like, Comment and Share with your friends.
Stay Tuned for Everything Geeky.
See you next week!
Cheers!
Team Bitxorbytes
Follow us on instagram: @bitxorbytes
Cover Image Credits: https://alphablots.com/product/typographic-birthday-cards-pack-of-six/
BitXorBytes 