Question

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;

              };

Answer 1

IF YOU HAVE ANY DOUBTS COMMENT BELOW

PLZZZ RATE THUMBSUP

ANS:

CODE:

// Radix Sort

#include<iostream>

using namespace std;

// function to get max value

int getMaximum(int array[], int n)

{

int max = array[0];

for (int i = 1; i < n; i++)

if (array[i] > max)

max = array[i];

return max;

}

// function to get min value

int getMinimum(int array[], int n)

{

int mn = array[0];

for (int i = 1; i < n; i++)

if (array[i] <mn)

mn= array[i];

return mn;

}

//counting sort

void counterSort(int array[], int n, int expo)

{

int out[100]; // out max

int i, count[10] = {0};

// Store count of occurrences in count[]

for (i = 0; i < n; i++)

count[ (array[i]/expo)%10 ]++;

// Change count[i] so that count[i] now contains actual

// position of this digit in out[]

for (i = 1; i < 10; i++)

count[i] += count[i - 1];

// construct the out max

for (i = n - 1; i >= 0; i--)

{

out[count[ (array[i]/expo)%10 ] - 1] = array[i];

count[ (array[i]/expo)%10 ]--;

}

for (i = 0; i < n; i++)

array[i] = out[i];

}

void counterSortDesc(int array[], int n, int expo)

{

int out[100]; // out max

int i, count[10] = {0};

// Store count of occurrences in count[]

for (i = 0; i < n; i++)

count[ (array[i]/expo)%10 ]++;

for (i = 10; i >=1; i--)

count[i] += count[i - 1];

// construct out max

for (i = 0; i >= n-1; i++)

{

out[count[ (array[i]/expo)%10 ] - 1] = array[i];

count[ (array[i]/expo)%10 ]++;

}

// Copy the out max to array[], so that array[] now

// contains sorted numbers according to current digit

for (i = 0; i < n; i++)

array[i] = out[i];

}

// Radix Sort function

void radixsort(int array[], int n)

{

// get maximum number

int m = getMaximum(array, n);

for (int expo = 1; m/expo > 0; expo *= 10)

counterSort(array, n, expo);

}

void radixsortDesc(int array[], int n)

{

// get minimum number

int m = getMinimum(array, n);

for (int expo = 1; m/expo > 0; expo *= 10)

counterSortDesc(array, n, expo);

}

// print an max

void print(int array[], int n)

{ cout<<"\n";

for (int i = 0; i < n; i++)

cout << array[i] << " ";

}

// Main function

int main()

{

int array[] = {185, 25, 35, 90, 904, 34, 2, 66};

int n = sizeof(array)/sizeof(array[0]);

radixsort(array , n);

print(array, n);

radixsortDesc(array,n);

print(array,n);

return 0;

}

PLZZZZZZZZ RATE THUMBSUP

Output C3 BIN TC 35 66 90 185 904 35 66 90 185 904 Activate Wi Go to PC setting

THANKS