Java Reference
In-Depth Information
11 }
12
13
// Insert the current element into list[k + 1]
14
list[k +
1
] = currentElement;
insert
15 }
16 }
17 }
The
insertionSort(int[] list)
method sorts any array of
int
elements. The method
is implemented with a nested
for
loop. The outer loop (with the loop control variable
i
) (line
4) is iterated in order to obtain a sorted sublist, which ranges from
list[0]
to
list[i]
. The
inner loop (with the loop control variable
k
) inserts
list[i]
into the sublist from
list[0]
to
list[i-1]
.
To better understand this method, trace it with the following statements:
int
[] list = {
1
,
9
,
4
,
6
,
5
,
-4
};
InsertionSort.insertionSort(list);
The insertion sort algorithm presented here sorts a list of elements by repeatedly inserting a
new element into a sorted partial array until the whole array is sorted. At the
k
th iteration, to
insert an element into an array of size
k
, it may take
k
comparisons to find the insertion posi-
tion, and
k
moves to insert the element. Let
T(n)
denote the complexity for insertion sort and
c
denote the total number of other operations such as assignments and additional comparisons
in each iteration. Thus,
insertion sort time complexity
T
(
n
)
=
(2
+
c
)
+
(2
*
2
+
c
)
+
g
+
(2
*
(
n
-
1)
+
c
)
=
2(1
+
2
+
g
+
n
-
1)
+
c
(
n
-
1)
2
(
n
-
1)
n
n
2
=
+
cn
-
c
=
-
n
+
cn
-
c
2
O
(
n
2
)
=
Therefore, the complexity of the insertion sort algorithm is
O
(
n
2
). Hence, the selection sort
and insertion sort are of the same time complexity.
23.1
✓
✓
Describe how an insertion sort works. What is the time complexity for an insertion
sort?
Check
Point
23.2
Use Figure 23.1 as an example to show how to apply a bubble sort on {45, 11, 50, 59,
60, 2, 4, 7, 10}.
23.3
If a list is already sorted, how many comparisons will the
insertionSort
method
perform?
A bubble sort sorts the array in multiple phases. Each pass successively swaps the
neighboring elements if the elements are not in order.
Key
Point
The bubble sort algorithm makes several passes through the array. On each pass, successive
neighboring pairs are compared. If a pair is in decreasing order, its values are swapped; oth-
erwise, the values remain unchanged. The technique is called a
bubble sort
or
sinking sort
,
because the smaller values gradually “bubble” their way to the top and the larger values sink
to the bottom. After the first pass, the last element becomes the largest in the array. After the
second pass, the second-to-last element becomes the second largest in the array. This process
is continued until all elements are sorted.
bubble sort
Search WWH ::
Custom Search