Java Reference
In-Depth Information
FIGURE 8-16
The time efficiencies of three sorting algorithms, expressed in
Big Oh notation
Best Case
Average Case
Worst Case
O(
n
2
)
O(
n
)
O(
n
)
O(
n
2
)
O(
n
2
)
O(
n
1.5
)
O(
n
2
)
O(
n
2
)
O(
n
2
) or O(
n
1.5
)
Selection sort
Insertion sort
Shell sort
C
HAPTER
S
UMMARY
•
A selection sort of an array selects the smallest entry and swaps it with the first one. Ignoring the new first
entry, the sort then finds the smallest entry in the rest of the array and swaps it with the second entry, and so on.
•
Typically, you perform a selection sort iteratively, although a simple recursive form is possible.
A selection sort is O(
n
2
) in all cases.
•
•
An insertion sort divides an array into two portions, sorted and unsorted. Initially, the array's first entry is in
the sorted portion. The sort takes the next unsorted entry and compares it with entries in the sorted portion.
As the comparisons continue, each sorted entry is shifted by one position toward the end of the array until the
unsorted entry's correct position is located. The sort then inserts the entry into its correct position, which has
been vacated by the shifts.
•
You can perform an insertion sort either iteratively or recursively.
An insertion sort is O(
n
2
) in the worst case but is O(
n
) in the best case. The more sorted an array is, the less
work an insertion sort does.
•
•
You can use an insertion sort to sort a chain of linked nodes, a task that typically is difficult.
•
The Shell sort is a modification of the insertion sort that sorts subarrays of entries that are equally spaced
within the array. The strategy efficiently arranges the array so that it is almost sorted, enabling an ordinary
insertion sort to quickly finish the job.
The worst-case behavior of Shell sort, as implemented in this chapter, is O(
n
2
). With a simple change, its
worst-case behavior can be improved to at least O(
n
1.5
).
•
P
ROGRAMMING
T
IP
•
To use
Comparable
with arbitrary types, write
Comparable<? super T>
instead of
Comparable<T>
E
XERCISES
1.
Show the contents of the array of integers 5 7 4 9 8 5 6 3 each time a selection sort changes it while sorting
the array into ascending order.
2.
Repeat Exercise 1, but use an insertion sort instead.
3.
Repeat Exercise 1, but use a Shell sort instead.
