How many calls necessary for quickSort
I was given this question and was hoping someone can let me know if my answer is correct.
How many recursive calls are necessary when quickSort sorts an array of size n if you use median-of-three pivot selection? State any assumptions you make about the value of n.
I say the answer is n because when you use median-of-three isnt that the best case scenario?
How many recursive calls are necessary when quickSort sorts an array of size n if you use median-of-three pivot selection? State any assumptions you make about the value of n.
I say the answer is n because when you use median-of-three isnt that the best case scenario?
The best case scenario occurs when the initial pivot value is the actual median. Median-of-three doesn't guarantee that.
int arr[] = { 3, 7, 8, 2, 5 };Median of three would be arr[2] (since the range is from arr[0] to arr[4], but given the values in the array, the actual median is arr[4] (5).
Of course, when you're sorting you have no idea of what the actual median is, or else there would be no need to sort it in the first place.
Last edited on
Just did a quick google search on what "median of three" actually means:
http://stackoverflow.com/questions/7559608/median-of-three-values-strategy
To paraphrase, take the middle and end elements of an array, sort them, and use the middle element as pivot.
This guarantees that you will never have the worst-case scenario of picking a pivot which contains the lowest or highest value in the array.
I've got no idea of exactly how many recursive calls would be necessary though. I guess since arrays of 3 elements or less will be sorted before you do the quicksort, the number of recursive calls should be 2 less than normal.
Normally:
quicksort(a[], 0, 2) calls quicksort(a[], 0, 0) and quicksort(a[], 2, 2)
Median of three:
quicksort(a[], 0, 2) array is totally sorted with median of three
http://stackoverflow.com/questions/7559608/median-of-three-values-strategy
To paraphrase, take the middle and end elements of an array, sort them, and use the middle element as pivot.
This guarantees that you will never have the worst-case scenario of picking a pivot which contains the lowest or highest value in the array.
I've got no idea of exactly how many recursive calls would be necessary though. I guess since arrays of 3 elements or less will be sorted before you do the quicksort, the number of recursive calls should be 2 less than normal.
Normally:
quicksort(a[], 0, 2) calls quicksort(a[], 0, 0) and quicksort(a[], 2, 2)
Median of three:
quicksort(a[], 0, 2) array is totally sorted with median of three
Topic archived. No new replies allowed.