Insertion Sort

17 July 2009, 06:08 PM

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. */`

publicvoidinsertionSort(int[] data) {intj, v ;for(inti=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

Post a comment~

Neha Kothari, 28 May 2012, 07:43 AMi 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