Sorting Algorithms Flashcards
Get familiar with sorting algorithms (17 cards)
What is the best and worse case runtime of quick sort
O(N log N) and O(n^2)
How does quick sort work
Pick a pivot and set it in its final place such that all smaller elements are on its left and larger elements are on its right, then repeat on these subsets.
What is the runtime of randomised quicksort
(Always the same) O(n log n)
What is the best and worse case runtime of merge sort
O(n log n) for both
How does merge sort work
Split the list in two then apply merge sort recursively to them, recombine sorted lists back together.
What is the runtime of heapSort
O(n log n) building heap takes O(n)
What is the best and worst case runtime of bubble sort
O(n) and O(n^2)
How does bubble sort work?
Elements are bubbled up, comparing them against the element next to it.
How does heapSort work
From a heap, swap root node with smallest element and then remove last element. Call max-heapify(a,1) to restore the heap
What is a heap
A heap is a tree such that the root is the largest element, recursively applies down.
What is the best and worse case runtime of insertion sort
O(n) and O(n^2)
How does insertion sort work
Iterate through list, take each element and put it in place in a sorted list
What is the best and worse case runtime of selection sort
O(n^2) for both
How does selection sort work
Iterates through the array and puts either the next smallest or largest element in place (start or end of list)
How do you prove correctness of an algorithm
- Create loop invariant
- Show that it works for initialisation
- Show that it works in maintenance (start/end of each loop)
- Show that it works on termination
How do you calculate the probability of two elements being compared in a quick sort
2/(j - i + 1)
Where j is the position in the sorted list of the larger element and i the same for the smaller element
What is a recurrence equation
An equation for the runtime that depends on the state of n
