Insertion Sort in c programming | c programming insertion sort

 In this article, we will learn about an sorting algorithm called insertion sort. Insertion sort is the sorting algorithm which used to sort the values of an array in increasing or decreasing order (ascending or descending order).

Insertion sort in c without function

In insertion sort we divide the array in to two subarrays or sub-list and the first subarray will be sorted and the next array is unsorted. We first assume that the first element in the array is sorted and run the loop from the second element, each time through the loop we assume a key element in the array and compare that key element with all the elements in the first sorted subarray and place the key in the appropriate position in an array.

Algorithm:-

1. Start.
2. First assume the first element of an array to be sorted.
3. Input the size of array from user.
4. Declare the array of integer of size n and input the array elements from user.
5. Run the loop from the second element and assign k as arr[i].
6. Place k in the appropriate place in the sorted subarray.
7. Print the result.
8. Stop.

For Example:-

4 2 1 3 5

1. Here first, we will assume 4 is sorted.
2. Take k as 2 and compare k with the sorted subarray and as you can see k is less than 4 therefore place 2 in front of 4.
3. Again compare k which is 1 with the sorted subarray that is 2 and 4, as you can see 1 is less compare to both 2 and 4 so place 1 in the first place.
4. Keep doing the same procedure and after traversing the array. we get the result as 

1 2 3 4 5

Insertion sort in C programming:-

#include <stdio.h>

int main()
{
    int n;
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    int arr[n]; // defining array of integers of size n
    for(int i=0; i<n; i++) {
        scanf("%d", &arr[i]);
    }
    
    printf("\nBefore performing insertion sort: ");
    for(int i=0; i<n; i++) {
        printf("%d\t", arr[i]);
    }
    
    for(int i=1; i<n; i++) {
        int k = arr[i]; // key to be compared with other elements
        int j = i-1;
        
        while(j>=0 && arr[j]>k) {
            arr[j+1] = arr[j]; // replacing if array of 
            j--;
        }
        arr[j + 1] = k;
        
    }
    
    printf("\nAfter performing insertion sort: ");
    for(int i=0; i<n; i++) {
        printf("%d\t", arr[i]);
    }

    return 0;
}

Output:-
Enter the number of elements: 3
122 231 11

Before performing insertion sort: 122   231     11
After performing insertion sort: 11     122     231

Enter the number of elements: 5
4 8 6 1 9

Before performing insertion sort: 4     8       6       1       9
After performing insertion sort: 1      4       6       8       9