Sorting Flashcards
Insertion Best Case
O(n)
Insertion Avg Case
O(n^2)
Insertion Worst Case
O(n^2)
Selection Best Case
O(n^2)
Selection Avg Case
O(n^2)
Selection Worst Case
O(n^2)
Heap Best Case
O(n log n)
Heap Avg Case
O(n log n)
Heap Worst Case
O(n log n)
Merge Best Case
O(n log n)
Merge Avg Case
O(n log n)
Merge Worst Case
O(n log n)
Quick Best Case
O(n log n)
Quick Avg Case
O(n log n)
Quick Worst Case
O(n^2)
Sorts that are easy on Linked List
Insertion, Selection, Merge, Quick
Sorts difficult for Linked List
Heap Sort
Sorts great for arrays
Insertion, Selection, Quick
Sorts bad for arrays
Merge Sort, you need additional array
Stability
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.
Stable Sorts
Insertion, Bubble, Merge [IBM] ** Selection can be made stable easily, Linked List version of Quick Sort as well
What is the BEST that a comparison based sorting algorithm can run?
O(n log n). Because making 2 way decisions take too long.
Stable
Items with equal keys come out in same order they went in
Non Stable sorts
Heap Sort ** can still be made stable with secondary key
Bucket Best Case
O(n + k) k: number of buckets
Bucket Avg Case
O(n + k) k: number of buckets
Bucket Worst Case
O(n^2)
Radix Best
O(nk)
Radix Average
O(nk)
Radix Worst
O(nk)
