algorithm2

Insertion Sort

Insertion sort belongs to the O(n2) sorting algorithms. Unlike many sorting algorithms with quadratic complexity, it is actually applied in practice for sorting small arrays of data. For instance, it is used to improve quicksort routine. Some sources notice, that people use same algorithm ordering items, for example, hand of cards.

Algorithm

Insertion sort algorithm somewhat resembles selection sort. Array is imaginary divided into two parts - sorted one and unsorted one. At the beginning, sorted part contains first element of the array and unsorted one contains the rest. At every step, algorithm takes first element in the unsorted part and inserts it to the right place of the sorted one. When unsorted part becomes empty, algorithm stops. Sketchy, insertion sort algorithm step looks like this:

becomes

Algorithm Analysis

Dynamic Picture
![Insert Sort]
(http://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif)

My Code

public class  {
private int[] arr;
private int length;

public (int[] arr) {
    this.arr = arr;
    this.length = arr.length;
}

public int getLength() {
    return this.length;
}


public void mInsertSort() {
    for (int i = 1; i < arr.length; i++)
        
        if (arr[i] < arr[i - 1]) {
            int temp = arr[i];
            //record the position where should be replaced by another number
            int j = i;
            //condition to decide the numbers which should be move to left
            while (j > 0 && arr[j - 1] > temp) {
                arr[j] = arr[j - 1];
                j--;
            }
            //replace the unsorted number arr[i]
            arr[j] = temp;
        }
}

public void printout() {
    for (int num:arr) {
        System.out.print(num + " ");
        }
    System.out.println();
    }
}


public class testInsertSort {
    public static void main(String[] args){
        int[] arr=new int[] {3,6,2,20,0};
        insertSort sort=new insertSort(arr);
        sort.mInsertSort();
        sort.printout();
    }
}