CHAPTER 9
Advanced Sorting
In this chapter, we will explain the following:
- What a heap is and how to perform heapsort using siftDown
- How to build a heap using siftUp
- How to analyze the performance of heapsort
- How a heap can be used to implement a priority queue
- How to sort a list of items using quicksort
- How to find the kth smallest item in a list
- How to sort a list of items using Shell (diminishing increment) sort
In Chapter 1, we discussed two simple methods (selection and insertion sort) for sorting a list of items. In this chapter, we take a detailed look at some faster methods—heapsort, quicksort, and Shell (diminishing increment) sort. ...
Get Advanced Topics in Java: Core Concepts in Data Structures now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
