O'Reilly logo

Advanced Topics in Java: Core Concepts in Data Structures by Noel Kalicharan

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

CHAPTER 9

image

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. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required