Coding in C++ Overview: You are to implement a sorting algorithm using Queues. I
ID: 3707524 • 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
#include<iostream.h>
#include<conio.h>
// Function to get maximum value in arr[]
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;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
void countSort(int *arr, int n, int exp)
{
int queue[100]; // output array
int i, count[10] = {0};
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (*(arr+i)/exp)%10 ]++;
// Change count[i] so that count[i] now contains actual
// position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
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)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
// function to print an array
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);
}