Quick sort is an exchange sort developed by C. A. R. Hoare in 1962. Hoare’s orig

Question

Quick sort is an exchange sort developed by C. A. R. Hoare in 1962. Hoare’s 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 pivot’s 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 of “quick_sorting_original” available in files tab at CANVAS. Test your complete program having function “median”, submit program in .C format.

/* QUICK SORT - ORIGINAL Written by: Date: */ #include <stdio.h> #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
Quick sort is an exchange sort developed by C. A. R. Hoare in 1962. Hoare’s 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 pivot’s 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 of “quick_sorting_original” available in files tab at CANVAS. Test your complete program having function “median”, submit program in .C format.

/* QUICK SORT - ORIGINAL Written by: Date: */ #include <stdio.h> #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
Quick sort is an exchange sort developed by C. A. R. Hoare in 1962. Hoare’s 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 pivot’s 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 of “quick_sorting_original” available in files tab at CANVAS. Test your complete program having function “median”, submit program in .C format.

/* QUICK SORT - ORIGINAL Written by: Date: */ #include <stdio.h> #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 /* QUICK SORT - ORIGINAL Written by: Date: */ #include <stdio.h> #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 // =================== 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

Explanation / Answer

The median function should basically compare three values first,left and and the element in middle of the list.since this comparison includes only three(constant) values, the function complexity is simplye O(1).

i am writing the function definition here. this function has to be called in the first line of quickSort().

void selectMedian(int sortData[],int left,int right) {

int middle=(left+right)/2; //middle element index

//find the MAX(index value of maximum element) and MIN(index of minimum element) of the three

int MAX=left,MIN=right;

if(sortData[middle]>sortData[MAX]) MAX=middle;

if(sortData[right]>sortData[MAX]) MAX=right;

if(sortData[middle]<sortData[MIN]) MIN=middle;

if(sortData[left]<sortData[MIN]) MIN=left;

int median=0;// index of median element

//the index of median is neither MAX nor MIN

if(left!=MAX && left!=MIN) median=left;

else if(middle!=MAX && middle!=MIN) median=middle;

else median=right;

// if median is not already left then swap it with left

if(median!=left){

int temp=sortData[left];

sortData[left]=sortData[median];

sortData[median]=temp;

}

}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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