Comparison Algorithms Flashcards
What is the best Big-Oh complexity of insertion sort?
O(n)
What is the worst Big-Oh complexity of insertion sort?
O(n^2)
Is insertion in-place?
Insertion sort is in-place.
Best time to use insertion sort?
When there is a small number of elements.
Is insertion sort stable?
Yes
What does it mean for a comparison algorithm to be stable?
The order of equal elements in the original sequence is preserved in the sorted sequence.
How does insertion sort work?
- The array is split into a sorted and unsorted section.
- We iterate through the unsorted part and handle each element
- We check whether the element is smaller than the first rightmost element of the sorted section.
- If smaller then we swap them, this repeats until the end of the sorted section or there is no swap (this is when correct position for element is found)
Is merge sort , divide and conquer based?
Yes
What is the merge sort Big-Oh complexity?
O(nlogn)
How does merge sort work?`
- The algorithm keeps splitting the array using the midpoint, until 1 element ‘arrays’
- The units are compared and sorted upon comparison (first iteration we compare 1 element vs 1, second 2 element vs 2)
- Repeat until the last comparison is on the 2 halves of the array
What is the complexity of the procedure of MERGE (no merge sort)
O(n), as we iterate through 2 sections of array, which is at worst length of array
What is the memory requirement of MERGE?
O(n), as we copy split sections into left and right arrays.
Is in-place implementation of MERGE (and hence merge-sort) possible?
Yes, but stability is lost.
Is merge-sort in place?
No
Some possible improvements for merge sort?
- iterative implementation
- use insertion-sort on small sections of array
What is the best Big-Oh complexity of quicksort?
O(nlogn)
What is the worst Big-Oh complexity of quicksort?
O(n^2)
How does quicksort operate?
- we split the array into smaller and smaller units, until atomic units, but one part contains smaller elements, while the other bigger. We split based on the pivot, which can be picked in a variety of ways.
- we merge 2 halves, one contains smaller items , other bigger, natrually sorted
- we build up a sorted sequence
Is quicksort in place?
Yes
Is quicksort stable?
No
What provides the best quicksort performance?
- choosing median as the pivot
Which algorithm is quicksort similar to?
Merge Sort
How does quicksort differ from merge sort?
- Quicksort splits based on the pivot. One section has smaller, other bigger. Merge sort splits in half.
- Merge compares upon combining 2 sections. Quicksort just combines the 2 sections, as one is greater, other smaller.
- Quicksort is in place, merge not.
Quicksort schemes…
- choose middle
- choose median of three
- randon choice
- choose last
Possible improvments?
- set a cut-off to insertion sort
- tail recursion optimisation
- iterative implementation
- 3 way quicksort
What data structure is heap sort based on?
A heap (min or max one)
What is the complexity of heap sort?
O(nlogn) at all times
How does heap sort work?
- we make the array into a min-heap structure
- we extract max and place it at the end recursively, until end of structure is reached , upon removal we have to fix the min-heap by running a heapify function on the array
What is a heap data structure?
A nearly completed binary tree, where parent is either greater or smaller then child, depending on whether is a min heap or a max heap. Root is therefore the min/max.
What is the space complexity of heap sort?
O(1)
Is heap sort stable?
No
Is heap sort normally iterative?
Yes
Formula for left child of a node in array implementation of heap data structure?
index * 2 +1
Formula for right child of a node in array implementation of heap data structure?
index * 2 + 2
Can a new level be started on a heap data strcutre without previous one being complete?
No
What is min/max - heapify?
A function, which restores the heap property.
