Explore BrainMass

Quick sort

Suppy an array containing integers 1 through 12 such that a quicksort algorithm using median of three will recurse to 6 levels, counting the top level as 0; showing that even with median of three, quicksort has worst case performance of O(n^2).

The pivot is then moved to the end and the partition is performed, then after the partition, the pivot moves to its rightful place.

Median of three: on the range [p, r], choosing as the split value the median of vals[p], vals[r], and vals[(p+r)/2].

Solution Preview

Quick sort is recursive divide-and-conquer technique.
In each round of quick sort:
1. choose a pivot amongst the unsorted values (say, the first value)
2. move all values less than the pivot before the pivot
3. move all values greater than the pivot after the pivot
4. pivot is now in correct place in sorted order ...

Solution Summary

Quick sort is demonstrated.