write the code in c++ and paste the output. Overview: You are to implement a sor

Question

write the code in c++ and paste the output.

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 will 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

Explanation / Answer

C++ 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];

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)

{

// 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);

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.