Implementation of Radix Sort in C++

Radix sort is a sorting algorithm that is used to sort numbers.

For example, if we are dealing with unsorted numbers, we know that these numbers are formed using digits from 0 to 9. So we need ten places labeled 0 to 9 to unsorted numbers.

Radix Sort in C++

So, let’s get started with an array of unsorted numbers: 10, 15, 1, 60, 5, 100, 25, 50

100 has three digits, whereas others have 2 or 1 digit. So, we will need to pad leading zeros with all numbers that are smaller than 100 to make them all three-digit number.

Now the array would be something like 010, 015, 001, 060, 005, 100, 25, 50

Since all of these have three digits, so the sorting process will require three passes.

PASS 1:

Sort the numbers using the 1st digit from the right.
Since the 010 has zero at the rightmost digit, we will place at Zero-th place, 015 at the 5th place, 001 at the 1-st place, 060 at the Zero-th place and so on.

0: 010, 060, 100, 050
1: 001
2:
3:
4:
5: 015, 005, 025
6:
7:
8:
9:

Now Pass one is complete. The array contains 010, 060,100, 050, 001, 015, 005, 025

PASS 2:

For the second pass, repeat the whole process using the 2nd digit from the right.
After completion of the second pass, the array would be 100, 001, 005, 010, 015, 025, 050, 060

PASS 3:

For the third pass, consider the 3rd digit from the right.

After the third pass, the array will be 001,005,010, 015, 025, 050, 060, 100. Remove the leading zeros at the end.

#include <iostream>
using namespace std;

#define MAX 10


void display(int arr[], int size);
int getMax(int arr[], int size);
void radixSort(int arr[], int size);

int main() {

  int arr[] = {10,15,1,60,5,100,25,50};


  int n = 8;

  cout<<"Unsorted array: ";
  display(arr, n);

  //sort the elements
  radixSort(arr, n);

  cout<<"Sorted array:   ";
  display(arr, n);

  return 0;
}

void display(int arr[], int size) {
  int i;
  for(i = 0; i < size; i++) {
    cout<<" " << arr[i];
  }
  cout<<endl;
}

int getMax(int arr[], int size) {
  int i, max = arr[0];
  for(i = 1; i < size; i++) {
    if(arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

void radixSort(int arr[], int size) {
  int i, max, bucket[MAX], count[10], expo = 1;

  //get the max value element in the unsorted array
  max = getMax(arr, size);

  while(max / expo > 0) {
    //reset count
    for(i = 0; i < 10; i++) {
      count[i] = 0;
    }

    //save count of the occurrence
    for(i = 0; i < size; i++) {
      count[ (arr[i] / expo) % 10 ]++;
    }

    //set count to contain the actual position of the digits
    for(i = 1; i < size; i++) {
      count[i] += count [i - 1];
    }

    //build the bucket
    for(i = size - 1; i >= 0; i--) {
      bucket[ count[ (arr[i]/expo) % 10 ]  - 1] = arr[i];
      count[ (arr[i]/expo) % 10 ]--;
    }

    //copy the result to arr
    for(i = 0; i < size; i++) {
      arr[i] = bucket[i];
    }

    //increase expo, 10^x
    expo *= 10;
  }
}

Related Articles