<style> .reveal { font-size: 30px; } .reveal strong { color: #E12315; } .reveal h1 { font-size: 55px; } </style> # Notes for CLRS (Part II - Sorting and Order Statistics) ### Cory Chu (2022) [[Return to Table of Content]](https://hackmd.io/@c0rychu/dsa/) **Reference**: Introduction to Algorithms by Thomas H. **C**ormen, Charles E. **L**eiserson, Ronald L. **R**ivest, and Clifford **S**tein. --- ## Part II - Sorting and Order Statistics - Introduction ---- ### The structure of the data - In practice, the numbers to be sorted are usually part of a collection of data called a **record**. Each record contains a **key**, which is the value to be sorted. The remainder of the record consists of **satellite data**, which are usually carried around with the key. - When a sorting algorithm permutes the keys, it must permute the satellite data as well. - If each record includes a large amount of satellite data, it often pays to permute an array of pointers to the records rather than the records themselves in order to minimize data movement. - These implementation details distinguish an algorithm from a full-blown program. - **Here, we only focus on sorting keys.** ---- ### Sorting Algorithms (Comparison sort) - Insertion sort (Ch2) - 👎 $\Theta(n^2)$ time in the worst case - 👍 Sort **in-place**, fast for small $n$ - Merge sort (Ch2) - $\Theta(n \lg n)$ time, not in-place - Heapsort (Ch6) - 👍 **$O(n \lg n)$** time, sort **in-place** - It uses an important data structure, called a **heap**, which can also implement a priority queue. - Quicksort (Ch7) - $\Theta(n^2)$ time in the worst case - However, its **expected running time is $\Theta(n \lg n)$**, and it generally **outperforms heapsort in practice**. - Sort **in-place** - Small constant factor, popular for large arrays. ---- ### Sorting Algorithms (Comparison sort) - Insertion sort, Merge sort, Heapsort, and Quicksort are all comparison sorts: they **determine the sorted order of an input array by comparing elements**. - Ch8: Proof that the **Lower bound** on the worst-case running time of any comparison sort is **$\Omega(n \lg n)$** - So, Heapsort and Merge sort are asymptotically optimal comparison sorts. - By means other than comparing elements, we can beat this $\Omega(n \lg n)$ lower bound, e.g., Counting sort, Radix sort, Bucket sort... ---- ### Sorting Algorithms (Running Time) | Algorithm | Worst-case | Avg.-case/expected | | -------------- | ----------------- | ------------------- | | Insertion sort | $\Theta(n^2)$ | $\Theta(n^2)$ | | Merge sort | $\Theta(n \lg n)$ | $\Theta(n \lg n)$ | | Heapsort | $O(n \lg n)$ | --- | | Quicksort | $\Theta(n^2)$ | $\Theta(n \lg n)$ (expected)| | Counting sort | $\Theta(k+n)$ | $\Theta(k+n)$ | | Radix sort | $\Theta(d(k+n))$ | $\Theta(d(k+n))$ | | Bucket sort | $\Theta(n^2)$ | $\Theta(n)$ (avg.-case) | --- ## Ch6 - Heapsort --- ## Ch7 - Quicksort --- ## Ch8 - Sorting in Linear Time --- ## Ch9 - Medians and Order Statistics **Skip**