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 live online training, plus books, videos, and digital content from nearly 200 publishers.