13,407,023 members (56,513 online)
alternative version

Stats

56.6K views
22 bookmarked
Posted 10 Jan 2009

, 28 Feb 2009

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.

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:

The Code for the Radix Sorting Methods

```public static int[] Sort(int[] array)
{
}
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];
} ```

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.:) 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;
}
}
}```

Share

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.

You may also be interested in...

 First Prev Next
 How to use the code in sorting strings gamer11273-Sep-09 23:33 gamer1127 3-Sep-09 23:33
 A better one tamash_ionut10-Jan-09 7:58 tamash_ionut 10-Jan-09 7:58
 Re: A better one afterburn2-Mar-09 18:45 afterburn 2-Mar-09 18:45
 Complexity Georgi Atanasov10-Jan-09 6:23 Georgi Atanasov 10-Jan-09 6:23
 Last Visit: 31-Dec-99 19:00     Last Update: 22-Feb-18 23:20 Refresh 1