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

Insertion Sort

Merge Sort

Bubble Sort

Selection Sort

Quick Sort

C Program For Bubble Sort | C Programming

C Program For Selection Sort | C Programming

C Program For Quick Sort | C Programming

C Program For Merge Sort | C Programming

C Program for Insertion Sort | C Programming