Using C++ Sort an array of 10,000 elements using the quick sort algorithm as fol

Q: Using C++ Sort an array of 10,000 elements using the quick sort algorithm as fol

a) #include #include using namespace std; #define SIZE 10000 /* swap a[i] and a[j] */ void swap(int a[], int i, int j) { int temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } void print(const int arr[]) { for(int i=0;i < SIZE; i++) { cout

ID: 3688313 • Letter: U

Question

Using C++

Sort an array of 10,000 elements using the quick sort algorithm as follows:
a. Sort the array using pivot as the middle element of the array.
b. Sort the array using pivot as the median of the rst, last, and middle elements
of the array.
c. Sort the array using pivot as the middle element of the array. However, when the
size of any sublist reduces to less than 20, sort the sublist using an insertion sort.
d. Sort the array using pivot as the median of the rst, last, and middle elements
of the array. When the size of any sublist reduces to less than 20, sort the sublist
using an insertion sort.

Explanation / Answer

#include <iostream>
#include <iomanip>

using namespace std;

#define SIZE 10000

/* swap a[i] and a[j] */
void swap(int a[], int i, int j)
{
   int temp;
   temp = a[i];
   a[i] = a[j];
   a[j] = temp;
}

void print(const int arr[])
{
   for(int i=0;i < SIZE; i++) {
       cout << setw(3) << arr[i];
   }
   cout << endl;
}

/* sort arr[left]...arr[right] into increasing order */
void qsort(int a[], int left_index, int right_index)
{
int left, right, pivot;
if(left_index >= right_index) return;

left = left_index;
right = right_index;

// pivot selection
pivot = a[(left_index + right_index) /2];

// partition
   while(left <= right) {
       while(a[left] < pivot) left++;
       while(a[right] > pivot) right--;
       if(left <= right) {
           swap(a,left,right);
           left++; right--;
       }
       print(a);
   }

// recursion
qsort(a,left_index,right);
qsort(a,left,right_index);
}

int main()
{
int len,a[SIZE];
cout << "Enter the number of elements :";
cin >> len;
cout << "Enter elements ";
int i;
for(i=0;i<len;i++)
cin >> a[i];

print(a);
qsort(a,0,len-1);
}