Sorting Efficiency Flashcards
(9 cards)
1
Q
Bubble Sort
A
O(n^2)
if the array is sorted, it is O(n)
In-Place
Stable
2
Q
Selection Sort
A
O(n^2)
In-Place
Unstable
3
Q
Insertion Sort
A
O(n^2) - average and worst case
O(n) - best case
In-Place
Stable
4
Q
Tree Sort
A
O(nlog(n)) - for a balanced tree
O(n) - for a degenerate tree
not in-place
not stable
5
Q
Heap Sort
A
O(nlog(n))
In-place
not stable
6
Q
Pivot sort
A
O(nlog(n))
if the pivot is the smallest/ largest value, it is O(n)
If the array is in order (or reversed), and we choose the smallest/ largest pivot, it is O(n^2)
In-Place
Not Stable
7
Q
Merge Sort
A
O(nlog(n))
Not In-Place
Stable
8
Q
Counting Sort
A
O(n + k)
Whichever (n or k) is bigger
9
Q
Radix sort
A
O(n) average and worst
