Home Practices Page 3 - Sort This Sort That

Inserting Methods - Practices

One of the main activities in algorithms and programs, whose purpose is manipulating data, is sorting. So if you write these kinds of programs-what kind of method for sorting data is best? In this article I will present some algorithms for sorting and their advantages and weaknesses.

Rating:  / 21
February 25, 2004

SEARCH DEV SHED

TOOLS YOU CAN USE

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-SORTfor 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]=kend_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.

 >>> More Practices Articles          >>> More By Djordje Popovic