home | news | contact | about
Insertion Sort
17 July 2009, 06:08 PM
Ahh~ the elementary sorting algorithm that is actually worth using. Although its improved cousin shellsort is better (actually *much* better), insertion sort excels when it comes to how much effort is needed on implementation. That is a given really, in fact insertion sort is the basis for shellsort so it has to be simpler right? Now if it tickles you to jump directly into shellsort, I'd like to remind you shellsort is quite complicated for an elementary method and can be confusing without prior knowledge of insertion sort. Give insertion sort some love shall we? I'm sure this will be an act to be appreciated very very soon.

Jeez thats some cheesy introduction for a sorting algorithm - an elementary one at that. One might say. But I figured having stern robotic writing is boring even to myself - something I discovered the hard way after reading my other articles. Dead boring. So might as well slack a bit and have fun writing.

To start with this one, let us have a look at an animation of insertion sort in action. See below for the applet. Click it if needed, which restart the sort with new random elements. The good thing with having this animation is, we human tend to understand things better with vision compared to reading. You know something is a banana just by looking at it, instead of told (or reading) 'a fruit that is shaped like a d**k that has to be peeled open for consumption', and many other ambiguous description. So observe the applet below and get a feel on how it works. Doesn't mean you'll necessarily have to understand it at this time (which is highly probable) but get a general mental picture of how elements move. Here is a tip: The algorithm becomes almost dead obvious just by looking at where the green bar stops and a new one selected! See if you can see this one! Don't be shy to reset a few time ;)


Applet: Insertion sort applet. Click to reset with new elements.

If that still escapes you, the following explanation will be the last thing I can offer. Use it together with the applet and "connect the dots". But first we will tackle the problem by investigating how insertion sort works. It works by considering one element at a time starting from the first (left-most), and properly inserting it among those already considered and at the same time keeping them sorted. This is pictured in our little applet up there. One element is selected (green bar) just to the right of the red line and comparing this selected element with its left neighbor. If the element on the immediate left is larger than the green bar, move that larger element one step to the right. It will appear as if the two has exchanged position, but not quite. The only actual movement is for the larger element which has moved one step ahead to the right, overwriting the selected element. Fortunately the selected element is already cached preventing it from being lost. Note: doing the exchange instead of caching is valid too but that is a waste of processor time!

The green bar will keep 'moving' to the left until it is not smaller than its immediate left neighbor. Once it stops, means the 'proper' spot has been found and the green bar is then inserted there. However this is not yet a permanent position, not until the last right most element is considered. The following will be a sample implementation in Java - so simple not much to say of it.

/**
 * InsertionSort data. Sorting is in-place.
 * @param data Array to sort. 
 */
public void insertionSort(int[] data) {
    int j, v ;
    for (int i=1;i<data.length;i++) {
        j = i ;
        v = data[i] ;
        // find proper spot for v
        while ((j > 0) && (data[j-1] > v)) {
            // move larger element
            data[j] = data[j-1] ;
            j-- ;          
        }
        // insert selected(v) element
        data[j] = v ;
    }
}

Last edited on 17 July 2009

Comments

~Neha Kothari, 28 May 2012, 07:43 AM
hi i read ur post.
i can vary the insertion sort in the following manner.
can you make the program for it....than mail me at:nehakothari492@yahoo.in

Suppose X is an array of N positive integers to be sorted. In this scheme, another array Y is used to store the
sorted integers. This array is to be viewed as a circular array, ie. index (N-1)+1 = index 0 and index 0-1 =
index N-1. The sorted integers get stored in a circular manner in Y, ie, it is possible that the index of the
smallest integer may be greater than the index of the largest integer.
Eg. 6 8 _ _ _ 1 2 4 5 is a view of the array Y sometime into the algorithm. ’_’ indicates unused locations of
the array. Smallest integer 1 is at index 5, largest integer 8 is at index 1. So the sorted array in Y is to be
generated by printing the contents from index 5 to 1, assuming the array wraps around at the end, ie. after
index 8, the next index is 0.
Assume that h holds the index of the smallest integer in Y and t holds the index of the largest integer in Y.
Initially,
1. h = t = 0
2. Y[0] = X[0] ie. the first integer in X[] is copied as the first integer in Y[].
3. All other elements in Y[] are initialised to a dummy value -1.
The rest of the integers in X[] are now inserted one by one into Y[] such that Y[] always contains a sorted
list of integers, with the smallest integer at index h and the largest at index t. This is done in the following
manner:
Let I be the next integer from X[] to be inserted into Y[]. Scan the array Y downwards from index h (with
wrap-around at the end) till index t and find out the place in Y[] where I has to fit in. If I fits in at either end
of the list, then insert it at the appropriate place in Y[]. Modify either t or h as appropriate to indicate the new
array structure; ie. either t is incremented or h is decremented (with wrap-around).
If I fits in somewhere in the middle of the list, then I should be inserted by shifting all the S smaller integers
one place to the left or by shifting all the L larger integers one place to the right, depending on the number of
integers to be shifted. That is, if S < L, the smaller integers should be shifted one place to the left and if S >=
L, the larger integers should be shifted one place to the right. Again either h or t should be modified
appropriately.
Example
Integers to be sorted X[]: 25 57 37 48 12 92 86 33
Contents of Y[] after inserting each integer from X[]:
Initially (t=0, h=0)
25 –1 –1 –1 –1 –1 –1 –1
57 fits in at end (t=1)
25 57 –1 –1 –1 –1 –1 –1
37 fits in middle, S=1, L=1, so shift 57 right. (t=2)
25 37 57 –1 –1 –1 –1 –1
48 fist in middle, S=2, L=1, So shift 57 right. (t=3)
25 37 48 57 –1 –1 –1 –1
12 fits in at beginning, circular property, (h=8, t=3)
25 37 48 57 –1 –1 –1 12
92 fits in at end (t=4).
25 37 48 57 92 –1 –1 12
86 fits in middle, S=5, L=1, so shift 92 right, (t=5).
25 37 48 57 86 92 –1 12
33 fits in middle, S=2, L=5, so shift 12, 25 left (h=7, t=5).
33 37 48 57 86 92 12 25
Input Specification
The input will consist of a single line containing an integer N followed by the N integers to be sorted. All
integers are positive and are separated by a single space. There will be no duplicates among the N integers.
Output Specification
The output should consist of N lines, each line containing N integers. The N integers are the contents of Y[]
(ie. Y[0] to Y[N-1]) after the insertion of each integer from X[]. All integers on a line should be separated by
a single space. N will be less than 50.
Sample Input/Output
Input
8 25 57 37 48 12 92 86 33
Output
25 -1 -1 -1 -1 -1 -1 -1
25 57 -1 -1 -1 -1 -1 -1
25 37 57 -1 -1 -1 -1 -1
25 37 48 57 -1 -1 -1 -1
25 37 48 57 -1 -1 -1 12
25 37 48 57 92 -1 -1 12
25 37 48 57 86 92 -1 12
33 37 48 57 86 92 12 25
Post a comment~
Name*
Type secret in reverse*
Comment*
Notes: The comment system is moderated.
Meaning your comment will not show until reviewed.