Java Reference
In-Depth Information
do
{
a. move list[location - 1] one array slot down
b. decrement location by 1 to consider the next element
sorted of the portion of the array
}
while
(location > 0 && the element in the upper list at
location - 1 is greater than temp)
}
copy temp into list[location]
The following Java method implements the previous algorithm:
public static void
insertionSort(
int
[] list,
int
listLength)
{
int
firstOutOfOrder, location;
int
temp;
for
(firstOutOfOrder = 1; firstOutOfOrder < listLength;
firstOutOfOrder++)
if
(list[firstOutOfOrder] < list[firstOutOfOrder - 1])
{
temp = list[firstOutOfOrder];
location = firstOutOfOrder;
do
{
list[location] = list[location - 1];
location--;
}
while
(location > 0 && list[location - 1] > temp);
list[location] = temp;
}
}
//end insertionSort
We leave it as an exercise for you to write a program to test the insertion sort algorithm.
It is known that for a list of length n, on average, an insertion sort makes about
n
2
þ
3
n
4
4
key comparisons and about
nðn
1
Þ
4
item assignments. Therefore, if n
¼
1000, to sort
the list, insertion sort makes about 250,000 key comparisons and about 250,000 item
assignments.
This chapter has presented two sorting algorithms, but there are many others. (For example,
the Additional Student Files folder at www.cengagebrain.com contains a bubble sort and a quick
sort algorithm.) Why are there so many different sorting algorithms? The answer is that the
performance of each sorting algorithm is different. Some algorithms make more compar-
isons, some make fewer item assignments, and some algorithms make fewer comparisons as
well as fewer item assignments. The preceding sections gave the average number of comparisons
and item assignments for this chapter's three sorting algorithms. By analyzing the number
Search WWH ::
Custom Search