Radix Sorting Implementation with C#

• Download sample project - 17.16 KB

Introduction

The article presented here is a description of the implementation of radix sort algorithm with C#.

Radix sort is a sorting algorithm that sorts integers by processing individual digits. Because integers can represent strings of digits, it can sort integers with Worst case performance O(K*N) where K is the number of digits and N is the number of integers being sorted.

There are two types of radix sorting:

1. Least significant digit (LSD) radix sort
2. Most significant digit (MSD) radix sort

LSD radix sorts process the integer representations starting from the least significant digit and move towards the most significant digit. MSD radix sorts work the other way around.

In this article, we will focus on the (LSD) radix sort.

Necessary Knowledge

A general knowledge of sorting algorithms is essential.

How the algorithm implementation works:

Let us assume that we have an array of integers like this {505,146,252,75}.

We assign each of them a key: (We will explain why we use keys later in the article.)

The algorithm is divided into two parts which are "Radix and counting algorithms". We will explain each of them separately:

1. Radix

The Code for the Radix Sorting Methods

public static int[] Sort(int[] array)
{
    return RadixSortAux(array, 1);
}
        static int[] RadixSortAux(int[] array, int digit)
        {
            bool Empty = true;
            KVEntry[] digits = new KVEntry[array.Length];//array that holds the digits;
            int[] SortedArray = new int[array.Length];//Hold the sorted array
            for (int i = 0; i < array.Length; i++)
            {
                digits[i] = new KVEntry();
                digits[i].Key = i;
                digits[i].Value = (array[i] / digit) % 10;
                if (array[i]/digit!=0)
                    Empty = false;
            }

            if (Empty)
                return array;

            KVEntry[] SortedDigits = CountingSort(digits);
            for (int i = 0; i < SortedArray.Length; i++)
                SortedArray[i] = array[SortedDigits[i].Key];
            return RadixSortAux(SortedArray, digit * 10);
        } 

Let's look at the RadixSortAux method. It starts by taking all digits of all numbers from CountingSort method for sorting and sorting the numbers according to the digits arrangement.

Foreach iteration in RadixSortAux digit is multiplied by 10 so as to get the next digit, and we check foreach number if number/digit not equal to zero therefore there are more digits to sort. If not, this means that we have reached the end of the numbers.

a) Taking array of the unit digits of the array {5,6,2,5} let it be arrayA.

Start by assigning them keys :

b) Use the counting algorithm to sort them. I'll explain the counting algorithm later in the article. The digits array will be as follows:

Note that the counting algorithm is a stable algorithm so the two '5' values don't swap, stability is essential in the radix algorithm.

c) After sorting the array of digits, we sort their numbers according to their arrangement:

So, numbers now are sorted according to their least significant digit...

d) Now we take an array of the tenth digit {5,0,7,4} and make the same operation on it, so the numbers after being sorted will be as follows:

e) Now we just have one more step and the array will be sorted.:) We take an array of the hundredth digit {5,1,0,2} and sort the numbers according to the sorted array of hundredth digits:

Finally, the array is sorted now. We just have to know how the counting algorithm works for sorting the digits.

2. Counting Algorithm

static KVEntry[] CountingSort(KVEntry[] ArrayA)
{
    int[] ArrayB = new int[MaxValue(ArrayA) + 1];
    KVEntry[] ArrayC = new KVEntry[ArrayA.Length];

    for (int i = 0; i < ArrayB.Length; i++)
	ArrayB[i] = 0;

    for (int i = 0; i < ArrayA.Length; i++)
	ArrayB[ArrayA[i].Value]++;

    for (int i = 1; i < ArrayB.Length; i++)
	ArrayB[i] += ArrayB[i - 1];

    for (int i = ArrayA.Length - 1; i >= 0; i--)
    {
	int value = ArrayA[i].Value;
	int index = ArrayB[value];
	ArrayB[value]--;
	ArrayC[index - 1] = new KVEntry();
	ArrayC[index - 1].Key = i;
	ArrayC[index - 1].Value = value;
    }
    return ArrayC;
}

static int MaxValue(KVEntry[] arr)
{
    int Max = arr[0].Value;
    for (int i = 1; i < arr.Length; i++)
        if (arr[i].Value > Max)
	   Max = arr[i].Value;
        return Max;
}

a) The counting algorithm creates another array of length 7 which is the (maximum number in arrayA) + 1 , then we add the number of recurrences foreach element of ArrayA in its index in ArrayB as follows:

ArrayA

ArrayB

The number of recurrences of 5 in ArrayA is put in ArrayB[5] which is 2, the number of recurrences of 6 in ArrayA is put in ArrayB[6] which is 1, and so on.

b) We start moving on ArrayB from ArrayB[1] to the end and increment each of them with the value in the index before:

ArrayB

c) Then we use a third array. Let it be ArrayC. This is the array in which integers will be put in sorted.

We start moving on all the integers in ArrayA from the right to the left: Let's say now we are on ArrayA[1], the value is 5, we now go to the index 5 in ArrayB and get its value. Now we get the index of value 5 in ArrayC which is equal to ArrayB[5] - 1. You can understand it from the following figure:

After this step, we should have a sorted array which is ArrayC:

ArrayC

Why We Use the Key/Value Pair

When sorting each digit for all numbers separately, we need to sort the numbers according to the digits arrangement so we assign them keys to sort the numbers:

The Numbers Array

Digits Array after Sorting which is ArrayC

So, by sorting the numbers array according to ArrayC, the arrangement of keys will be:

struct KVEntry
{
    int key;
    int value;

    public int Key
    {
  	get
	{
             return key;
	}
	set
	{
	    if (key >= 0)
		key = value;
	    else
		throw new Exception("Invalid key value");
	}
    }

    public int Value
    {
	get
	{
             return value;
	}
	set
	{
	    this.value = value;
	}
    }
}