Question

in C++, Modify the quicksort algorithm such that it uses the last item as the pivot instead of the 1^st. Also, sort in descending order, instead of ascending order.

NOTE: Do not move the last element into the first element of the array. You must treat the algorithm as if the pivot is actually sitting in the last location of the array.

After it has been sorted in descending order, go through all the items in the array and make sure that they all have the same number of digits as the largest element in the array by adding additional 5’s to the end of the numbers. For example, given the following sorted array:

324, 46, 6

After adding the additional digits, the array will look like the following:

324, 465, 655

Then sort the new array using radix sort in descending order.

Read the original data elements from a file. The elements in the file will be separated by some kind of white space, just like before. The number of elements will not exceed 10.

Answer 1

Program

#include<iostream>
#include<fstream>
#include<math.h>

using namespace std;

//Function partition used to partition the array
int partition(int a[], int l,int r)
{
//set last element as pivot
   int t = a[r];
   int i = l-1;
   int j = r;

   while(1)
   {
   while(t>a[--j]);

       while(t<a[++i]);

       if(i>=j) break;

       //interchange
       swap(a[i],a[j]);
   }

   if(i==j) i++;

   swap(a[r], a[i]);

   return i;
}

//Function to sort the array using quick sort in descending order
void quicksort(int a[], int l, int r)
{
   if(l>=r) return;

   int i=partition(a,l,r);

   quicksort(a,l,i-1);

   quicksort(a,i+1,r);
}

//Function to print the array
void print(int arr[], int n)
{
for(int i=0; i<n; i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}

//Function to modify the array and return max number of digit
int modifyArray(int a[], int n)
{
int max = 0;

for(int i=0; i<n; i++)
{
int t = a[i];
int count = 0;
while(t!=0)
{
count++;
t=t/10;
}
if(count>max) max = count;
}

int m = pow(10, max-1);

for(int i=0; i<n; i++)
{
while(a[i]<m)
{
a[i] = 10*a[i] + 5;
}
}
return max;
}

//Function to sort the array using radix sort in descending order
void radixSort(int a[], int n, int num)
{
int b[10][5], c[10];
int i, div,large,l;
div=1;

for(int passes=0; passes<num; passes++)
{
for(int k=0;k<10;k++)
c[k]=0;
for(i=0;i<n;i++)
{
l=(a[i]/div)%10;
b[l][c[l]++]=a[i];
}
i=0;
for(int k=9;k>=0;k--)
{
for(int j=0;j<c[k];j++)
a[i++]=b[k][j];
}
div*=10;
}
}

//main function
int main()
{
ifstream ifs;

//open the file
ifs.open("num.txt");

int arr[10], n;

//read the numbers fro the file
for(n=0; ifs>>arr[n]; n++);

//print the array
cout<<"Original array:"<<endl;
print(arr, n);

//quicksort in descending order
quicksort(arr,0,n-1);

cout<<"After quick sort:"<<endl;
//print the array
print(arr, n);

//modify the array
int num = modifyArray(arr, n);

cout<<"After modification:"<<endl;
//print the array
print(arr, n);

//radixsort in descending order
radixSort(arr, n, num);

cout<<"After radix sort:"<<endl;
//print the array
print(arr, n);

return 0;
}

Output:

Original array:
25 137 52 26 234 92 43 399 37 59
After quick sort:
399 234 137 92 59 52 43 37 26 25
After modification:
399 234 137 925 595 525 435 375 265 255
After radix sort:
925 595 525 435 399 375 265 255 234 137