INSERTION SORT - The Sorting Algorithm

INSERTION SORT

Insertion Sort Is A Type Of Sorting Algorithm. It Can Be Easily Explained Through The Example Of Deck Of Cards. In Insertion Sort, We Always Assume That The First Element Is Sorted. We Compare The First Element With The Next Element. If The Next Element Is Smaller Then We Swap Both The Elements. By This Way Elements At First 2 Indices Gets Sorted. Then We Compare The Element Present At The Next Index (ie, 3rd index) With First 2 Elements And Sort It. We Keep On Doing It Until All The Elements Of The Array/List Are Not Sorted. Insertion Sort Is More Efficient That Bubble And Selection Sort.

COMPLEXITY

Worst complexity: n^2

Average complexity: n^2

Best complexity: n

Space complexity: 1

CODE IMPLEMENTATION

C++

#include <iostream>
using namespace std;

int main() {
    int a[] = { 4,3,2,18,9,0,22,34,59,24,32};
    int size = (sizeof(a)/sizeof(a[0]));
    for(int i=1; i<size; i++)
    {
        int n =i;
        while(n!=0)
        {
            if(a[n]<a[n-1])
            {
                int temp = a[n];
                a[n] = a[n-1];
                a[n-1] = temp;
                
                n = n-1;
            }
            else
            {
                break;
            }
            
        }
    }
    
    for(int i=0; i<size; i++)
    {
       cout<<a[i]<<endl;
    }
}

JAVA

public class MyClass {
    public static void main(String args[]) {
      int a[] = { 4,3,2,18,9,0,22,34,59,24,32};
      int size = a.length;
      for(int i=1; i<size; i++)
      {
          int n = i;
          while(n!=0)
          {
              if(a[n]<a[n-1])
              {
                  int temp = a[n];
                  a[n] = a[n-1];
                  a[n-1] = temp;
                  
                  n = n-1;
              }
              else
              {
                  break;
              }
          }
      }
      
      for(int i: a)
      {
          System.out.println(i);
      }
    }
}

PYTHON

a = [4,3,2,18,9,0,22,34,59,24,32]
size = len(a)
for i in range(1,size):
    n = i
    while n!=0:
        if a[n]<a[n-1]:
            temp = a[n]
            a[n] = a[n-1]
            a[n-1] = temp
            n=n-1
        else:
            break
for i in a:
    print(i)