C++ Program For Radix Sort Using Dynamic Array

In a positional numeral system, the radix (or base) is the number of digits used to represent numbers. In this tutorial, we are going to perform a radix sorting algorithm to sort an array.

Radix Sort - A basic Introduction

Radix Sort can lexicographically sort a variety of data types, including numbers, words, and emails, although it is most commonly used to sort collections of integers and strings (that are mapped to appropriate integer keys).

• This method groups the individual digits of the same place value before sorting the items. After that, arrange the items in ascending/descending order.
• Let's say we have a 4-element array. We'll start by sorting items by the value of the unit place. Then we'll sort the items by the value of the tenth position. This procedure continues until the last major location is reached.

Algorithm

As of now, we have a rough understanding of how radix sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Using counting_sort function to sort elements on basis of their places.
2. Calculate the count of elements.
3. Calculate the cumulative count
4. Place elements in sorted order
5. define a function radix_Sort()
6. Pass parameter array and place
7. Get Maximum element
8. Apply counting_sort()
9. Now the array is sorted
10. Print the array

C++ Program for Radix Sort

As discussed above in the algorithm, let us now dive into the programming part of the radix sort operation influenced by the algorithm.

#include <iostream>
using namespace std;

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;
}

void countingSort(int array[], int size, int place) {
  const int max = 10;
  int output[size];
  int count[max];

  for (int i = 0; i < max; ++i)
    count[i] = 0;
  for (int i = 0; i < size; i++)
    count[(array[i] / place) % 10]++;

  for (int i = 1; i < max; i++)
    count[i] += count[i - 1];

  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) {

  int max = getMax(array, size);

  // Apply counting sort to sort elements based on place value.
  for (int place = 1; max / place > 0; place *= 10)
    countingSort(array, size, place);
}

// Print an array
void printArray(int array[], int size) {
  int i;
  for (i = 0; i < size; i++)
    cout << array[i] << " ";
  cout << endl;
}

int main() {
  int array[] = {121, 432, 564, 23, 1, 45, 788};
  int n = sizeof(array) / sizeof(array[0]);
  radixsort(array, n);
  printArray(array, n);
}

1 23 45 121 432 564 788

Conclusion

In this tutorial, we have performed a radix sort operation in C++ to sort a graph. The radix sort algorithm doesn't have stability. The time complexity of the topological sort algorithm is O(n+k) and the space complexity is O(max).