Radix Sort Example And C Code | Coding Bot

Like Us On Facebook

Follow Us On Twitter


Wednesday, 20 February 2013

Radix Sort Example And C Code


Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.

Basic Steps To Be Performed:

Each key is first figuratively dropped into one level of buckets corresponding to the value of the rightmost digit. Each bucket preserves the original order of the keys as the keys are dropped into the bucket. There is a one-to-one correspondence between the number of buckets and the number of values that can be represented by a digit. Then, the process repeats with the next neighboring digit until there are no more digits to process. In other words:
  1. Take the least significant digit of each key.
  2. Group the keys based on that digit, but otherwise keep the original order of keys. 
  3. Repeat the grouping process with each more significant digit.
The sort in step 2 is usually done using bucket sort or counting sort, which are efficient in this case since there are usually only a small number of digits.

Step-by-step example:

Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66
Sorting by least significant digit (1s place) gives:
170, 90, 8022, 24, 45, 75, 66
Sorting by next digit (10s place) gives:
802, 2, 24, 45, 66, 170, 75, 90
Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802
It is important to realize that each of the above steps requires just a single pass over the data, since each item can be placed in its correct bucket without having to be compared with other items.
Some LSD radix sort implementations allocate space for buckets by first counting the number of keys that belong in each bucket before moving keys into those buckets. The number of times that each digit occurs is stored in an array. Consider the previous list of keys viewed in a different way:
170, 045, 075,090, 002, 024, 802, 066
The first counting pass starts on the least significant digit of each key, producing an array of bucket sizes:
2 (bucket size for digits of 0: 170, 090)
2 (bucket size for digits of 2: 002, 802)
1 (bucket size for digits of 4: 024)
2 (bucket size for digits of 5: 045, 075)
1 (bucket size for digits of 6: 066)
A second counting pass on the next more significant digit of each key will produce an array of bucket sizes:
2 (bucket size for digits of 0: 002, 802)
1 (bucket size for digits of 2: 024)
1 (bucket size for digits of 4: 045)
1 (bucket size for digits of 6: 066)
2 (bucket size for digits of 7: 170, 075)
1 (bucket size for digits of 9: 090)
A third and final counting pass on the most significant digit of each key will produce an array of bucket sizes:
6 (bucket size for digits of 0: 002, 024, 045, 066, 075, 090)
1 (bucket size for digits of 1: 170)
1 (bucket size for digits of 8: 802)


C Program For Radix Sort:

/* Double-Click To Select Code */

#include<stdio.h>
#include<conio.h>

radix_sort(int array[], int n);
void main()
{
 int array[100],n,i; 
 clrscr();
 printf("Enter the number of elements to be sorted: ");
 scanf("%d",&n);
 printf("\nEnter the elements to be sorted: \n");
 for(i = 0 ; i < n ; i++ )
 {
  printf("\tArray[%d] = ",i);
  scanf("%d",&array[i]);
 }
 
 printf("\nArray Before Radix Sort:");  //Array Before Radix Sort
 for(i = 0; i < n; i++)
 {
  printf("%8d", array[i]);
 }
 printf("\n");
 
 radix_sort(array,n);

 printf("\nArray After Radix Sort: ");  //Array After Radix Sort
 for(i = 0; i < n; i++)
 {
  printf("%8d", array[i]);
 }
 printf("\n");
 getch();
}

radix_sort(int arr[], int n)
{
 int bucket[10][5],buck[10],b[10];
 int i,j,k,l,num,div,large,passes;
 
 div=1;
 num=0;
 large=arr[0];
 
 for(i=0 ; i<n ; i++)
 {
  if(arr[i] > large)
   {
    large = arr[i];
   }
   
  while(large > 0)
  {
   num++;
   large = large/10;
  }
  
  for(passes=0 ; passes<num ; passes++)
  {
   for(k=0 ; k<10 ; k++)
   {
    buck[k] = 0;
   }
   for(i=0 ; i<n  ;i++)
   {
    l = ((arr[i]/div)%10);
    bucket[l][buck[l]++] = arr[i];
   }
   
   i=0;
   for(k=0 ; k<10 ; k++)
   {
    for(j=0 ; j<buck[k] ; j++)
    {
     arr[i++] = bucket[k][j];
    }
   }   
   div*=10;   
  }
 }
}

Output of Program:

Radix Sort Example And C Code


Please Comment If You Liked This Post !! 

This article uses material from the Wikipedia article Radix Sort which is released under the Creative Commons Attribution-Share-Alike License 3.0

Do you like this post? Please link back to this article by copying one of the codes below.

URL: HTML link code: Forum link code:

17 comments:

  1. Just excellent. I have been searching everywhere online for good Radix sort. Hope there's one with you to specifically sort a string.....

    ReplyDelete
  2. bucket[l][buck[l]++] = arr[i] .Can You explain me this step please ?

    ReplyDelete
  3. Bucket is a 2-D array. In this step, we are assigning whatever value of 'L' we are getting in arr[i], into:
    bucket[l][buck[l]++] = arr[i];

    where "l = ((arr[i]/div)%10);"

    ReplyDelete
  4. Thank you for your early reply .I appreciate it .Yes ,I knew that its 2-D array but my question was which values would be store in buck [i] its also 1-D array .I got its explanation though and thank you again for your effort :D .

    ReplyDelete
  5. and void main() ? Seriously? I assume you also use Turbo C++

    ReplyDelete
  6. and void main() ? Seriously? Do you also use Turbo C++?

    ReplyDelete
  7. conio.h and void main()? Seriously?

    ReplyDelete
  8. Most students are still taught to execute C/C++ languages in Turbo C++, that's why these codes have been written in Turbo C++ friendly way.

    ReplyDelete
  9. I think people will move to GCC if they know it exists, most people in my class used think that Turbo C++ is latest C/C++ compiler. So I told them about GCC and forced teachers to teach in GCC, teacher asked the Admin to change OS to Ubuntu and now everyone uses GCC on Linux, this way College saved money and people are now following standards. People change if you tell them why they need to change!!

    ReplyDelete
  10. I agree with you. Eventually change will come.

    ReplyDelete
  11. It almost worked!
    Array Before Radix Sort:
    50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

    Array After Radix Sort:
    1 2 3 4 5 6 7 8 9 6 7 8 9 14 15 16 17 18 19 15 16 17 18 19 25 26 27 28 29 25 26 27 28 29 35 36 37 38 39 35 36 37 38 39 45 46 47 48 49 45

    ReplyDelete
  12. please correct started for loop, its working,
    modify in c#


    ================================
    public int[] radix_sort(int[] arr, int n)

    {

    int[,] bucket = new int[10, 5];

    int[] buck = new int[10];





    int i,j,k,l,num,div,large,passes;



    div=1;

    num=0;

    large=arr[0];



    for(i=0 ; i large)

    {

    large = arr[i];



    }

    }

    while(large > 0)

    {

    num++;

    large = large/10;

    }



    for(passes=0 ; passes<num ; passes++)

    {

    for(k=0 ; k<10 ; k++)

    {

    buck[k] = 0;

    }

    for(i=0 ; i<n ;i++)

    {

    l = ((arr[i]/div)%10);

    bucket[l,buck[l]++] = arr[i];

    }



    i=0;

    for(k=0 ; k<10 ; k++)

    {

    for(j=0 ; j<buck[k] ; j++)

    {

    arr[i++] = bucket[k,j];

    }

    }

    div*=10;

    }



    return arr;

    }

    ReplyDelete
  13. teri maa ka bhosda madarchod... Chutiya code hai. Sort to hua hee nahi. GAnd k dhakkan

    chut salaaaaaa.. :D

    ReplyDelete
  14. can u please explain me the radix function of this program line by line either here or at guneet.jass@gmail.com?
    thank you

    ReplyDelete
  15. Sir please explain me the radix sort function in details..its very urgent as i've got a practical on 12th of may and i gotta knw the working in that function of radix sort soon..please do the needful..
    either explain the same here..or inbox me on guneet.jass@gmail.com

    ReplyDelete