Explore BrainMass

Explore BrainMass

    Quick sort

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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].

    © BrainMass Inc. brainmass.com March 4, 2021, 6:10 pm ad1c9bdddf

    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. The median of three worst case scenarios are determined.