Java Reference
In-Depth Information
Chapter 9
Advanced Sorting
In this chapter, we will explain the following:
siftDown
•
What a heap is and how to perform heapsort using
siftUp
•
How to build a heap using
•
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
k
th 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.
9.1 Heapsort
Heapsort
is a method of sorting that
interprets
the elements in an array as an almost complete binary tree. Consider
the following array, which is to be sorted in ascending order:
num
37
25
43
65
48
84
73
18
79
56
69
32
1
2
3
4
5
6
7
8
9
10
11
12
We can think of this array as an almost complete binary tree with 12 nodes, as shown in Figure
9-1
.
Search WWH ::
Custom Search