Quick sort is an exchange sort developed by C. A. R. Hoare in 1962. Hoares original algorithm selected the pivot key as the first element in the list. In 1969, R. C. Singleton improved the sort by selecting the pivot key as the median value, of three elements: left, right, and an element in the middle of the list. Quick sort is most efficient when the pivots location is the middle of the array. Once the median value is determined, it is exchanged with the left element.

Write addition function that determine the median value and exchange it with the first. Use this function in the existing program below. Test your complete program having function median, and show the complete program with the "median" function integrated. please include comments throughout the whole code.

/* QUICK SORT - ORIGINAL Written by: Date: */ #include  #define MAX_ARY_SIZE 12 // Prototype Declarations void quickSort(int sortData[], int left, int right); void quickInsertion(int sortData[], int first, int last); // MAIN int main(void) { int i; int ary[MAX_ARY_SIZE] = {89, 72, 3, 15, 21, 57, 61, 44, 19, 98, 5, 77};// , 39, 59, 61}; printf("Unsorted array: "); for ( i = 0; i < MAX_ARY_SIZE; i++) { printf("Pl enter the values-->"); scanf("%4d", &ary[i]); } // printf("%3d", ary[ i ]) ; quickSort(ary, 0, MAX_ARY_SIZE - 1); printf(" Sorted array: "); for ( i = 0; i < MAX_ARY_SIZE; i++) printf("%3d", ary[i]); printf(" "); return 0; } // main // =================== quickSort ==================== void quickSort(int sortData[], int left, int right) { #define MIN_SIZE 3 // set to 3 for testing // Local Definitions int sortLeft; int sortRight; int pivot; int hold; // Statements if ((right - left) > MIN_SIZE) { pivot = sortData[left]; sortLeft = left + 1; sortRight = right; while (sortLeft <= sortRight) { // Find key on left that belongs on right while (sortData[sortLeft] < pivot) sortLeft = sortLeft + 1; // Find key on right that belongs on left while (sortData[sortRight] >= pivot) sortRight = sortRight - 1; if (sortLeft <= sortRight) { hold = sortData[sortLeft]; sortData[sortLeft] = sortData[sortRight]; sortData[sortRight] = hold; sortLeft = sortLeft + 1; sortRight = sortRight - 1; } // if } // while // Prepare for next pass sortData[left] = sortData[sortLeft - 1]; sortData[sortLeft - 1] = pivot; if (left < sortRight) quickSort(sortData, left, sortRight - 1); if (sortLeft < right) quickSort(sortData, sortLeft, right); } // if right else  quickInsertion(sortData, left, right); return; } // quickSort // =================== Program 12-7 quickInsertion ==================== void quickInsertion(int sortdata[], int first, int last) { // Local Definitions int hold; int walker; // Statements for (int current = first + 1; current <= last; current++) { hold = sortdata[current]; for (walker = current - 1; walker >= first && hold < sortdata[walker]; walker--) { sortdata[walker + 1] = sortdata[walker]; } sortdata[walker + 1] = hold; } // for return; } // quickInsertion