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.
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 vwhile ((j > 0) && (data[j-1] > v)) {// move larger elementdata[j] = data[j-1] ; j-- ; }// insert selected(v) elementdata[j] = v ; } }
Last edited on 17 July 2009
Comments
Post a comment~