Searching and Sorting
Overview
A huge amount of computing time is devoted to searches in collections of data. As explained in the first lecture in this part of the course, searches are much more efficient than they otherwise be if the “key”, being searched for, is part of a set that has a total order, and if the collection of elements that is being searched through, to find the key, is sorted in non-decreasing order.
A variety of efficient sorting algorithms are, therefore, presented and analyzed.
Lecture #15: Basic Algorithms for Searching and Sorting
Required Reading
Lecture Presentation
Tutorial #13: More about Binary Search
Lecture #16: Merge Sort
Required Reading
- Lecture Notes:
[ PDF ]
[ Video ]
- Questions for Review: [ PDF ]
Lecture Presentation
Tutorial #14: Merge Sort
Lecture #17: Binary Heaps
Required Reading
Lecture Presentation
Tutorial #15: Implementing an Unbounded Binary Heap
Lecture #18: Applications of Binary Heaps
Required Reading
- Lecture Notes: [ PDF ] [ Video ]
- Questions for Review
Lecture Presentation
Lecture #19: Quick Sort
Required Reading
- Lecture Notes: [ PDF ] [ Video ]
- Questions for Review
