Sorts Flashcards
Quicksort Time Complexity
best, avg O(n log n) (orange)
worst O(n^2) (red)
Quicksort Space Complexity
log n (green)
Quick sort calls itself log(n) times. For each recursive call, a stack frame of contsant size is created.
Quicksort - How does it work?
How Does It Work?
Choose a pivot. Reorder the array so that all the values less than the pivot value are before the pivot and all the values greater than the pivot value are after the pivot. Now the pivot is in its final position. Apply the same pattern recursively.
Choice of pivot matters greatly. If the final position is chosen as the pivot, performance will be O(n^2) worst case for already sorted arrays or arrays of identical elements.
Computer architecture favors quicksort because it is a cache-efficient sort. It linearly scans the input and linearly partitions the input, which means you make the most of each cache load before reloading.
Quicksort Features
Features
In practice, 2-3x faster than mergesort and heapsort despite having the same best case and avg case Big O
In place
Not stable
Why is quicksort 2-3x faster than mergesort and heap sort despite having the same Big O time complexity?
Computer archutecture favors quicksort because it is a cache efficient sort. Quicksort processes segments of the array in order. When it loads the first element, the location is loaded into the cache. When it needs to access the next element, that element is likely already in the cache. Other algorithms, like heapsort, jump around the array a lot making them less cache efficient.
Mergesort Natural Variant
Can get best case of O(n) using the “natural” variant which exploits naturally occuring sorted sequences. Rather than starting with sublists of size 1 or 2, split the data into naturally occuring runs
3,4,2,1,7
becomes
3,4 2 1,7
Mergesort Time Complexity
Time Complexity
Best, avg, and worst case: n log n
Mergesort - How Does It Work?
Divides entire dataset into groups of at most two.
Compares each number one at a time, moving the smallest number to left of the pair.
Once all pairs sorted it then compares left most elements of the two leftmost pairs creating a sorted group of four with the smallest numbers on the left and the largest ones on the right.
This process is repeated until there is only one set.
Mergesort Space Complexity
Space Complexity
O(n) worst case
Mergesort Features
Features
Stable (!)
Divide and conquer
What’s the best algorithm for sorting? Questions to ask…
What can you tell me about the data?
Is it already sorted, mostly sorted, or unsorted?
How large are the data sets likely to be?
Are there duplicate key values?
How expensive are key comparisons?
What are the requirements?
Are we optimizing for best-case, worst-case, or average-case performance?
Does the sort need to be stable?
What about the system?
Is the largest data set to be sorted smaller than the available memory?
What is a stable sort?
Preserves the input ordering of elements with equal keys
Selection Sort Time Complexity
Time Complexity
Worst, avg, best case: n^2 (red)
Selection Sort Space Complexity
Space complexity
O(1)
Selection Sort - How Does It Work?
How does it work?
Loop through array. Find the smallest element then swap it with the element in position 0. Repeat the same process to find the next smallest element and swap it with the item in position 1.
At each iteration, you are selecting the next smallest element and moving it into the sorted porition of the array.
Heap Sort - Time Complexity
Time Complexity
Best, avg, worst: n log n (orange)
Insertion Sort - How Does It Work?
Loop through the array beginning at item 1. (item 0 becomes the sorted portion of the array.) At each iteration, insert the current element into sorted position at the front of the array.
(If asked to sort a deck of cards, most people would do it this way.)
