Sorting Revisted (More indepth) Flashcards
What are some mergesort properties?
Based on a recursive divide-and-conquer approach:
- If the list has 0 or 1 elements, done.
- Divide list into two lists of equal or nearly equal size and recursively sort each half.
- Finally, merge the two sorted halves into one sorted list.
Worst-case running time of Θ(n log n)
One of the best external (disk) sorting algorithms.
Works well for linked lists in addition to arrays/vectors
Mergesort analysis
The number of comparisons used by mergesort on an input of size n satisfies a recurrence of the form:
T(n) = T([n/2]) + T([n/2]) + n
By induction, we see that T(n) is Θ(n lg n) for n a power of 2.
Base case: n = 0 or n = 1
Inductive hypothesis: T(n) = n lg n
Then (next inductive case):
T(2n) = 2T(n) + 2n (from recurrence)
= 2n lg n + 2n (substitute hypothesis)
= 2n(lg(2n) − 1) + 2n (note lg 2 = 1)
= 2n lg(2n) (simplify)
Master Theorem for Divide-Conquer Recurrences
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/831/531/a_image_thumb.jpg?1466294577)
What are some quicksort properties?
Quicksort is based on a recursive partitioning about a ‘pivot’:
- Pick any element as the pivot (many options here).
- Partition elements into three groups: less than (possibly equal to) pivot, equal to pivot, and more than (possibly equal to) pivot.
- Run quicksort on first and third partitions until one element.
In practice, a very fast internal sorting algorithm (almost twice as fast as mergesort)
On average good O(n lg n), but worst case input data leads to Ω( n2 ) performance
What are 3 different ways to choose a quicksort pivot?
- Use passive pivot strategy (e.g. fixed position in range)
- Use active pivot strategy (e.g. median-of-three)
- Use random pivot strategy (more likely O(n lg n) performance)
Quicksort recurrence relations and runtime
Best case is when partitioning gives partitions of the same size so cost is either
T(n) = 2T((n − 1)/2) + n for unique elements
or
T(n) = 2T(n/3) + n when duplicates allowed
Both recurrences are O(n lg n)
Worst case is when partitioning gives unbalanced partitions where cost is then
T(n) = T(n − 1) + n
which is O( n2 )
What is beadsort and what is its runtime complexity range?
Sorting algorithm which sorts positive integers by representing them in unary as a sequence of beads on a horizontal lines then uses gravity to sort them with the assistance of vertical rods
The algorithm’s run-time complexity ranges from O(1) to O(S), where S is the sum of the input integers
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/843/798/a_image_thumb.jpg?1466335406)