Data Structures (insertion sort in data structures)

 Insertion Sort

👉 Insertion sort is the simple sorting algorithm which is commonly used in the daily lives while ordering a deck of cards. 

👉 In this algorithm, we insert each element onto its proper place in the sorted array. 

👉 This is less efficient than the other sort algorithms like quick sort, merge sort, etc.

Technique:

👉 Consider an array A whose elements are to be sorted. Initially, A[0] is the only element on the sorted set. 

👉 In pass 1, A[1] is placed at its proper index in the array.

👉 In pass 2, A[2] is placed at its proper index in the array. Likewise, in pass n-1, A[n-1] is

placed at its proper index into the array.

👉 To insert an element A[k] to its proper index, we must compare it with all other elements i.e. A[k-1], A[k-2], and so on until we find an element A[j] such that, A[j]<=A[k].

👉 All the elements from A[k-1] to A[j] need to be shifted and A[k] will be moved to A[j+1].

Complexity

Complexity     Best Case     Average Case     Worst Case

Time                 Ω(n)             θ(n 2 )                 o(n 2 )

Space                o(1)

Algorithm

Step 1: Repeat Steps 2 to 5 for K = 1 to N-1

Step 2: SET TEMP = ARR[K]

Step 3: SET J = K ? 1

Step 4: Repeat while TEMP <=ARR[J]

SET ARR[J + 1] = ARR[J]

SET J = J ? 1

[END OF INNER LOOP]

Step 5: SET ARR[J + 1] = TEMP

[END OF LOOP]

Step 6: EXIT

Working of Insertion Sort

Suppose we need to sort the following array.

Initial array

1. The first element in the array is assumed to be sorted. Take the second element and store it separately in key.
   
   Compare key with the first element. If the first element is greater than key, then key is placed in front of the first element.

   

   If the first element is greater than key, then key is placed in front of the first element.

2. Now, the first two elements are sorted.
   
   Take the third element and compare it with the elements on the left of it. Placed it just behind the element smaller than it. If there is no element smaller than it, then place it at the beginning of the array.

   

   Place 1 at the beginning

3. Similarly, place every unsorted element at its correct position.

   

   Place 4 behind 1

   

   Place 3 behind 1 and the array is sorted

Implementation of Insertion Sort:

#include <stdio.h>

int main(void)

{

    int a[10],n, i, j,key;

    printf("Enter number of elements\n");

    scanf("%d", &n);

    printf("Enter the elements in to an array \n");

    for (i = 0; i < n; i++)

    {

        printf("a[%d]=",i);

        scanf("%d",&a[i]);

    }

    for (i = 1; i < n; i++)

    {

        key=a[i];

        j = i-1;

        while (j >= 0 && a[j] > key)

        {

            a[j+1] = a[j];

            j = j - 1;

        }

        a[j+1]=key;

    }

    printf("Sorted list in ascending order:\n");

    for (i = 0; i < n; i++)

    {

        printf("a[%d]=%d\n", i,a[i]);

    }

   

}

OUTPUT:

Enter number of elements
5
Enter 5 integers
9 8 6 3 1
Sorted list in ascending order:
1
3
6
8
9