The Royal Coding
Binary Search Bubble Sort Build A Max Heap Build A Min Heap Graph Traversal Heap Sort Implementing A Basic Hash Table Implementing A Binary Search Tree Implementing A Queue Implementing A Stack Insertion Sort Length Of Linked List Linear Search Linked Lists Merge A Two Sorted Linked List Merge Sort Quick Sort Redix Sort Reverse A Linked List Selection Sort Ternary Search Suffix Automata Construction

Python/C/C++/JAVA

Advanced Practice Programs with Code and Concept

By D.S

Radix Sorting

Radix sort is a simple yet effective algorithm for sorting an array or list of integers. It works by sorting the elements based on their individual digits, from least significant to most significant. The digits are first divided into separate buckets, with each bucket containing all the numbers that have the same digit at a given position. Then these buckets are sorted and combined in order to produce the final sorted output. Radix sort has a time complexity of O(nk), where n is the number of elements in the input list and k is the maximum length of any element in terms of digits. It can be implemented using an array of queues or linked lists for storing and sorting each digit's values. Overall, radix sort is an efficient way to sort large collections of integers without having to rely on comparisons between elements as with other sorting algorithms like quicksort or mergesort.

(a.) C Program

#include <stdio.h>

void countingSort(int arr[], int n, int exp) {
    int output[n], count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

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

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];

    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSort(arr, n, exp);
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}
Output:-
Sorted array:
[2, 24, 45, 66, 75, 90, 170, 802]

(b.) C++ Program

#include <iostream>
      using namespace std;
      
      void countingSort(int arr[], int n, int exp) {
          int output[n], count[10] = {0};
      
          for (int i = 0; i < n; i++)
              count[(arr[i] / exp) % 10]++;
      
          for (int i = 1; i < 10; i++)
              count[i] += count[i - 1];
      
          for (int i = n - 1; i >= 0; i--) {
              output[count[(arr[i] / exp) % 10] - 1] = arr[i];
              count[(arr[i] / exp) % 10]--;
          }
      
          for (int i = 0; i < n; i++)
              arr[i] = output[i];
      }
      
      void radixSort(int arr[], int n) {
          int max = arr[0];
          for (int i = 1; i < n; i++)
              if (arr[i] > max)
                  max = arr[i];
      
          for (int exp = 1; max / exp > 0; exp *= 10)
              countingSort(arr, n, exp);
      }
      
      void printArray(int arr[], int n) {
          for (int i = 0; i < n; i++)
              cout << arr[i] << " ";
          cout << endl;
      }
      
      int main() {
          int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
          int n = sizeof(arr) / sizeof(arr[0]);
          radixSort(arr, n);
          cout << "Sorted array: " << endl;
          printArray(arr, n);
          return 0;
      }
Output:-
Sorted array:
[2, 24, 45, 66, 75, 90, 170, 802]

(c.) Python Program

def countingSort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]


def radixSort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        countingSort(arr, exp)
        exp *= 10


arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:")
print(arr)
radixSort(arr)
print("Sorted array:")
print(arr)
Output:-
Original array:
[170, 45, 75, 90, 802, 24, 2, 66]
Sorted array:
[2, 24, 45, 66, 75, 90, 170, 802]

(d.) Java Program

import java.util.Arrays;

      public class Main {
          static void countingSort(int arr[], int n, int exp) {
              int output[] = new int[n];
              int count[] = new int[10];
      
              Arrays.fill(count, 0);
      
              for (int i = 0; i < n; i++)
                  count[(arr[i] / exp) % 10]++;
      
              for (int i = 1; i < 10; i++)
                  count[i] += count[i - 1];
      
              for (int i = n - 1; i >= 0; i--) {
                  output[count[(arr[i] / exp) % 10] - 1] = arr[i];
                  count[(arr[i] / exp) % 10]--;
              }
      
              for (int i = 0; i < n; i++)
                  arr[i] = output[i];
          }
      
          static void radixSort(int arr[], int n) {
              int max = arr[0];
              for (int i = 1; i < n; i++)
                  if (arr[i] > max)
                      max = arr[i];
      
              for (int exp = 1; max / exp > 0; exp *= 10)
                  countingSort(arr, n, exp);
          }
      
          public static void main(String[] args) {
              int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
              int n = arr.length;
              radixSort(arr, n);
              System.out.println("Sorted array:");
              for (int i = 0; i < n; i++)
                  System.out.print(arr[i] + " ");
          }
      }
Output:-
Sorted array:
[2, 24, 45, 66, 75, 90, 170, 802]

How did you feel about this post?

😍 🙂 😐 😕 😡

Was this helpful?

👍 👎