Sorting Algorithms, 4th edition 1. Fundamentals 1.1 Programming Model 1.2 Data Abstraction 1.3 Stacks and Queues 1.4 Analysis of Algorithms 1.5 Case Study: Union-Find 2. Sorting 2.1 Elementary Sorts 2.2 Mergesort 2.3 Quicksort 2.4 Priority Queues 2.5 Sorting Applications 3. Searching 3.1 Symbol Tables 3.2 Binary Search Trees 3.3 Balanced Search Trees 3.4 Hash Tables 3.5 Searching Applications 4. Graphs 4.1 Undirected Graphs 4.2 Directed Graphs 4.3 Minimum Spanning Trees 4.4 Shortest Paths 5. Strings 5.1 String Sorts 5.2 Tries 5.3 Substring Search 5.4 Regular Expressions 5.5 Data Compression 6. Context 6.1 Event-Driven Simulation 6.2 B-trees 6.3 Suffix Arrays 6.4 Maxflow 6.5 Reductions 6.6 Intractability Related Booksites Web Resources FAQ Data Code Errata Lectures Cheatsheet References Online Course Programming Assignments 2. Sorting Overview. Sorting is the process of rearranging a sequence of objects so as to put them in some logical order. Sorting plays a major role in commercial data processing and in modern scientific computing. Applications abound in transaction processing, combinatorial optimization, astrophysics, molecular dynamics, linguistics, genomics, weather prediction, and many other fields. In this chapter, we consider several classical sorting methods and an efficient implementation of a fundamental data type known as the priority queue. We discuss the theoretical basis for comparing sorting algorithms and conclude the chapter with a survey of applications of sorting and priority-queue algorithms. 2.1 Elementary Sorts introduces selection sort, insertion sort, and shellsort. 2.2 Mergesort describes megesort, a sorting algorithm that is guaranteed to run in linearithmic time. 2.3 Quicksort describes quicksort, which is used more widely than any other sorting algorithm. 2.4 Priority Queues introduces the priority queue data type and an efficient implementation using a binary heap. It also introdues heapsort. 2.5 Applications describes applications of sorting, including using alternate orderings, selection, the system sort, and stability. Java programs in this chapter. Below is a list of Java programs in this chapter. Click on the program name to access the Java code; click on the reference number for a brief description; read the textbook for a full discussion. REF PROGRAM DESCRIPTION / JAVADOC 2.1 Insertion.java insertion sort - InsertionX.java insertion sort (optimized) - BinaryInsertion.java binary insertion sort 2.2 Selection.java selection sort 2.3 Shell.java shellsort 2.4 Merge.java top-down mergesort - MergeBU.java bottom-up mergesort - MergeX.java optimized mergesort - Inversions.java number of inversions 2.5 Quick.java quicksort - Quick3way.java quicksort with 3-way partitioning - QuickX.java optimized 2-way quicksort - QuickBentleyMcIlroy.java optimized 3-way quicksort - TopM.java priority queue client 2.6 MaxPQ.java max heap priority queue - MinPQ.java min heap priority queue - IndexMinPQ.java index min heap priority queue - IndexMaxPQ.java index max heap priority queue - Multiway.java multiway merge 2.7 Heap.java heapsort Sorting demos. Below are some interesting sorting demos. Sorting Algorithm Animations by David Martin. Audibilization and Visualization of Sorting Algorithms by Timo Bingmann. The Sound of Quicksort. Robot visualizations of quicksort and mergesort. Sorting visualizations by Carlo Zapponi, using inversion count as a measure of progress. Last modified on August 26, 2016. Copyright © 2000–2019 Robert Sedgewick and Kevin Wayne. All rights reserved.
