Java Reference
In-Depth Information
1
// Standard heapsort.
2
public static <AnyType extends Comparable<? super AnyType>>
3
void heapsort( AnyType [ ] a )
4
{
5
for( int i = a.length / 2 - 1; i >= 0; i-- ) // Build heap
6
percDown( a, i, a.length );
7
for( int i = a.length - 1; i > 0; i-- )
8
{
9
swapReferences( a, 0, i ); // deleteMax
10
percDown( a, 0, i );
11
}
12
}
figure 21.28
The
heapSort
routine
Exercise 21.23. Assuming that we have written
percDown
, we can easily
express
heapSort
as shown in Figure 21.28.
Although heapsort is not as fast as quicksort, it can still be useful. As dis-
cussed in Section 8.6 (and detailed in Exercise 8.20), in quicksort we can keep
track of each recursive call's depth, and switch to an
O
(
N
log
N
) worst-case sort
for any recursive call that is too deep (roughly 2 log
N
nested calls). Exercise
8.20 suggested mergesort, but actually heapsort is the better candidate.
external sorting
21.6
So far, all the sorting algorithms examined require that the input fit in main
memory. However, the input for some applications is much too large to fit in
main memory. In this section we discuss
external sorting,
which is used to
handle such very large inputs. Some of the external sorting algorithms involve
the use of heaps.
External sorting
is
used when the
amount of data is
too large to fit in
main memory.
21.6.1
why we need new algorithms
Most of the internal sorting algorithms take advantage of the fact that memory
is directly accessible. Shellsort compares elements
a[i]
and
a[i-gap]
in one
time unit. Heapsort compares
a[i]
and
a[child=i*2]
in one time unit. Quick-
sort, with median-of-three pivoting, requires comparing
a[first]
,
a[center]
,
and
a[last]
in a constant number of time units. If the input is on a tape, all
these operations lose their efficiency because elements on a tape can be
accessed only sequentially. Even if the data are on a disk, efficiency still suf-
fers because of the delay required to spin the disk and move the disk head.
Search WWH ::
Custom Search