Okay I know I am again writing one more blog for insertion sort. The first one I had written when I was trying to develop a assembly language library containing all the sorting algorithm functions. Now I am creating a library in C language which will have many sorting algorithm functions and much more other functions. So the first one I tried was Insertion Sort. My primary book reference is "Introduction to Algorithms - 3rd Edition: Authors - Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein".
The way I wrote this function is first I read the concept of insertion sort from the above mentioned book. Then I tried to create a C function based on the read concept. Once done I read the actual pseudo code given in the book and if it is much better I rewrote it in my library. So my version of insertion sort was different than in the book and 99% book version will be better and it happened in my case as well so I changed my logic to match with the book.
Imagine that there is a room, and inside which there are exactly 100 students and each student has class ID. This class ID is any number from 1 to 100. Now you are asked to arrange those students in a line in front of class building in the ascending order of their class IDs. So how do you do it? You will ask students to come out one at a time. First student will stand at the front of line. Now second student comes out. You will check his class ID and compare with the already stood students class ID. If his class ID is smaller than you will ask the earlier student to go back one position and new student will stand infront now. If the new students class ID is greater than the already standing student then you will ask the new student to stand at the next position after the already standing student. This process will repeat until all the students have stood in the line. This is nothing but Insertion sort. You will take a number and try to find the position of this number in the already sorted list of number. Once you found the position you insert that number to that position in the sorted list of number.
My initial code was like this:
//Take each number and place it in correct position
for (int i = 1; i <= nSize; i++)
{
int nKey = arNumbers[i];
int nPos = i;
//Find the position of the new number to be placed
for (int j = 0; j < i; j++)
{
if (arNumbers[j] > nKey)
{
nPos = j;
break;
}
}
if (nPos != i)
{
//Move all the numbers to the right to make the position for new number
for (int k = i - 1; k > nPos; k--)
{
arNumbers[k + 1] = arNumbers[k];
}
arNumbers[nPos] = nKey;
}
}
The above program works fine. But just that I have one extra for loop. I have one FOR loop for finding position to insert key element and one FOR loop to insert the key in the found position. But rather these two loops can be merged into to single loop and we can do both tasks together. Now below code is based on the book and in that loop is merged.
for (int i = 1; i < nSize; i++)
{
int nKey = arNumbers[i];
int j = i - 1;
while (j >= 0)
{
if (arNumbers[j] > nKey)
{
arNumbers[j + 1] = arNumbers[j];
}
else
{
break;
}
j--;
}
arNumbers[j + 1] = nKey;
}
The worst case of the algorithm arises when the array is sorted in the opposite direction. The order of growth for Insertion sort algorithm is THETA(n^2). I will not go in detail of the proof for this. You can see that there is a loop inside a loop. First loop has to iterate n times. Inside loop also has to iterate n times. Thats why its n*n = n^2..
Code is present at location https://github.com/harsha-kadekar/LibraryOfAlgorithms.git .
No comments:
Post a Comment