Insertion Sort Program in C

How Insertion Sort works in C

In this technique we pick an Element and then insert it at the appropriate position  in ascending and descending order.

Insertion Sort

Insertion Sort in C

If we have n element then it requires (n-1) pass to sort.  In each pass we insert current element at appropriate position so that the element in current  range are in order.

  • In insertion sort A Sublist (or sorted array) is maintained which is always sorted. this algorithm  is not suitable for large data sets.
  • The average and worst complexity of an insertion sort is O(n2).
  • This is less efficient on list containing more number of elements.
  • The main advantage of  the insertion sort it is moderity.it is also exhibits a good performance.
Insertion Sort Working in C Intro

Execution of Insertion Sort in C

Pass 1- First of all to given the unsorted array.In  this array the first element should be fixed.so the compares second and third element.In this array  5>2 then they are swap .

Pass 2- In this array algorithm compares the next two element and arrange the element with their position.

Pass 3- the finally array is Sorted.

Insertion Sort in C

Algorithm of Insertion Sort

Insertion Sort-(A,N): A is an array with N element.

Step 1- I=1;

Step 2- Repeat Step 3 and 5 While I<N.

Step 3-temp=A[I],J=I-1;

Step 4-Repeat While J>=0 and  temp<A[J]

                A[J+1]=A[J] and J=J-1

Step 5-A[j+1]=temp,I=I=1

Step 6-Exit

Code of Insertion Sort

#include <stdio.h>

/* Function to print array */
void display(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Main function to run the program
int main()
{
int array[] = {5, 3, 1, 9, 8, 2, 4,7};
int size = sizeof(array)/sizeof(array[0]);

printf("Before Insertion sort: \n");
display(array, size);

int i, target, j;
for (i = 1; i < size; i++)
{
target = array[i];
j = i - 1;

/* Here the elements in b/w arrary[0 to i-1]
which are greater than target are moved
ahead by 1 position each*/
while (j >= 0 && array[j] > target)
{
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = target;
}
printf("After Insertion sort: \n");
display(array, size);
return 0;
}
#include <stdio.h>

// Here we are implementing Insertion sort
void insertionSort(int array[], int size)
{
int i, target, j;
for (i = 1; i < size; i++)
{
target = array[i];
j = i - 1;

/* Here the elements in b/w arrary[0 to i-1]
which are greater than target are moved
ahead by 1 position each*/
while (j >= 0 && array[j] > target)
{
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = target;
}
}

/* Function to print array */
void display(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Main function to run the program
int main()
{
int array[] = {5, 3, 1, 9, 8, 2, 4,7};
int size = sizeof(array)/sizeof(array[0]);

printf("Before Insertion sort: \n");
display(array, size);

insertionSort(array, size);

printf("After Insertion sort: \n");
display(array, size);
return 0;
}

Output

Before Insertion sort:
5 3 1 9 8 2 4 7
After Insertion sort:
1 2 3 4 5 7 8 9 

Advantages and Disadvantages of Insertion Sort

Advantages

  1. It is simple, small and easy to write.
  2. It doesn’t use a lot of overhead.
  3. It uses in place sorting, thus O(1) space requirements
  4. If data is almost sorted, then it can be very fast approaching O(n) and faster than Merge sort

    (for sorted data, and small N, else merge sort is faster)

  5. Efficient for (quite) small data sets.

Disadvantages

  1. Poor average time complexity of O(n2)
  2. If there are many elements then it is inefficient
  3. Many items needs to be shifted to one insertion

Properties

  1. You will encounter the best case if the data is already or nearly sorted
  2. It will give worst case results if the array is sorted in opposite order as required
Insertion sort in C meme

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting