Insertion
sort
Let
a be an array of numbers a[1], a[2] ….. a[n]. Our aim is to sort them in
ascending order using insertion sort.
Principle
Scan
the array a from a[1] to a[n] and find the smallest elements a[r], r = 1, 2 ……,
r and insert into its proper position in the previously sorted sub array a[1],
a[2] …. a[r]. This can be explained by
the following steps.
i)
For r = 1 the previously sorted such
array is empty therefore a[1] by itself is sorted.
ii)
For r =2 , a[2] is inserted into the
proper position in the previously sorted sub array a[1] i.e.; a[2] is inserted
after or before a[1].
iii)
For r = 3, a[3] is inserted into the
proper position in the previously sorted sub array a[1], a[2]. i.e.; a[3] is
inserted either before a[1] or after a[2] or in between a[1] and a[2].
The above steps are
repeated until the last element a[n] is inserted into its proper position in
the sorted sub array. Now the given array a is in sorted order.
Arrange
the given array of numbers in ascending order
Let
the numbers in the array a are
a[1]
= 43 a[2] = 72 a[3] = 10
a[4] = 23 a[5] = 80 a[6] = 1
a[7] = 75
a[1] a[2] a[3] a[4] a[5] a[6] a[7] r
[43] 72 10 23 80 1 75 1 
Sorted sub array
[43] 72 10 23 80 1 75 2
New insert element in the sorted
sub array [43]
[43 72] 10 23 80 1 75 3 Sorted
sub array
[10 43 72] 23 80 1 75 4
Sorted sub array
[10 23 43 72] 80 1 75 5
[10 23 43 72 80] 1 75 6
[1 10 23 43 72 80] 75 7
[1 10 23 43 72 75 80]
After
n elements are inserted into its proper position the array a is in sorted order.
Procedure
insertionsort
(a, n)
// a is the name of the array. N is the size of the
array.
{
for
i = 1 to n do
{
x
= a[i] ;
j
= i ;
While
(x<a[j-1] && j-1≥ 1) do // to find the first biggest element than
new data.
j =
j-1 ;
k =
i ;
while
(j < k) do //shifting the data 1
position forward.
{
a[k] = a[k-1] ;
k = k – 1 ;
}
a[j] = x ;
}
}
Evaluation of the above procedure with an example
a[1] a[2] a[3] a[4] a[5] a[6] a[7] i j k x
43 72 10 23 80 1 75 1 1 1 43
43 72 10 23 80 1 75 2 2 2 72
43 72 10 23 80 1 75 3 2 3 10
43 72 72 23 80 1 75 3 1 2 10
43 43 72 23 80 1 75 3 1 1 10
10 43 72 23 80 1 75 4 2 4 23
10 43 72 72 80 1 75 4 2 3 23
10 43 43 72 80 1 75 4 2 2 23
10 23 43 72 80 1 75 5 5 5 80
10 23 43 72 80 1 75 6 1 6 1
10 23 43 72 80 80 75 6 1 5 1
10 23 43 72 72 80 75 6 1 4 1
10 23 43 43 72 80 75 6 1 3 1
10 23 23 43 72 80 75 6 1 2 1
10 10 23 43 72 80 75 6 1 1 1
1 10 23 43 72 80 75 7 6 7 75
1 10 23 43 72 80 80 7 6 6 75
|
Complexity
Let
f(n) be the number of comparisons required. Then
f(n)
= 1 +2 + 3 + ……. (n-1)
No comments:
Post a Comment