Coding in C++ Overview: You are to implement a sorting algorithm using Queues. I
ID: 3708036 • Letter: C
Question
Coding in C++
Overview: You are to implement a sorting algorithm using Queues. In this algorithm you will scan each integer in the array and determine the value of the least significant bit according to this value you wil enQueue it in it's respective Queue, after this you will move up the position of the LSB and repeat the process. You must implement this algorithm in place, meaning that you will not create more arrays to hold your data. 10pts What I mean by this: Given the array Int sort[5]1, 376, 573, 999, 428 ) Pass 1 1, 376, 573, 999, 428 Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 573 376 428 Pass 2 1, 573, 376, 428, 999 Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 428 573 376 Pass 3 1, 428, 376, 573, 999 Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 376 428 573 Result: 1, 376, 428, 573, 999Explanation / Answer
CODE:
#include<iostream.h>
#include<conio.h>
int getMax(int *arr, int n)
{
int mx = *(arr+0);
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = *(arr+i);
return mx;
}
void countSort(int *arr, int n, int exp)
{
int queue[100]; // output array
int i, count[10] = {0};
for (i = 0; i < n; i++)
count[ (*(arr+i)/exp)%10 ]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--)
{
queue[count[ (*(arr+i)/exp)%10 ] - 1] = *(arr+i);
count[ (*(arr+i)/exp)%10 ]--;
}
for (i = 0; i < n; i++)
*(arr+i) = queue[i];
}
void sort(int *arr, int n)
{
int m = getMax(arr, n);
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
void print(int *arr, int n)
{
for (int i = 0; i < n; i++)
cout << *(arr+i) << " ";
}
void main()
{
clrscr();
int *arr,n;
cout<<"Enter the number of elements";
cin>>n;
arr = new int[n];
for(int i=0;i<n;i++)
{
cout<<endl<<"Enter a number";
cin>>*(arr+i);
}
sort(arr, n);
cout<<endl<<"SORTED LIST IS :";
print(arr, n);
}