Question

5- How could you design a Three-Pass-Radix sort algorithm to sort the following group of integ containing three digits: 666,6,66,323, 13, 333, 111, 23, 100, 102

؟

Answer 1

-> 666, 6,66,323,13,333, 111,23,100, 102 o to 9. Step 1: Define 10 queues U In 7 8 6 9 4 2 step 2: Based on least significant bit insert in queue. 6 66,6,66 23 100,102 Illi 13,333, 323 23 66 . 333 13 323 666 100 102 - 8 8 I 9 3 4 s 6 2 - o in Group all numbers from o to 9 >) same ordes inserted 100,!!!, 102, 323,13,333,23, 666,66, 66 step3 Based on Ten's place digit insert in queue. 670 66 666 13 102 2.3 323 333 100 M 4. Ib 2 3 0 - numbers from Group all o to 9 in same order inserted = 100,102,6,111, 13, 323, 23, 335, 666, 66

step 4 Based hundred's place insert in queue. 100 ,102,006 102,006,!!!,013 !!!,013,323,023, 333, 666,066 66 23 13 6 102 3 33 323 100 5 6 7 3 4 2 666 9. Grouping all numbers from oto 9 in same order inserted. 6,13,23, 66, 100, 102, 111, 323,333, 666,

///defining a function to which i pass the array list and size of n

void radixsort(int list[], int n) {
//get a max number for which the loop has to run i.e for 2 digit number we need to run 2 times i.e upto tens place   

int m = getMax(list, n);

int exp;

//for every digit place i am calling function count sort
for (exp = 1; m / exp > 0; exp *= 10)
countSort(list, n, exp);
}

//getting the maxvalue from array

int getMax(int list[], int n) {
int mx = list[0];
int i;
for (i = 1; i < n; i++)
if (list[i] > mx)
mx = list[i];
return mx;
}

//function to insert the elements in queue based on digit --i.e units digit and tens place

void countSort(int list[], int n, int exp) {
//defining the output queue and of size n

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

//loop to count the number of elements in the particular queue place ..i.e at queue 1 how many elements are //inserted

for (i = 0; i < n; i++)
count[(list[i] / exp) % 10]++;

for (i = 1; i < 10; i++)
count[i] += count[i - 1];

///inserting in the queue based on digits place in the queue output   

for (i = n - 1; i >= 0; i--) {
output[count[(list[i] / exp) % 10] - 1] = list[i];
count[(list[i] / exp) % 10]--;
}

//coping the elements  and modifing the queue--list

for (i = 0; i < n; i++)
list[i] = output[i];
}

c code:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

int getMax(int list[], int n) {
int mx = list[0];
int i;
for (i = 1; i < n; i++)
if (list[i] > mx)
mx = list[i];
return mx;
}

void countSort(int list[], int n, int exp) {
int output[n];
int i, count[10] = { 0 };

for (i = 0; i < n; i++)
count[(list[i] / exp) % 10]++;

for (i = 1; i < 10; i++)
count[i] += count[i - 1];

for (i = n - 1; i >= 0; i--) {
output[count[(list[i] / exp) % 10] - 1] = list[i];
count[(list[i] / exp) % 10]--;
}

for (i = 0; i < n; i++)
list[i] = output[i];
}

void radixsort(int list[], int n) {
int m = getMax(list, n);

int exp;
for (exp = 1; m / exp > 0; exp *= 10)
countSort(list, n, exp);
}

void print(int list[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d\t", list[i]);
}

int main()
{
   //defining the array list
int list[] = {666,6, 66, 323, 13, 333, 111, 23, 100,102 };
int i, n = sizeof(list) / sizeof(list[0]);

printf("List of numbers before sort: \n");
for(i = 0; i<10; i++)
printf("%d\t", list[i] );
//calling the function
radixsort(list, n);

printf("\n\nList of numbers after sort: \n");
print(list, n);
printf("\n\n");
return 0;
}

List of numbers before sort: 666 6 66 323 13 333 111 23 100 182 List of numbers after sort: 13 23 66 100 102 111 323 333 666 Process exited after 0.84421 seconds with return value 8 Press any key to continue