7-9 Flashcards
What is a simple way to improve mergesort?
Make it drop down to insertion sort when approximately 40 items are left in the array.
How does quicksort work?
take the first value (or middle value out of first, middle and last, or random value in the array). We then use this value to seperate the array into two sub arrays, the left has all smaller values and the right has all larger values. This could be done recursively until the array length is 1 or less and then combined.
Analyse quicksort.
Has big theta of n log n, this occurs when there are log n splits of the array(always perfect split). In the worst case it has a time complexity of n^2, which is a completely unbalanced split. Any kind of proportional split e.g average 90% is still good.
How can we improve quicksort?
Pick a small size and let the quicksort subarrays be returned without sorting further. Use insertion sort to finish as insertion sort is quick on nearly sorted data.
What is a stable sorting algorithm?
One in which equal keys are left in the same relative order.
How do we sort in linear time?
Use a non comparison sort like counting, bucket and radix sort.
What is counting sort?
A linear time non comparison sort which requires the integers to be in a small range, number of data items roughly the same as size of largest key.
It works by working out for each input key how many keys are smaller, it can then place the key in the that number+1 spot.
It is stable.
What is bucket sort?
A non comparison sort which has three phases:
- Distribute keys into buckets (based on characteristics like first letter or comparison to pre-determined values). O(n)
- Sort the buckets(keys must be uniformly distributed), using a comparison sort function.
- join the buckets. O(n).
What is radix sort?
Sort by creating buckets using the rightmost digit only first and sorting that, then recombine all buckets and repeat for second to rightmost digit etc. The digit sort must be stable to work. If the keys don’t all have the same number of digits add leading 0s
