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.

The inspiration has been taken from playing cards

Insertion Sort
Time Complexity O(n2)
Best Case Ω(n)
Worst Case O(n2)
Aux. Space Complexity O(1)
Best case when Array is already sorted
Worst case when Array is reverse sorted

Insertion Sort in C

Insertion sort is just like how to sort playing cards in your hands. You pick one card and try to place that card in its correct position.

The array is kind of split into a sorted part and an unsorted part. A value from the unsorted part is picked and placed into its correct position in the sorted part.

Below are examples on how you can do the same.

Insertion Sort Working in C Intro

Execution of Insertion Sort in C

Insertion Sort in C

Approach of Insertion Sort

  • Iterate over the whole array, picking each item in the array once iteratively
  • Call this picked item key
  • If this key item is smaller than its predecessor, compare it to the item before
  • To make space for this swapped item move items greater than key one position right
  • Keep doing this until you find a smaller element than key element.

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[] = {8, 6, 4, 20, 24, 2, 10, 12}; 
    int size = sizeof(array)/sizeof(array[0]); 

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

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

/* Here the elements in b/w arrary[0 to i-1]
which are greater than key are moved
ahead by 1 position each*/
while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j = j - 1; } // placing element at its correct position array[j + 1] = key; } printf("After Insertion sort: \n"); display(array, size); return 0; } // Time Complexity : O(n^2) // Auxiliary Space : O(1)

Output

Before Insertion sort: 
8 6 4 20 24 2 10 12 
After Insertion sort: 
2 4 6 8 10 12 20 24 
#include<stdio.h>

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

/* Here the elements in b/w arrary[0 to i-1]
which are greater than key are moved
ahead by 1 position each*/
while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j = j - 1; } array[j + 1] = key; } } /* 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; } // Time Complexity : O(n^2)
// Auxiliary Space : O(1)

Output

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

Some facts about Insertion sort

  • Time Complexity: O(n2)
  • Auxiliary Space: O(1)
  • Best Case: Ω(n), when the array is already sorted
  • Worst Case: Θ(n^2), when the array is reverse sorted.
  • Algorithmic Paradigm: Incremental Approach
  • Sorting In Place: Yes
  • Stable: Yes

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 a large number of 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 the opposite order as required
Insertion sort in C meme

Time Complexity
For Linear Search

Best

Ω(n)

Average

O(n2)

Worst

Θ(n2)

Space Complexity

O(1)

Time Complexity
For Linear Search

Best

O(n)

Average

O(n2)

Worst

Θ(n2)

Space Complexity

O(1)

Quiz time

Quiz Time

Question 1. How many passes does an insertion sort algorithm consist of? –

  1. N-1
  2. N-2
  3. N
  4. N2

(Flipkart – HackerEarth Test)

Explanation: An insertion algorithm consists of N-1 passes when an array of N elements is given.

Question 2. For the following question, how will the array elements look like after second pass?

35, 7, 64, 57, 28, 14

  • 8, 21, 32, 34, 51, 64
  • 8, 32, 34, 51, 64, 21
  • 8, 34, 51, 64, 32, 21
  • 8, 34, 64, 51, 32, 21

(TCS NQT)

Original Array : 

35, 7, 64, 57, 28, 14

After Pass 1 : 7, 35, 64, 57, 28, 14

After Pass 2 : 7, 35, 64, 57, 28, 14 (no change)

After Pass 3 : 7, 35, 57, 64, 28, 21 (no swapping)

After Pass 4 : 7, 28, 35, 57, 64, 14 (no swapping)

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