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:
What is Insertion Sort?: Insertion Sort as you know is a fairly simple to implement comparison based sorting algorithm. As Ive 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, lets 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)Its 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 whats 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:CODE
//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?
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)
Insertion Sort: Everything You Wanted to Know, A description, implementation, analysis, and basic information about I
11 Jul, 2008 - 10:29 AM
| 