Question

Generate a random list NUMBERS of size 100.

Sort NUMBERS using QUICKSORT until the sublist has size 15 or less; then use INSERTIONSORT on the sublist.

Answer 1

Here is the required code:

#include<iostream>
using namespace std;
template<class t>
class sorting
{
public:
   int SIZE, a[100];
   void getdata();
   void isort();
   void qsort(int[], int, int);
   int partition(int[], int , int);
   void display();
};
template<class t>
void sorting<t>::getdata()
{
   cout << "\nEnter the size of an array:";
   cin >> SIZE;
   cout << "Randomly generated elements of the array: ";
   for (int i = 1;i <= SIZE;i++)
{a[i] = (rand()%100)+1;       cout<<a[i]<< " ";}
}
template<class t>
void sorting<t>::display()
{
   cout << "\nSorted Array: ";
   for (int i = 1;i <= SIZE;i++)
       cout << a[i] << " ";
}
template<class t>
void sorting<t>::msort(int A[], int p, int r)
{
   int q;
   if (p < r)
   {
       q = (p + r) / 2;
       msort(A, p, q);
       msort(A, q + 1, r);
       merge(A, p, q, r);
   }
}
template<class t>
void sorting<t>::merge(int A[], int p, int q, int r)
{
   int n1, n2, i, j;
   n1 = q - p + 1;
   n2 = r - q;
   int L[100];
   int R[100];
   for ( i = 1;i <= n1;i++)
       L[i] = A[p+i-1];
   for ( j = 1;j <= n2;j++)
       R[j] = A[q+j];
   L[n1+1] = 32767;
   R[n2+1] = 32767;
   i = j = 1;
   for (int k = p;k <= r;k++)
   {
       if (L[i] <= R[j])
       {
           A[k] = L[i];
           i = i + 1;
       }
       else
       {
           A[k] = R[j];
           j = j + 1;
       }
   }
}
template<class t>
void sorting<t>::qsort(int A[], int p, int r)
{
   int q;
   if (p < r)
   {
       q =   partition(A, p, r);
       qsort(A, p, q - 1);
       qsort(A, q + 1, r);
   }
}
template<class t>
int sorting<t>::partition(int A[], int p, int r)
{
   int x, i, j, temp;
   x = A[r];
   i = p - 1;
   for (j = p;j <= r - 1;j++)
   {
       if (A[j] <= x)
       {
           i = i + 1;
           temp = a[i];
           a[i] = a[j];
           a[j] = temp;
       }
   }
   temp = a[i+1];
   a[i+1] = a[r];
   a[r] = temp;
   return i + 1;
}

void sorting::isort()
{
   int i, j, pivot;
   for (i = 1;i < SIZE;i++)
   {
       pivot = a[i];
       j = i - 1;
       while (j >= 0 && a[j] > pivot)
       {
           a[j+1] = a[j];
           j = j - 1;
       }
       a[j+1] = pivot;
   }
}
int main()
{
   sorting<float>s;
   int f;
           cout << "\nQuick Sort\n";
           s.getdata();
           s.qsort(s.a, 1, s.SIZE);
           s.display();
   return 0;
}