Radix Sort the best sorting algorithm
Hi, this is Shubham Mishra, I write blogs on algorithms and on the technologies. Today we will be going to deals with one of the best algorithm for sorting of an array. Before doing this algorithm I recommend you to visit other algorithms such as Merge Sort, so as to compare Radix sort algorithm with them. Radix sort is my favourite for its time complexity. Don't panic about time complexity for Radix, I will cover that later in this post.
Radix sort is also known as bucket sort. The radix sort is to sort decimal numbers, where the radix or base is 10, which need 10 buckets. This all buckets are numbered from 0 to 9. The most important part of the algorithm is that the number of iterations required is equal to the number of digits in the largest number in the list. For example, refer to the table below,
Now we will be going to see the radix sort function implemented in C. Use below function for sorting Integer arrays.
Above is the function for Radix sort. There is one major drawback of radix sort as you may have noticed that it works only for an Integer array. But the one big reason for its selection could be its time complexity which is analysed below,
The number of digits to be sorted needs 'k' iterations, distribution and collection of array elements need O(n+n = 2n) time. So total time complexity is O(2kn). Since it is of linear complexity, I think one should always think of Radix sort algorithm.
See my all posts Shubham Mishra
You can also visit my other posts such as Introduction to Recursion Algorithm and Data Structure and its type
Radix sort is also known as bucket sort. The radix sort is to sort decimal numbers, where the radix or base is 10, which need 10 buckets. This all buckets are numbered from 0 to 9. The most important part of the algorithm is that the number of iterations required is equal to the number of digits in the largest number in the list. For example, refer to the table below,
 |
| Radix Sort Algorithm |
Before moving on to the algorithm and code I would like to explain you in general terms that how radix sort works.
- The number of iteration is now known to you as per above table. In the first pass, 10 buckets are created. The array elements are selected one by one and separated in those 10 buckets on the basis of the digit at last position of the number. Let's consider in first iteration a number '290', is inserted in the 0th bucket since the last digit is '0'.
- The elements from all the buckets from '0' to '9' are collected in an array in the same sequence as it is in the buckets. Now in the second iteration first step is repeated but this time the bucket decision is judged on the basis of 2nd last digit. In the case of our previous example, '290', now it will be inserted in the 9th bucket.
- Again the bucket elements are inserted in an array in the same sequence as it is in the buckets from '0' to '9'. In this way, after performing the required number of iterations we get sorted array at the end.
Now, let's understand Radix sort diagrammatically. Suppose we have an array = [10, 5, 99, 105, 55, 100, 135, 141, 137, 200, 199]. Since in the array the largest number is 200 with 3 digits, so 3 iterations will be required.
1st Iteration:-
 |
| Radix Sort 1st Iteration |
2nd Iteration:-
 |
| Radix Sort 2nd Iteration |
3rd Iteration:-
 |
| Radix Sort 3rd Iteration |
Now we will be going to see the radix sort function implemented in C. Use below function for sorting Integer arrays.
Above is the function for Radix sort. There is one major drawback of radix sort as you may have noticed that it works only for an Integer array. But the one big reason for its selection could be its time complexity which is analysed below,
The number of digits to be sorted needs 'k' iterations, distribution and collection of array elements need O(n+n = 2n) time. So total time complexity is O(2kn). Since it is of linear complexity, I think one should always think of Radix sort algorithm.
See my all posts Shubham Mishra
You can also visit my other posts such as Introduction to Recursion Algorithm and Data Structure and its type
Ok great, we are done with this post,
Now if you like my way of talk, lets explore more blogs written by me and my inner knowledge,
Get to know answers for common search on Google : A blog for posts which can help you for daily life problems, such as where to get free images, Topic suggestion for the blog.
Computer Science algorithms and other knowledge share : A blog for posts such as best search algorithm, Top interview questions for diffrent technologies, knowledge share for some frameworks or programming languages for the interview or in general terms.
My ideas to solve real world problems : A blog where me shared and presented my ideas to solve a real world problems, this will be interesting for me.
Future of computer science technology discussed : A blog where me discussed about the future of computer science and new technologies which will change our way for looking to solve problems.
Ruby on Rails Web development Blog : As the name suggest, it is the blog for sharing few knowledge about RoR web development framework.
Liked my blogs, wanna to connect:
Thanks for reading this post, Have a good day :)
Comments
Post a Comment