CODEWITHSUNDEEP
algorithmsortingquicksort
user3118602
user3118602

Reputation: 583

Median of three (mean) in quicksort?

I can't seem to understand how this works despite reading this - median of three values strategy

I understand that in quick sort, I can pick an arbitrary value to be my pivot and start from there. For a median of three quick sort, some online article said to pick the first, last and the middle values in the unsorted array and then pick the value that is the center of these 3 values (e.g 56, 12, 45 -45 will be picked). The example also shows it with 9 values, making it easy to pick the first, last and middle values.

What if the unsorted array is of 8 values only like 34, 66, 57, 45, 20, 98, 92, 41? Is my median value going to be 45 given that the first, last and middle values are 34, 45, 41 respectively?

Thanks.

Upvotes: 1

Views: 2110

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76336

Is my median value going to be 45 given that the first, last and middle values are 34, 45, 41 respectively?

It will be 41, since that is the median of these three numbers.

In general, the method is picking three numbers according to some scheme, and taking the median as the current pivot.

If choosing the median of the first, middle, and last, there are some technicalities to consider, like an even sized array (as in your example), arrays of size less than three, etc. Any reasonable choice you do there will be fine.

Upvotes: 1

Related Questions