Sorting (5)
Michael L. Littman
September 10th, 1998
SORTING
Telephone Book Publishing
Data Details
Comparing Keys
Formal Statement [Step 0]
Permutations
Beyond Adjacency
Keys
Sorts of Sorts
Other Applications
INSERTION SORT
Arrays
Swaps
Step 1: Develop Algorithm
Explanation
Step 2: Prove Correctness
Step 3: Efficiency
Measures of Sortedness
Sorting with Small Insertion Indices
An Assortment of Sorts
DIVIDE-AND-CONQUER SORTING
Recurrences for Earlier Sorts
Divide and Conquer
Two Algorithms
Merge Sort
Quicksort
Partitioning In Place
Explanation
Picking A Pivot
Empirical Comparison
A Consortium
SORTING IN LINEAR TIME
A Lower Bound
The Decision Tree
The Bound
Faster Sorts Via Bit Operations
Forward Radix Sort
Discussion
Empirical Results on Random Lists
SPARSE MATRICES
Matrices
Vectors and Matrix-Vector Product
Transposition and Matrix-Matrix Products
Sparse Matrices
Problems
Next:
SORTING
