Problem Question
Write a program to implement Insertion Sort.
Explanation of Problem
Insertion Sort is a simple sorting algorithm, used extensively when learning Algorithms, Data Stuctures, and Space-Time Complexity. However, due to the high order of complexity it incurs to sort a list, makes it impractical for large applications.
In insertion sort, the program iterates through the list of values as many times as the number of items in the list. It compares the element with all elements placed previous to it, and if it finds that the previous element to be greater than the current, it swaps the two. If the previous element is smaller than the current element, it assumes the curerent element is correctly placed and breaks to next iteration.
Thus, insertion sort picks an element, and tries to put it in best possible position for the partial list it is working with. Each iterarion, it expands its scope and works with a larger list thereby incrementally building a sorted list.
To understand insertion sort better, consider a list of 5 numbers, [5, 3, 2, 1, 4]. Following is how insertion sort would sort the list.
Unlike bubble sort, we can notice that the insertion sort algorithm stops after the list is sorted. This makes it more eficient. On smaller list insertion sot works pretty well, however with increasing size, the algorithm takes more time. If the list is already sorted, the overal time taken by algorithm decreases, because in each iteration the element will be compared only once and the program will skip to next iteration, instead of comparing all elements in each iteration.
Code
#include <stdio.h>
/**@Title: SortingAlgorithms v1.1.c*
*@Language: ANSI C*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Toxifier*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 27-04-2015*
*/
#include <stdio.h>
int main()
{
int userChoice, outerLoop, innerLoop, exchangeSpace, lengthNumberList = 0, originalNumberList[25], sortedNumberList[25];
printf ("Welcome to SortingAlgorithms v1.1\n");
printf ("Made by Toxifier\n");
do
{
printf ("\n1: Add an element to the list\n");
printf ("2: Display Original List\n");
printf ("3: Perform Insertion Sort\n");
printf ("4: Empty List\n");
printf ("5: Exit\n");
printf ("Enter your choice: ");
scanf ("%d", &userChoice);
switch (userChoice)
{
case 1:
if (lengthNumberList >= 25)
{
printf ("\nArray Full\n");
}
else
{
printf ("\nEnter the value: ");
scanf ("%d", &originalNumberList[lengthNumberList]);
sortedNumberList[lengthNumberList] = originalNumberList[lengthNumberList];
lengthNumberList++;
}
break;
case 2:
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
printf ("\nOriginal List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", originalNumberList[outerLoop]);
}
}
break;
case 3:
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
outerLoop = 1;
while ( outerLoop < lengthNumberList )
{
innerLoop = outerLoop;
while (innerLoop > 0 && sortedNumberList[innerLoop - 1] > sortedNumberList[innerLoop])
{
exchangeSpace = sortedNumberList[innerLoop - 1];
sortedNumberList[innerLoop - 1] = sortedNumberList[innerLoop];
sortedNumberList[innerLoop] = exchangeSpace;
innerLoop--;
}
outerLoop++;
}
printf ("\nSorted List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", sortedNumberList[outerLoop]);
}
}
break;
case 4:
lengthNumberList = 0;
break;
case 5:
printf ("Thank You for using SortingAlgorithms v1.1\n");
printf ("Made by Toxifier\n");
break;
default:
printf ("\nWrong Choice!\n");
break;
}
}
while (userChoice != 5);
system("pause");
return 0;
}
Explanation of Code
#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H
int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.
printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.
scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.
int userChoice, outerLoop, innerLoop, exchangeSpace, lengthNumberList = 0, originalNumberList[25], sortedNumberList[25]; -> Here we define the variables we are going to use in our program.
userChoice is used for the switch and do-while loop. The program is menu driven to allow user to change the array and move in any order they wish to.
outerLoop, innerLoop are the loop variables and exchangeSpace is the temporary space which we would use during value exchange operation.
lengthNumberList is used to track the final position of the arrays. originalNumberList[25], sortedNumberList[25] are the arrays which will hold the user input and the sorted list, respectively.
if (lengthNumberList >= 25)
{
printf ("\nArray Full\n");
}
else
{
printf ("\nEnter the value: ");
scanf ("%d", &originalNumberList[lengthNumberList]);
sortedNumberList[lengthNumberList] = originalNumberList[lengthNumberList];
lengthNumberList++;
}
This is the first case of the program where the user inputs the array values. Since the array is defined with maximum length of 25, an error is thrown to the user and they are not allowed to add more values to the list once the limit is reached.
If the array has enough space though, the user can proceed further and input a value to the array, which will get stored at the end of the list. Every user input is copied to the sortedNumberList as well, so that original list is inatct for future reference.
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
printf ("\nOriginal List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", originalNumberList[outerLoop]);
}
}
This is the second case of our program which is used to display the list created by the user so far. The code iterates through the array, originalNumberList and prints each element.
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
outerLoop = 1;
while ( outerLoop < lengthNumberList )
{
innerLoop = outerLoop;
while (innerLoop > 0 && sortedNumberList[innerLoop - 1] > sortedNumberList[innerLoop])
{
exchangeSpace = sortedNumberList[innerLoop - 1];
sortedNumberList[innerLoop - 1] = sortedNumberList[innerLoop];
sortedNumberList[innerLoop] = exchangeSpace;
innerLoop--;
}
outerLoop++;
}
printf ("\nSorted List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", sortedNumberList[outerLoop]);
}
}
This is the third case of our program where we have the probem statement addressed - implementing the insertion sort algorithm. We first check the length of the array, and proceed with sorting only if there are any elements. The outer loop is used to iterate through the list as many times as the number of elements in the list. The inner loop compares each element of the list to its immediate neighbor as the loop traverses through the list. The inner loop only works until the immediate neighbor is geater, else the loops ends and the contorl comes back to outer loop. Whenever the immediate neighbor of the element is greater, the two values are swapped. Once the list is sorted, it is displayed.
Talking a bit more about the two loops, the outer loop traverses the list from second element onwards, left to right. The inner loop traverses the list right to left, starting from the element pointed to by the outer loop, and runs only if the element to the left is greater, else it breaks assuming the current element is already placed correctly. (Sometimes I wonder why don't they call it assumption sort, but well! :D ).
It is important to note that we are working on the sortedNumberList array insted of the originalNumberList array. The idea is to preserve the original list for any reference.
When implementing insertion sort, this code is good enough to solve the problem. Rest of the code in our C program is only having a few useful additions which helps in easy execution of the program, making it more user friendly.
lengthNumberList = 0; -> This is the fourth case where we reset the lengthNumberList variable, which tracks the last element of the array. This helps in giving the user ability to redo any operation, without the need of closing and starting the program again.
printf ("Thank You for using SortingAlgorithms v1.1\n");
printf ("Made by Toxifier\n");
This is the fifth case statement, which allows the user to safely exit the program.
default:
printf ("\nWrong Choice!\n");
When using the case statement, it is important to use the break keyword at the end of each case to avoid the program from falling through the next case. It is also important to note the default case, which is important to handle any wrong values in the swithc-case logic.
system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.
Output(s)
Download Source Code
