Java Reference
In-Depth Information
In the best case, the pivot divides the array each time into two parts of about the same size.
Let
T(n)
denote the time required for sorting an array of
n
elements using quick sort. Thus,
O
(
n
log
n
) best-case time
recursive quick sort on
partition time
two subarrays
n
2
n
2
T
(
n
)
=
T
¢
≤
+
T
¢
≤
+
n
.
Similar to the merge sort analysis,
T
(
n
)
O
(
n
log
n
).
On the average, the pivot will not divide the array into two parts of the same size or one
empty part each time. Statistically, the sizes of the two parts are very close. Therefore, the
average time is
O
(
n
log
n
). The exact average-case analysis is beyond the scope of this topic.
Both merge sort and quick sort employ the divide-and-conquer approach. For merge sort,
the bulk of the work is to merge two sublists, which takes place
after
the sublists are sorted.
For quick sort, the bulk of the work is to partition the list into two sublists, which takes place
before
the sublists are sorted. Merge sort is more efficient than quick sort in the worst case,
but the two are equally efficient in the average case. Merge sort requires a temporary array
for sorting two subarrays. Quick sort does not need additional array space. Thus, quick sort is
more space efficient than merge sort.
=
O
(
n
log
n
) average-case time
quick sort vs. merge sort
23.10
✓
✓
Describe how quick sort works. What is the time complexity for a quick sort?
Check
23.11
Why is quick sort more space efficient than merge sort?
Point
23.12
Use Figure 23.7 as an example to show how to apply a quick sort on
{45, 11, 50, 59, 60, 2, 4, 7, 10}.
A heap sort uses a binary heap. It first adds all the elements to a heap and then
removes the largest elements successively to obtain a sorted list.
Key
Point
Heap sorts
use a binary heap, which is a complete binary tree. A binary tree is a hierarchical
structure. It either is empty or it consists of an element, called the
root
, and two distinct binary
trees, called the
left subtree
and
right subtree
. The
length
of a path is the number of the edges
in the path. The
depth
of a node is the length of the path from the root to the node.
A
binary heap
is a binary tree with the following properties:
heap sort
root
left subtree
right subtree
length
depth
Shape property: It is a complete binary tree.
■
Heap property: Each node is greater than or equal to any of its children.
■
A binary tree is
complete
if each of its levels is full, except that the last level may not be full
and all the leaves on the last level are placed leftmost. For example, in Figure 23.9, the binary
trees in (a) and (b) are complete, but the binary trees in (c) and (d) are not complete. Further,
the binary tree in (a) is a heap, but the binary tree in (b) is not a heap, because the root (39) is
less than its right child (42).
complete binary tree
42
39
42
42
32
39
32
42
32
39
32
22
29
14
33
22
29
14
22
14
33
22
29
(a) A heap
(b)
(c)
(d)
F
IGURE
23.9
A binary heap is a special complete binary tree.
Search WWH ::
Custom Search