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.


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.