Insertion Sort

Insertion Sort

• An insertion sort is one that sorts a set of values by inserting values into an existing sorted file.
• Suppose that Iist[] is a list of n elements in memory. The insertion sort technique scans the list Iist[] from Iist[1] to list[n-1], inserting each element list[ k] into its proper position in the previously sorted sublist list[o], list[1], ..., list[n-1].

Illustration:

Let list[] be an array of 7 elements: 25, 15, 30, 9, 99, 20, 26.

Initial scenario,

Step 1: list[1]

Step 2: list[2]>list[1] , so position of elements remain same.

Step 3: list[3] is less than list[2.],list [1] and list[o], thus list[3] is inserted at list[o] position and others are shifted by one position.

Step 4: list[4]>list[3] , so position of elements remain same.

Step 5: list[5] is less than list[4], list[3], and list[2], so list[5] is inserted at the position of list[2] and others are shifted by one position.

Step 6: list[6] is less than list[5] and list[4], so list[6] is inserted at the position of list[4] and others are shifted by one position.

After step 6, the list is completely sorted.

Algorithm for insertion sort:

This algorithm sorts the array list with n elements. Let temp be a temporary variable to interchange the two values, k be the total

number of passes and j be another control variable for sorting.

Step1: Initialization,

Set k=1

Step2: For k=1 to (n-1)

Set temp=a.[k]

Set j=k-1

While temp<a[j] and (j>=0) perform the following steps

Set a[j+1]=a[j]

Set j=j-1

[End of loop structure]

Assign the value of temp to list[j+1]

[End of for loop structure]

Step3: Exit

Efficiency of insertion sort

Best Case: If the initial list is already sorted, then only one comparison is made on each pass, so that the complexity comes out to be O( n ).

Worst Case: If the initial list is sorted in reverse order, the total number of comparisons is:

1+z+3+...+k+(n-1)=n*(n-1)/2

so that the complexity comes out to be O(n^2).

Average Case: The average number of comparisons in the insertion sort (by considering all possible permutations of the input list) is O(n^2).

Note: The closer the list is in sorted order, the more efficient the insertion sort is.

C Program For Insertion Sort

#include <stdio.h>

void insertionSort(int arr[], int n)

{

    int i, key, j;

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

    {

         key = arr[i];

         j = i - 1;

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

        {

             arr[j + 1] = arr[j];

             j = j - 1;

         }

         arr[j + 1] = key;

     }

}





void printArray(int arr[], int n)

{

     int i;

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

         printf("%d  ", arr[i]);

     printf("\n");

}

int main()

{

     int arr[100],n,i;

    printf("How many elements are u going to enter?: ");

    scanf("%d",&n);

    printf("Enter %d elements:\n",n);

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

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

     insertionSort(arr, n);

    printf("\nThe sorted list is:\n");

    printArray(arr, n);

     return 0;

}

Related Posts

Bubble Sort

Merge Sort

Selection Sort

Quick Sort

C Program For Selection Sort | C Programming

C Program For Quick Sort | C Programming

C Program For Merge Sort | C Programming

C Program For Bubble Sort | C Programming

C Program for Insertion Sort | C Programming