Insertion Sorting

Explanation of inserting Sorting

Consider that when we have a set of pocker cards in our hands, how will we sort them? Normally, we will start with the third card, and find a right place to insert it in. This is how insertion sort works.

To start with, assuming we have this set of numbers and we want to sort it in inscending order:

The original set of number: 3,6,3,5,2,1,7

The result set of number: 1,2,3,3,5,6,7

Firstly, we can consider that the first number is sorted, so we take the second number. To find the right position of 6, we need to compare it from the last number in the sorted list (which is the first number), if the number is larger than it, then we swap them. Otherwise, we move foward in the sorted list and compare it with that number. Because there is no next number in the sorted list in this condition, we will finish swap and 6 has find its position.

Repeat to do the process n(the length of array) times, the whole array is sorted because all elements are inserted into correct position.

Pros and Cons of inserting Sorting

Pros

1. Negligible storage space is used. (Only a temp variable)
2. It is stable.

   Cons

3. The time complexity is O(n²), which is bad.

   Implementation

   Java

public class insertSort {
    public static void sort(Comparable[] list){
        int len = list.length;
        for(int i =1;i<len;i++){
            for(int j=i;j>0;j--){
                if(list[j].compareTo(list[j-1]) < 0){
                    swap(list,j,j-1);
                }
                else{
                    break;
                }
            }
        }
    }
    private static void swap(Object [] list,int i,int j){
        Object temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
    public static void main(String[] args){
        Integer[] list = {3,6,3,5,2,1,7};
        sort(list);
        for(int num:list){
            System.out.println(num);
        }
    }
}

Python

def insertSort(list):
    for i in range(1,len(list)):
        for j in range(i,0,-1):
            if list[j-1] > list[j]:
                temp = list[j]
                list[j] = list[j-1]
                list[j-1] = temp
            else:
                break
    return list