Sorting Algos Flashcards
Explain how Selection Sort works
- Keep track of current item and current minimum
- Start at first index and interate through the array, keeping track of the minimum item’s index
- After iterating through the array, if the current minimum is less than the current index, swap the items
- Continue for every index until array is sorted
Explain how Insertion Sort works
- Start at the first index
- Compare current item with item to the left
- if it is greater, keep as it is
- if it is less than, swap with left item until the item on the left is smaller
- Continue for entire array
Explain how Merge Sort works
- Recursively split the array in two until you are left with pairs of individual indexes
- Take each pair of sub-arrays and MERGE them into another array in sorted order
- Continue merging pairs until the entire array is sorted
Explain how Quick Sort works
Pivot conditions:
- Correct position in final array
- Items to the left are smaller
- Items to the right are larger
ItemOnLeft - Starting from the left of the array, the first item that is larger than the pivot
ItemOnRight - Starting from right of the array, the first item that is smaller than the pivot
- Choose a pivot in the array and swap it to the back
- Find IOR and IOL and swap them
- If the index of IOL > index of IOR, stop
- Swap pivot (whic is at the back) with IOL
- Recursively sort the LHS and RHS
Explain how Heap Sort works
- Initialize an empty Heap H
- Insert all the items in the array into H
- deleteMax and add to array starting from A[n-1] until A[0]
Explain how Radix Sort works
R= Radix (base system) d = # of digits
- Start at either at most or least significant digit
- For each digit, add to count or buckets and sort back into the array by your current digit
- Repeat d (or m?) times
What is the best case complexity for Selection sort?
Theta(n^2)
What is the worst case complexity for Selection sort?
Theta(n^2)
What is the average case complexity for Selection sort?
Theta(n^2)
What is the best case complexity for Insertion sort?
Theta(n)
What is the worst case complexity for Insertion sort?
Theta(n^2)
What is the average case complexity for Insertion sort?
Theta(n^2)
What is the best case complexity for Merge sort?
Theta(nlog(n))
What is the worst case complexity for Merge sort?
Theta(nlog(n))
What is the average case complexity for Merge sort?
Theta(nlog(n))
Why are the complexities for Selection Sort the same?
Regardless of how much the array is sorted at the beginning, we will always have to iterate through n, n-1, n-2, …. 2, 1 indicies. This is n^2 time
Why are the complexities for Insertion sort different?
If the array is already sorted, the number of swaps needed is 0, meaning we only have to do n comparisons and no swaps.
Why are the complexities for Merge Sort the same?
At every recursive level we have Theta(n) operations. The number of levels is log(n). Regardless of how sorted the array is at the beginning, this is the case
What is the best case complexity for Quick sort?
Theta(nlog(n))
What is the worst case complexity for Quick sort?
Theta(n^2)
What is the average case complexity for Quick sort?
Theta(nlog(n))
Why is there a difference between the worst and best case complexity for Quick Sort?
It all depends on how you pick your partition. The best case will have a perfectly balanced partition while the worst case will have every partition include only one element.
What is the average complexity for LSD Radix Sort?
Theta(m(n+R))
Where m = # of digits
R = Radix (base)
Can Radix sort to better than comparison based sorting?
Yes, Radix can get to o(nlog(n))
What is the complexity of Heap Sort
Heap sort in all cases is Theta(nlog(n))
What is randomized Quick Sort?
Pick a random pivot at each step
What is the complexity of Randomized Quick Sort?
Average run time of Theta(n)
Worst-Case expected of Theta(n) as well
What is expected runtime?
For a randomized algorithm, you measure your complexity by “expected” runtime since it is randomized. Thus your worst, best and average runtimes are really “what is the expected runtime give the worst, best or average inputs”
What is the lower bound for comparison-based sorting?
Omega(nlog(n)) - all comparison based sorting takes at least nlog(n) time
Compare the runtime of comparison and non-comparison based sorting
Non-comparison based sorting can achieve o(nlog(n)) depending on the input while the lower bound for comparison-based sorting is Theta(nlog(n))
