Insertion sort in C, python

Insertion sort

       

         Insertion sort is a simple sorting technique. It is almost similar to the way we sort the playing cards. The whole array is split into two parts namely the sorted and unsorted. The elements from the unsorted array are placed at the correct position in the sorted array. The process continues until the entire unsorted array gets sorted out.

Procedure :

Explanation :

        Now let us consider an array [7,1,4,2]. We have to start from the element at index 1 and compare it with all the previous elements and arrange the elements in the sorted format. Continue the same process until we reach the last element, so that the entire array gets sorted.

For example, 

for the array [7,1,4,2], starting with the element 1 at index 1, compare it with previous element 7 ,as 1 is less than 7 swap the elements 1 and 7.

The array becomes [1,7,4,2].

Now move onto the next index position. Compare the element at index 2 with the the previous elements and arrange them accordingly.

Repeat the  same process till we are done with the last index.

Algorithm :

1. Start
2. Iterate from 1 to n-1.
3. Compare arr[i] with its previous element. 
4. If the element is smaller than its previous element, compare it with the elements before.
5. Swap the greater elements with the smaller elements to the correct sorted position.
6. End

Code :

C

#include<stdio.h>

int main(){

    int count,arr[10],temp;

    printf("Enter the number of elements in array : ");

    scanf("%d",&count);

    for(int i=0;i<count;i++){

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

    }

    for(int i=0;i<count;i++){

        for(int j=0;j<=i;j++){

            if(arr[j]>arr[i]){

                temp=arr[i];

                arr[i]=arr[j];

                arr[j]=temp;

            }

        }

        for(int k=0;k<count;k++){

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

        }

        printf("\n");

        

    }

    

}

Python

#insertion sort

l=list(map(int,input("Enter array elements : ").split()))

for i in range(len(l)):

l[i]=int(l[i])

def InsertionSort(l):

print("Insertion sort : ")

for i in range(len(l)):

for j in range(i):

if(l[i]<l[j]):

temp=l[i]

l[i]=l[j]

l[j]=temp

print(l)

InsertionSort(l)

Complexity:

• Time complexity(Best case)=O(n)
• Time complexity(Average case)=O(n*2)
• Time complexity(Worst case)=O(n*2)
• Best case : Insertion sort takes minimum time(O(n)) if the elements of the array are in sorted order.
• Worst case : Insertion sort takes maximum time(O(n*2)) if the elements of the array are in descending order.
• Space complexity=O(1)
• Uses : Insertion sort is used when the array needed to be sorted is very small. Insertion sort works efficiently when the input array is already sorted.