Overview
Notes:
- Implement sorts & know best case/worst case, average complexity of each:
- no bubble sort - it's terrible - O(n^2), except when n <= 16
- Stability in sorting algorithms ("Is Quicksort stable?")
- Which algorithms can be used on linked lists? Which on arrays? Which on both?
- I wouldn't recommend sorting a linked list, but merge sort is doable.
- Merge Sort For Linked List - GeeksforGeeks (article)
- Visualization of 15 Sorting Algorithms - Youtube (video).
- Implement sorts & know best case/worst case, average complexity of each:
Implement:
- Mergesort: O(n log n) average and worst case
- Quicksort O(n log n) average case
- Selection sort and insertion sort are both O(n^2) average and worst case
- For heapsort, see Heap data structure above
Not required but recommended:
- Sedgewick - Radix Sorts - Coursera (6 videos)
- Radix Sort - Yale (article)
- Radix Sort - Youtube (video)
- Radix Sort, Counting Sort (linear time given constraints) - MIT 6.006 (video)
- Randomization: Matrix Multiply, Quicksort, Freivalds' algorithm - MIT 6.046 (video)
- Sorting in Linear Time - MIT 6.851 (video)
More Sorting Content
- Lecture 15 | Programming Abstractions - Stanford (video)
- Lecture 16 | Programming Abstractions - Stanford (video)
- Algorithms - Sorting - Lecture 2 - Shai Simonson (video)
- Algorithms - Sorting II - Lecture 3 - Shai Simonson (video)
- Mergesort/Quicksort - CSE373 Skiena (video)
- Linear Sorting - CSE373 Skiena (video)