Radix sort C++ Come up with an unsorted array of numbers (integer array). Sort the numbers in ascending order and descending order and display them using radix sort. First sort in ascending, then reset the array to its original order and finally sort the array again in descending order.

USE THIS STUCTURE

struct nodeQ{

node *front;

node *rear;

};

nodeQ que[10];

enqueue(que[i],data);

EXAMPLE:

Original, unsorted list:

[170, 45, 75, 90, 2, 802, 24, 66]

1^ST PASS:

The integers are enqueued into an array of ten separate queues based on their digits from right to left.

0: 170, 090

1: none

2: 002, 802

3: none

4: 024

5: 045, 075

6: 066

7: none

8: none

9: none

The queues are dequeued back into the array of integers, in increasing order.

[170, 090, 002, 802, 024, 045, 075, 066]

2^nd PASS

0: 002, 802

1: none

2: 024

3: none

4: 045

5: none

6: 066

7: 170, 075

8: none

9: 090

The queues are dequeued back into the array of integers, in increasing order.

[002, 802, 024, 045, 066, 170, 075, 090]

3^rd PASS

Queues:

0: 002, 024, 045, 066, 075, 090

1: 170

2: none

3: none

4: none

5: none

6: none

7: none

8: 802

9: none

The queues are dequeued back into the array of integers, in increasing order.

[002, 024, 045, 066, 075, 090, 170, 802] (sorted)

Algorithm

Find the largest element in the array (MAX)

M=10, N=1 (Used to find the least significant digit, start with the right most digit)

Create a 10 element array of queues.

Continue while there are more significant digits that have to be processed (N<=MAX). For each pass process one of the significant digits

Identify the least significant digits starting from the right most digit using mod and division and place in appropriate queue.

For example: 195 is going to be placed in one of the queues based on LSD

195%10 = 5

5/1=5 1^st least significant digit (M=10, N=1) place in queue 5

195%100=95

95/10=9 2^nd least significant digit (M=100, N=10) Place in queue 9

195%1000=195

195/100=1 3^rd least significant digit (M=1000, N=100) place in queue 1

Dequeue all the queues and Repopulate array

M=M*10, N=N*10 (Process the next least significant digit)

struct node{

int data;

node *next;

};