Page 1 of 1

Insertion Sort: Everything You Wanted to Know A description, implementation, analysis, and basic information about I Rate Topic: ***** 1 Votes

#1 captainhampton  Icon User is offline

  • Jawsome++;
  • member icon

Reputation: 13
  • View blog
  • Posts: 548
  • Joined: 17-October 07

Posted 11 July 2008 - 10:29 AM

Introduction:

This tutorial is based on the sorting algorithm “Insertion Sort”, one of the best known and usually one of the first few sorting routines students learn who are going into the field of computer science. Although this algorithm is not the most efficient for certain data sets, it most certainly has its purpose for others. Having an assortment of different sorting algorithms at your finger tips parallels to a wizard having a book of many spells. The more spells you know, the more you will be able to counter-act other spells. Having a good arsenal of these algorithms and knowing what situations to apply them to will help you make the best decision in a real-life application. Keep this in mind as you add this spell to your book:

:blink: What is Insertion Sort?:

Insertion Sort as you know is a fairly simple to implement comparison based sorting algorithm. As I’ve stated before, Insertion Sort has its moment in the sun when used upon small data sets, which Quick Sort (Check out my Quick Sort Tutorial for more information) does very poorly on. Of course, conversely Insertion Sort does a poor job with large data sets. Another benefit in using Insertion Sort would be if you know that the majority of your set of data will be sorted, before choosing an algorithm, Insertion Sort also shines here. Insertion Sort is also more efficient than its counterpart sorts, Bubble Sort and Selection Sort both of which have about the same running time, however in practice Insertion Sort tends to trump these as well. One of the final reasons as to why Insertion Sort is efficient is that it happens to be an “on-line” algorithm which means it takes the input as it comes to it and does not have to digest the entire set at once.

The Algorithm:

Now that we know a bit about what Insertion Sort is and appropriate situations to use it in, let’s take a brief look at the algorithm to which it is based upon:

In short if we have a set of data, and we want to perform the Insertion Sort routine, we simply insert the elements one by one into our array. As each element is inserted, it is compared to the element it is next to. If the current element is less than the previous one we move it down progressively as we call this function. To make this a bit more concrete an example is provided here:

Legend: ( Numbers highlighted in Green are the sorted elements in the data set ).

Here is our set of integers for this example. We start off with “7” inserted into the list, which is fine and we progress from there:
[ 7 9 0 5 6 4 8 3 ] -Swaps made: (0)

We move on to “9” which is greater than “7”. Since this is so no swaps are made and the list is happy:
[ 7 9 0 5 6 4 8 3 ] -Swaps made: (0)

Now we get to an element of lesser value, “0”. We take the appropriate action, compare it to “9” and find out it is less so we move it down in between “7” and “9”. We then compare it to “7” which it is also less than, move it on down again for a total of 2 swaps:
[ 0 7 9 5 6 4 8 3 ] -Swaps made: (2)

“5” is the next victim on our list. “5” is compared with “9” moved down, compared with “7” and likewise moved down. Finally compared with "0" and since “5” is greater than “0” it is in the correct position and does not swap:
[ 0 5 7 9 6 4 8 3 ] -Swaps made: (2)

It’s time for “6” to shine, it is compared with “9” moved down, and compared with “7” and moved down. “5” is less than “6” so it is in its new happy home:
[ 0 5 6 7 9 4 8 3 ] -Swaps made: (2)

“4” has a bit of a journey ahead of it. It will be swapped with “9”, then “7”, “6”, and “5”. It is greater than “0” so it has reached its destination:
[ 0 4 5 6 7 9 8 3 ] -Swaps made: (4)

“8” has a short journey it is compared with “9” and swapped. Compared with “7” and decides its content with his position so he stays:
[ 0 4 5 6 7 8 9 3 ] -Swaps made: (1)

“3” traverses almost all of the way down the list until it meets up with his new neighbor “0”:
[ 0 3 4 5 6 7 8 9 ] -Swaps made: (6)


The idea of Insertion Sort is fairly easy to see, it logically makes a lot of sense in the realm of comparisons. Now that you have a good handle on what’s going on let us take a look behind the scenes and see what is happening from the coding aspect of things.

The Code

The code, like the algorithm is easy to implement and see what is happening throughout. Let us take a look at the code:

Insertion Sort Routine:
//insertionSort Function
void insertionSort(int size, int data[]){
  int j, val;
  
  //iterate through entire list
  for(int i = 1; i < size; i++){
	 val = data[i];
	 j = i - 1;
	 
	 while(j >= 0 && data[j] > val){
			   data[j + 1] = data[j];
			   j = j - 1;
	 }//end while
	 data[j + 1] = val;
  }//end for
  
  //Prints the sorted list
  for ( int i = 0; i < size; i++ )
	  cout << data[i] << " ";
	  
  
}//end insertionSort Function



As we can see quite clearly, the code follows the basic structure of the algorithm very nicely. Next we will give a brief asymptotic analysis of the Insertion Sort algorithm.

Analysis & Conclusion

As we have witnessed Insertion Sort has its optimum niche in the world of sorting algorithms. Remember that sorting algorithms are situation specific, and if one algorithm does not cater to a specific case than you must strategically pick another, you wouldn't attempt to cut down a tree with a spoon would? :P Insertion Sort as every other sort have their pros and cons use this knowledge to your advantage and be able to apply it to the correct occurrences.

Now for a look at asymptotic analysis:

Worst Case:
Insertion Sort has a worst case of O(N * N) or O(N)(squared). This is achieved because regardless it has to traverse as well as swap through the entire list

Average Case:
Average follows suit with the worse case, mainly because on average you are going to have to traverse the list and swap, it as well gives the running time of O(N * N) or O(N)(squared). Average case can also be analyzed from a different view point as well, if we take O(N + i ), "i" being inversions we can achieve the average case by this method as well.

Best Case:
The best case would be that the list was already sorted, meaning it would only have to traverse the list as oppose to traverse and swap. This yields a linear time complexity to it, or O(N)

Is This A Good Question/Topic? 4
  • +

Replies To: Insertion Sort: Everything You Wanted to Know

#2 gabehabe  Icon User is offline

  • GabehabeSwamp
  • member icon




Reputation: 1383
  • View blog
  • Posts: 10,962
  • Joined: 06-February 08

Posted 11 July 2008 - 11:07 AM

This is a nice series of sort tutorials you've got going here, I look forward to seeing the next one :)
Was This Post Helpful? 0
  • +
  • -

#3 captainhampton  Icon User is offline

  • Jawsome++;
  • member icon

Reputation: 13
  • View blog
  • Posts: 548
  • Joined: 17-October 07

Posted 11 July 2008 - 11:27 AM

View Postgabehabe, on 11 Jul, 2008 - 11:07 AM, said:

This is a nice series of sort tutorials you've got going here, I look forward to seeing the next one :)


Thank you very much, I really just wanted to encapsulate searching and sorting algorithms in such a way for people to be able to develop a deeper understand and more or less appreciation. Thank you again for your kind words.
Was This Post Helpful? 0
  • +
  • -

#4 gabehabe  Icon User is offline

  • GabehabeSwamp
  • member icon




Reputation: 1383
  • View blog
  • Posts: 10,962
  • Joined: 06-February 08

Posted 11 July 2008 - 11:33 AM

Well, I had problems with search algorithms (mostly because I never really paid much attention to any but bubble, which is in my snippets) but your tutorials are a good read :^:

Thanks for the great resources :)
Was This Post Helpful? 0
  • +
  • -

#5 born2c0de  Icon User is offline

  • printf("I'm a %XR",195936478);
  • member icon

Reputation: 180
  • View blog
  • Posts: 4,667
  • Joined: 26-November 04

Posted 12 July 2008 - 05:01 AM

View Postgabehabe, on 12 Jul, 2008 - 12:03 AM, said:

Well, I had problems with search algorithms (mostly because I never really paid much attention to any but bubble, which is in my snippets) but your tutorials are a good read :^:

Thanks for the great resources :)

You mean bubble sort right? ;)
Was This Post Helpful? 0
  • +
  • -

#6 wartech  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 10
  • View blog
  • Posts: 203
  • Joined: 16-October 06

Posted 16 September 2008 - 02:09 AM

Great explanation on the algorithm! It was very easy to understand. More tutorials please...:)

Actually captainhampton I just checked out the rest of your tutorials. Very nice. I need more time to check them out. B)
Was This Post Helpful? 0
  • +
  • -

#7 Guest_quest*


Reputation:

Posted 16 July 2010 - 05:49 PM

'Swaps' may be a mis-leading word here ... since the values are moved up one position ('right') each comparison, over-writing that value to its 'right' ... The comparator value is copied over that 'final opened-up available position' ... ONLY AT THE END OF THAT PASS.

It may be best to think of an insert sort like this:

1. first one takes the array of the 1st 2 elements and inserts the 2nd element in the correct place.

2. then take the array of 3 elements and insert the 3rd element in the correct place

...

(n-1). On (n-1)th pass, insert the nth element in its correct place.

Now you are done!.
Was This Post Helpful? 0

#8 ddotreprah  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 19-February 11

Posted 19 February 2011 - 04:12 PM

Thanks for this thread, helped me understand fully how insertion sort works. Hope I'm not bumping an age old thread, found this on google when trying to find a better explaination to the algorithm behind insertion sort.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1