C#: Radix sort

C# Sharp Searching and Sorting Algorithm: Exercise-10 with Solution

Write a C# Sharp program to sort a list of elements using Radix sort algorithm.

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.

An Example :

Original, unsorted list : 272, 45, 75, 81, 501, 2, 24, 66

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

272, 81, 501, 2, 24, 45, 75, 66

Here we keep 501 before 2, because 501 occurred before 2 in the original list, and similarly for pairs 272 & 81 and 45 & 75.

Sorting by next digit (10s place) gives :

501, 2, 24, 45, 66, 272, 75, 9

Notice that 501 again comes before 2 as 501 comes before 2 in the previous list.

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

2, 24, 45, 66, 75, 81, 272, 501

It is important to realize that each of the above steps requires just a single pass over the data, since each item can be placed in its correct bucket without having to be compared with other items.

Some radix sort implementations allocate space for buckets by first counting the number of keys that belong in each bucket before moving keys into those buckets. The number of times that each digit occurs is stored in an array. Consider the previous list of keys viewed in a different way :

272, 045, 075, 081, 002, 024, 501, 066

The first counting pass starts on the least significant digit of each key, producing an array of bucket sizes :

• 2 (bucket size for digits of 0: 272, 081)
• 2 (bucket size for digits of 2: 002, 501)
• 1 (bucket size for digits of 4: 024)
• 2 (bucket size for digits of 5: 045, 075)
• 1 (bucket size for digits of 6: 066)

A second counting pass on the next more significant digit of each key will produce an array of bucket sizes :

• 2 (bucket size for digits of 0: 002, 501)
• 1 (bucket size for digits of 2: 024)
• 1 (bucket size for digits of 4: 045)
• 1 (bucket size for digits of 6: 066)
• 2 (bucket size for digits of 7: 272, 075)
• 1 (bucket size for digits of 9: 081

A third and final counting pass on the most significant digit of each key will produce an array of bucket sizes :

• 6 (bucket size for digits of 0: 002, 024, 045, 066, 075, 081)
• 1 (bucket size for digits of 1: 272)
• 1 (bucket size for digits of 8: 501)

Sample Solution:-

C# Sharp Code:

using System;

namespace Radix_Sort
{
    class Program
    {
        // Method to perform Radix Sort
        static void Sort(int[] arr)
        {
            int i, j;
            int[] tmp = new int[arr.Length];

            // Loop through each bit of the integers (from the most significant to the least significant bit)
            for (int shift = 31; shift > -1; --shift)
            {
                j = 0;

                // Iterate through the array to classify the elements based on the current bit
                for (i = 0; i < arr.Length; ++i)
                {
                    // Check the current bit status for the integer
                    bool move = (arr[i] << shift) >= 0;

                    // If the current bit matches the required position
                    if (shift == 0 ? !move : move)   
                        arr[i - j] = arr[i]; // Move the element to the left side of the array
                    else                             
                        tmp[j++] = arr[i]; // Move the element to the temporary array
                }

                // Copy the elements from the temporary array to the original array at the end
                Array.Copy(tmp, 0, arr, arr.Length - j, j);
            }
        }

        static void Main(string[] args)
        {
            int[] arr = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };

            Console.WriteLine("\nOriginal array : ");
            foreach (var item in arr)
            {
                Console.Write(" " + item);
            }

            // Perform Radix Sort on the array
            Sort(arr);

            Console.WriteLine("\nSorted array : ");
            foreach (var item in arr)
            {
                Console.Write(" " + item);
            }

            Console.WriteLine("\n");
        }
    }
}

Sample Output:

Original array :                                                                                              
 2 5 -4 11 0 18 22 67 51 6                                                                                    
Sorted array :                                                                                                
 -4 0 2 5 6 11 18 22 51 67 

Flowchart:

C# Sharp Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C# Sharp program to sort a list of elements using Quick sort
Next: Write a C# Sharp program to sort a list of elements using the selection sort algorithm.