Java Reference
In-Depth Information
We observed before that the actual number of machine operations, and the actual
number of microseconds that the computer spends on them, is approximately
proportional to the number of element visits. Maybe there are about 10 machine
operations (increments, comparisons, memory loads, and stores) for every element
visit. The number of machine operations is then approximately 10 ¶ . Again, we
1
2
n
2
aren't interested in the coefficient, so we can say that the number of machine
operations, and hence the time spent on the sorting, is of the order of n
2
or O(n
2
).
The sad fact remains that doubling the size of the array causes a fourfold increase in
the time required for sorting it with selection sort. When the size of the array
increases by a factor of 100, the sorting time increases by a factor of 10,000. To sort
an array of a million entries, (for example, to create a telephone directory) takes
10,000 times as long as sorting 10,000 entries. If 10,000 entries can be sorted in about
1/2 of a second (as in our example), then sorting one million entries requires well
over an hour. We will see in the next section how one can dramatically improve the
performance of the sorting process by choosing a more sophisticated algorithm.
Selection sort is an O(n
2
) algorithm. Doubling the data set means a fourfold
increase in processing time.
636
637
S
ELF
C
HECK
5.
If you increase the size of a data set tenfold, how much longer does it
take to sort it with the selection sort algorithm?
2
n
2
1
5
2
6.
How large does n need to be so that is bigger than n ɨ3?
A
DVANCED
T
OPIC
14.1: Insertion Sort
Insertion sort is another simple sorting algorithm. In this algorithm, we assume that
the initial sequence
a[0] a[1] . . . a[k]
