469,636 Members | 1,951 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Share your developer knowledge by writing an article on Bytes.

Insertion Sort

3,652 Expert 2GB
So far, the Articles sections are filled with slow sorting algorithms. Bubble Sort and Selection Sort, while very easy to comprehend, are relatively slow algorithms at Θ(n^2) running time. Here, I will try to explain an algorithm to sort an array of numbers that is fast for small sets of data, though it is still an O(n^2) algorithm; the Insertion Sort.

Suppose we have an array of n-1 elements that is already sorted in increasing order. We then come to the nth element (let us call it x) to be ‘inserted’ into this sorted array. It follows that there is some portion of the array in which the elements are less than x, and another portion in which the elements are greater than x. Further, because we know that the existing array is sorted, we know that the array generally looks like this:

[elements < x][elements>x]

We begin the algorithm by creating a hole at the end of the array:

[elements<x][elements>x][empty hole]

Now, we want to have our array completely sorted for all n elements at the end, so the alert reader may realize that the array must look like this when we are done at this step:


It follows that all of the elements greater than x must shift down the array one slot. We can, in fact, do this very simply by moving any element a[j] to a[j+1] as long as a[j] is greater than x. We start this moving at the element just before the hole and continue until the element we check is less than x. Now every element has been shifted one slot and overwritten every previously copied value except for the last to be shifted, of which there remains 2 copies adjacent to each other. We know that this element is greater than x (or else we would not have shifted it) and so we place x in the position that element originally held.

A powerful note to this algorithm is that it can be implemented to use no extra space. If we consider only the first I elements of any array as our sorted array, then creating a hole is as simple as increasing our array’s size, making a copy of the last term (which must be inserted into its sorted position), and following our steps above. The algorithm in pseudocode is presented below:

Expand|Select|Wrap|Line Numbers
  1. void insertion_sort(int[] array) {
  2.     for (Loop i from 1 to array.size-1)
  3.         int x = array[i]
  4.         int j = array[i-1]
  5.         while (j >= 0 && array[j] > x)
  6.             array[j+1] = array[j]
  7.             j = j - 1
  8.         array[j+1] = x
  9. }
Nov 16 '07 #1
0 3587

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

2 posts views Thread by N. | last post: by
4 posts views Thread by ashu | last post: by
1 post views Thread by Franky, Mondestin | last post: by
11 posts views Thread by Am | last post: by
6 posts views Thread by Julia | last post: by
19 posts views Thread by tkpmep | last post: by
9 posts views Thread by python_newbie | last post: by
reply views Thread by gheharukoh7 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.