Java Reference
In-Depth Information
FIGURE 9-10
The time efficiency of various sorting algorithms, expressed in
Big Oh notation
Average Case
Best Case
Worst Case
Radix sort
Merge sort
Quick sort
Shell sort
Insertion sort
Selection sort
O(
n
)
O(
n
log
n
)
O(
n
log
n
)
O(
n
1.5
)
O(
n
2
)
O(
n
2
)
O(
n
)
O(
n
log
n
)
O(
n
log
n
)
O(
n
)
O(
n
)
O(
n
2
)
O(
n
)
O(
n
log
n
)
O(
n
2
)
O(
n
2
) or O(
n
1.5
)
O(
n
2
)
O(
n
2
)
To give you an idea of how the problem size affects time efficiency, Figure 9-11 tabulates the
four growth-rate functions that appear in Figure 9-10 for several values of
n
. You certainly could
use an O(
n
2
) sort algorithm when
n
is 10. When
n
is 100, a Shell sort is almost as fast as a quick
sort in the average case. But when
n
is one million, an average-case quick sort is much faster than a
Shell sort and much, much faster than an insertion sort.
If your array has relatively few entries, or if it is nearly sorted, the insertion sort is a
good choice. Otherwise, the quick sort is generally preferable. Note that merge sort is useful
when the data collection is in an external file because it is too large to reside in main mem-
ory all at once.
We will discuss another sorting algorithm, the heap sort, in Chapter 26. This technique is also
O(
n
log
n
), but the quick sort is usually preferable.
FIGURE 9-11
A comparison of growth-rate functions as
n
increases
10
2
664
10
3
10
4
10
3
9966
31,623
10
6
10
4
132,877
10
6
10
8
10
5
1,660,964
31,622,777
10
10
10
6
19,931,569
10
9
10
12
n
n
log
2
n
n
1.5
n
2
10
33
32
10
2
C
HAPTER
S
UMMARY
•
Merge sort is a divide and conquer algorithm that halves an array, recursively sorts the two halves, and then
merges them into one sorted array.
•
Merge sort is O(
n
log
n
). However, it does use additional memory to perform the merge step.
•
Quick sort is another divide and conquer algorithm that partitions an array into two subarrays that are sepa-
rated by one entry, the pivot. The pivot is in its correct sorted position. The entries in one subarray are less
than or equal to the pivot, while the entries in the second subarray are greater than or equal to the pivot.
Quick sort recursively sorts the two subarrays.
•
Quick sort is O(
n
log
n
) most of the time. Although it is O(
n
2
) in its worst case, you usually can avoid this
case by choosing appropriate pivots.
•
Even though merge sort and quick sort are O(
n
log
n
) algorithms, quick sort is usually faster in practice and
does not require additional memory.
