Civil Engineering Reference
In-Depth Information
4
1
4
1
1
7
4
4
7
3
9
7
7
4
9
1
9
9
7
3
3
3
9
Figure 2.35
Inserting the fourth and fifth numbers.
In the insertion of the (k + 1)
th
item, k comparisons or number shiftings have to be carried
out, and the number of operations for sorting n items is given by
=+++−+−=
−
nn
(
1
)
N
12
(
n
2
)
(
n
1
)
2
Hence, insertion sort is also an order
O
(n
2
) algorithm. However, insertion sort has an
average performance better than that of bubble sort as fewer swaps of elements are required
in the insertion process. The following is the
pseudo-code
of the insertion sort algorithm.
Algorithm Insert_Sort (n, A)
// A = Array to be sorted, A
i
= Element in A with index i, n = Number of
// items
{
Loop: i = 2,n
T = A
i
j = 1
While (A
j
< T) j = j + 1
Loop: k = i, j + 1, -1
A
k
= A
k-1
End loop k
A
j
= T
End loop i }
2.6.3 Quick sort
Quick sort is a
divide-and-conquer
algorithm. A list of n items is divided into two sub-lists
by properly positioning a pivot taken out randomly from the original list. The sub-lists are
further divided into shorter lists by introducing a pivot in each sub-list following exactly the
same way as for the original list. Hence, a recursive procedure can be easily devised to deal
with the lists and sub-lists in turn until there are only two items in the list or there are three
items in the list with the pivot at the middle. In the ideal scenario, the pivots always cut the
lists more or less into two equal halves. The level of subdivisions k reducing a list of n items
down to a list of two or three items is given by
=
log( )
log( )
n
2
k
=
nork
2
