Radix sort program in C#

Radix sort is a non-comparative sorting algorithm that sorts integers by grouping them based on individual digits or radix. It works by distributing the elements into buckets based on the value of each digit, from the least significant digit (LSD) to the most significant digit (MSD). Radix sort can be performed using two main approaches: LSD radix sort and MSD radix sort.

LSD Radix Sort: LSD radix sort starts sorting from the least significant digit to the most significant digit. The algorithm performs multiple passes, each pass distributing the elements into buckets based on the current digit being examined. After each pass, the elements are collected from the buckets and combined to form a new array. LSD radix sort continues this process until all digits have been examined, resulting in a sorted array.

MSD Radix Sort: MSD radix sort starts sorting from the most significant digit to the least significant digit. Unlike LSD radix sort, it uses a recursive approach. The algorithm recursively partitions the array into buckets based on the current digit being examined. If the current digit is the least significant digit, the algorithm uses a stable sorting algorithm (e.g., insertion sort) to sort the elements within each bucket. MSD radix sort continues this process recursively for each significant digit until all digits have been examined.

using System;

public class RadixSort
{
    public static void Main()
    {
        int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };

        Console.WriteLine("Original array:");
        PrintArray(arr);

        Sort(arr);

        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }

    public static void Sort(int[] arr)
    {
        int max = GetMax(arr);

        // Perform LSD radix sort
        for (int exp = 1; max / exp > 0; exp *= 10)
        {
            CountingSort(arr, exp);
        }
    }

    public static void CountingSort(int[] arr, int exp)
    {
        int n = arr.Length;
        int[] output = new int[n];
        int[] count = new int[10];

        // Count the occurrences of each digit
        for (int i = 0; i < n; i++)
        {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

        // Calculate the cumulative count
        for (int i = 1; i < 10; i++)
        {
            count[i] += count[i - 1];
        }

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

        // Copy the output array to the original array
        for (int i = 0; i < n; i++)
        {
            arr[i] = output[i];
        }
    }

    public static int GetMax(int[] arr)
    {
        int max = arr[0];
        for (int i = 1; i < arr.Length; i++)
        {
            if (arr[i] > max)
            {
                max = arr[i];
            }
        }
        return max;
    }

    public static void PrintArray(int[] arr)
    {
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}

In this example, the Sort method implements the LSD radix sort algorithm. The CountingSort method is used as a subroutine to sort the elements based on the current digit. The GetMax method is used to find the maximum element in the array, which is required to determine the number of passes in the radix sort. The Main method initializes an array of integers, calls the Sort method to sort the array using radix sort, and then prints both the original and sorted arrays using the PrintArray method.

Original array:
170 45 75 90 802 24 2 66
Sorted array:
2 24 45 66 75 90 170 802

The program demonstrates the step-by-step execution of the LSD radix sort algorithm on the given array and outputs the sorted array.

Radix sort is a stable sorting algorithm that has a time complexity of O(nk), where n is the number of elements and k is the maximum number of digits in the input. It is particularly efficient for sorting integers with a fixed number of digits or a small range of values.