Insertion
sort
Procedure:
Step
1: The second element of an array is
compared with the elements that appears before it (only first element in this
case). If the second element is smaller than first element, second element is
inserted in the position of first element.
Step
2:
The third element of an array is compared with the elements that appears
before it (first and second element). If third element is smaller than second
and first element, it is inserted in the position of first element.
If third element is larger than first
element but, smaller than second
element, it is inserted in the position of second element. If third element is larger
than both the elements, it is kept in the position as it is.
Step
3: Repeat the above
steps for n-1 times. At the end of the n-1 th pass, all the elements of the
array is available in sorted order.
Algorithm:
Step 1:
Repeat iß1 to n-1 and increment by 1
key
= a[i];
Repeat
jßi-1
to j>=0 && a[ j] > key and decrement by 1
a[
j+1] = a[ j];
End
Repeat
a[
j+1] = key;
End Repeat
Example:
Before sorting the
given array is a={15,20,10,30,50,18,5,45}
0 comments:
Post a Comment