Click here to Skip to main content
Click here to Skip to main content

Tagged as

Radix Sorting Implementation with C#

, 28 Feb 2009
Rate this:
Please Sign up or sign in to vote.
Radix sorting implementation with C#

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

Key Value
1 505
2 146
3 252
4 75

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 :

Key Value
1 5
2 6
3 2
4 5

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:

Key Value
3 2
1 5
4 5
2 6

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:

Key Value Number
3 2 252
1 5 505
4 5 75
2 6 146

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:

Key Value Number
1 0 505
2 4 146
4 7 75
3 5 252

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

Key Value Number
4 0 75
2 1 146
3 2 252
1 5 505

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

Key 1 2 3 4
Value 5 6 2 5

ArrayB

Index 0 1 2 3 4 5 6
Value 0 0 1 0 0 2 1

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

Index 0 1 2 3 4 5 6
Value 0 0 1 1 1 3 4

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

Key 3 1 4 2
Value 2 5 5 6

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

Key 1 2 3 4
Value 505 146 252 75

Digits Array after Sorting which is ArrayC

Key 3 1 4 2
Value 2 5 5 6

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

Key 3 1 4 2
Value 252 505 75 146
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;
	}
    }
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Mostafa saeed
Software Developer Premium methods
Egypt Egypt
Student at Faculty of computer and information sciences at Ainshams University,I'm a programmer from three years ago working with
 
Programming languages :
Intel 8086 Assembly,C,C++,C#,VB,Visual prolog.
 
Web development languages and technologies:
ASP.NET , PHP.
 
Database engines:
Oracle,SQL Server and MySQL.

Comments and Discussions

 
QuestionHow to use the code in sorting strings Pinmembergamer11273-Sep-09 22:33 
GeneralA better one Pinmembertamash_ionut10-Jan-09 6:58 
GeneralRe: A better one Pinmemberafterburn2-Mar-09 17:45 
GeneralComplexity PinmemberGeorgi Atanasov10-Jan-09 5:23 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140814.1 | Last Updated 28 Feb 2009
Article Copyright 2009 by Mostafa saeed
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid