Radix Sort

It is a non-comparative sorting algorithm. It is technique a sorting technique that sorts the elements by first grouping the individual digits of the same place value. Then sort the elements according to their increasing and decreasing order.

Suppose, we have an array of 6 elements.

Let the array be :

[112, 52, 292, 23, 45, 788]

It is sorted according to the radix sort as shown in the figure below.

Please go through the counting sort before reading this article because counting sort is used as an intermediate sort in radix sort.

Example:

Original, unsorted list:

170, 45, 75, 90, 802, 24, 2, 66

Sorting by least significant digit (1s place) gives:

[*Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.]

Sorting by next digit (10s place) gives:

[*Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.]

802, 2, 24, 45, 66, 170, 75, 90

Sorting by most significant digit (100s place) gives:

2, 24, 45, 66, 75, 90, 170, 802

Implementation Using C:

#include <stdio.h>
 
 int getMax(int array[], int n) {
  int max = array[0];
  for (int i = 1; i < n; i++)
  if (array[i] > max)
  max = array[i];
  return max;
 }
 
 // Using counting sort
 void countingSort(int array[], int size, int place) {
  int output[size + 1];
  int max = (array[0] / place) % 10;
 
  for (int i = 1; i < size; i++) {
  if (((array[i] / place) % 10) > max)
  max = array[i];
  }
  int count[max + 1];
 
  for (int i = 0; i < max; ++i)
  count[i] = 0;
 
  // Cal count of elements
  for (int i = 0; i < size; i++)
  count[(array[i] / place) % 10]++;
 
  // Cal cummulative count
  for (int i = 1; i < 10; i++)
  count[i] += count[i - 1];
 
  // Place the elements in sorted order
  for (int i = size - 1; i >= 0; i--) {
  output[count[(array[i] / place) % 10] - 1] = array[i];
  count[(array[i] / place) % 10]--;
  }
 
  for (int i = 0; i < size; i++)
  array[i] = output[i];
 }
 
 void radixsort(int array[], int size) {
  // Get maximum element
  int max = getMax(array, size);
 
  // Apply counting sort to sort elements
  for (int place = 1; max / place > 0; place *= 10)
  countingSort(array, size, place);
 }
 
 void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
  printf("%d ", array[i]);
  }
  printf("\n");
 }
 
 int main() {
  int array[] = {120, 422, 584, 21, 7, 46, 788};
  int n = sizeof(array) / sizeof(array[0]);
  radixsort(array, n);
  printArray(array, n);
 }

Output:
 7 21 46 120 422 584 788

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Follow Programmers Door for more.

#programming #blog #placement #interview #radix_sort