Java Reference
In-Depth Information
Sorting algorithms are good examples for studying algorithm design and analysis.
Key
Point
When presidential candidate Barack Obama visited Google in 2007, Google CEO Eric
Schmidt asked Obama the most efficient way to sort a million 32-bit integers (
www.youtube
.com/watch?v=k4RRi_ntQc8
).
Obama answered that the bubble sort would be the wrong way to
go. Was he right? We will examine different sorting algorithms in this chapter and see if he
was correct.
Sorting is a classic subject in computer science. There are three reasons to study sorting
algorithms.
why study sorting?
First, sorting algorithms illustrate many creative approaches to problem solving, and
these approaches can be applied to solve other problems.
■
Second, sorting algorithms are good for practicing fundamental programming tech-
niques using selection statements, loops, methods, and arrays.
■
Third, sorting algorithms are excellent examples to demonstrate algorithm
performance.
■
The data to be sorted might be integers, doubles, characters, or objects. Section 7.11, Sorting
Arrays, presented selection sort. The selection sort algorithm was extended to sort an array of
objects in Section 19.5, Case Study: Sorting an Array of Objects. The Java API contains several
overloaded sort methods for sorting primitive type values and objects in the
java.util.Arrays
and
java.util.Collections
classes. For simplicity, this chapter assumes:
what data to sort?
1. data to be sorted are integers,
2. data are stored in an array, and
3. data are sorted in ascending order.
The programs can be easily modified to sort other types of data, to sort in descending order,
or to sort data in an
ArrayList
or a
LinkedList
.
There are many algorithms for sorting. You have already learned selection sort. This chap-
ter introduces insertion sort, bubble sort, merge sort, quick sort, bucket sort, radix sort, and
external sort.
The insertion-sort algorithm sorts a list of values by repeatedly inserting a new
element into a sorted sublist until the whole list is sorted.
Key
Point
Figure 23.1 shows how to sort the list {
2
,
9
,
5
,
4
,
8
,
1
,
6
} using insertion sort.
The algorithm can be described as follows:
insertion sort animation on
Companion Website
for (int i = 1; i < list.length; i++) {
insert list[i] into a sorted sublist list[0..i-1] so that
list[0..i] is sorted.
}
To insert
list[i]
into
list[0..i-1]
, save
list[i]
into a temporary variable, say
currentElement
. Move
list[i-1]
to
list[i]
if
list[i-1] > currentElement
,
move
list[i-2]
to
list[i-1]
if
list[i-2] > currentElement
, and so on, until
list[i-k] <= currentElement
or
k>i
(we pass the first element of the sorted list).
Assign
currentElement
to
list[i-k+1]
. For example, to insert
4
into {
2
,
5
,
9
} in Step
4 in Figure 23.2, move
list[2]
(
9
) to
list[3]
since
9>4
, and move
list[1]
(
5
) to
list[2]
since
5 > 4
. Finally, move
currentElement
(
4
) to
list[1]
.
Search WWH ::
Custom Search