Sorting algorithm 3: Insertion Sort

In this tutorial we shall go through the concept of insertion sort and how to implement in C language.

1. We need to take 2 loops.

2. Outer Loop will loop through all the elements in the array list. Here we consider first element as the smallest element.

3. Inner loop is used to check for that if there is any smallest element present, then the element we considered in the outer loop.

4. If present, then we shall swap the element to the index of the outer loop.

Here in the first pass, the smallest element will be in the first position. Second pass, second smallest element will be in the 2nd position and so on.

#include<stdio.h>

void print_array(int array[], int length)
{
	int index = 0;

	printf("The sorted array is \n");

	for(index = 0 ; index < length ; index++)
	{
		printf("%d\n",array[index] );
	}
}
void swap (int *num_1, int *num_2)
{
	int temp = *num_1;
	*num_1 = *num_2;
	*num_2 = temp;
}

void insertion_sort (int array[], int length)
{
	int outer_loop_index = 0;
	int inner_loop_index = 0;
	int temp_variable = 0;
//outer for loop is to iterate through all the elements
	for(outer_loop_index = 1; outer_loop_index < length ; outer_loop_index ++)
	{
		//inner for loop is used to check if there is element smaller than the index of outer arrray.
		for(inner_loop_index = outer_loop_index - 1 ; inner_loop_index >= 0 ; inner_loop_index --)
		{
			if(array [inner_loop_index + 1] < array[inner_loop_index])
			{
				swap(&array[inner_loop_index + 1], &array [inner_loop_index]);
			}
		}
	}
}

int main()
{
	int length = 0;
	int array[100];
	int index = 0;

	printf("Enter the length of the array\n");
	scanf("%d", &length);

	printf("Enter the array elements of length %d\n", length);

	for (index = 0; index < length; ++index)
	{
		scanf("%d", &array[index]);
	}

	insertion_sort(array, length);

	print_array(array, length);


}

3.5 Output of the program

Enter the length of the array
5

Enter the array elements of length 5
5
4
3
2
1

The sorted array is
1
2
3
4
5

3.6 Time complexity analysis of Insertion Sort

As we are using 2 for loops, the time complexity is O(n^2).