Inserting Methods - Practices

These methods are based on step-by-step array sorting. You have two parts of an array, sorted and unsorted, so you take one element from the unsorted part and put it in the right place of sorted part.

Let's see an example of direct inserting method or insertion-sort algorithm:


INSERTION-SORT
for i=2 to n do 
 k=a[i]
 j=i-1
 while( j>0) and (a[j]>k) do
  a[j+1] = a[j]
  j=j-1
 end_while
 a[j+1]=k
end_for



This is how this algorithm works. After i iterations of the for loop, our array has sorted and unsorted parts. (See image below.)  In the next iteration we take the first element from the unsorted part and place it in variable k. In the while loop we compare this variable with the last element in the sorted part of our array. 

If the value of the element in the while loop is bigger than the value of the for loop we move it one place above in our array. Now we take the next element from the sorted part and compare it with variable k.  If this element is bigger we move it up one position in the array. 

We repeat this process until we find an element value bigger than the value of variable k. At this moment we stop the while loop, and place our value of variable k one place behind found value. After our while loop is over (when i reaches value n) our array will be sorted. In this case, in ascending order.

This method is most effective if our array of keys is smaller and almost sorted.  The worst thing about this algorithm is that it requires much record moving. This leads to the conclusion that our array should be organized as a linked-list if our records are big. In this way we can just reconnect pointers.