/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package insertionlistsort;

/**
 *
 * @author mweya
 */
public class Insertionlistsort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int[] toSort = {15,7,32,6,92,74,3};
        System.out.println("Insertion sort:\n"+arrToString(toSort)+"\n"+arrToString(properInsertionSort(toSort))+"\n");
        int[] toSort1 = {15,7,32,6,92,74,3};
        System.out.println("Bubble sort:\n"+arrToString(toSort1)+"\n"+arrToString(bubbleSort(toSort1))+"\n");
        int[] toSort2 = {15,7,32,6,92,74,3};
        System.out.println("Selection sort:\n"+arrToString(toSort2)+"\n"+arrToString(selectionSort(toSort2))+"\n");
        int[] toSort3 = {15,7,32,6,92,74,3};
        System.out.println("Insertion list sort:\n"+arrToString(toSort3)+"\n"+arrToString(insertionListSort(toSort3))+"\n");
        int[] toSort4 = {15,7,32,6,92,74,3};
        System.out.println("Slightly more efficient Insertion sort:\n"+arrToString(toSort4)+"\n"+arrToString(slightlyMoreEfficientInsertionSort(toSort4))+"\n");
      //  int[] toSort5 = {15,7,32,6,92,74,3};
      //  System.out.println("Pretty ridiculous Insertion Sort:\n"+arrToString(toSort5)+"\n"+arrToString(prettyRidiculousInsertionSort(toSort5)));
    }
    
    public static int[] selectionSort(int[] arr) {
        int i = 0;
        int j = 0;
        int min = 0;
        int minpos = 0;
        while (j<arr.length) {
            i = j;
            min = arr[j];
            while(i<arr.length) {
                // get minimum
                if (min>arr[i]) {
                    min = arr[i];
                    minpos = i;
                }
                i = i+1;
            }
            if (min<arr[j]) {
                int temp = arr[j];
                arr[j] = min;
                arr[minpos] = temp;
            }
            j = j+1;
        }
        return arr;
    }
    
    public static int[] bubbleSort(int[] arr) {
        // Get smallest
        int j = 0;
        int i = 0;
        while (j<arr.length) {
            while (i<arr.length) {
                if(arr[i]>arr[j]) {
                    // Swap
                    int temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
                i = i+1;
            }
           i = 0; 
           j = j+1;
        }
        return arr;
    }
    
   // public static int[] insertionListSortmk2(int[])
    
    public static int[] insertionListSort(int[] arr) {
            int[] newarr = new int[arr.length];
            int j = 0; 
            int i = 0;
            while(j<arr.length) {
                newarr[j] = arr[j];
                i = j;
                while(i>0) {
                    if (newarr[i]<newarr[i-1]) {
                        int temp = newarr[i];
                        newarr[i] = newarr[i-1];
                        newarr[i-1] = temp;
                    }
                    i = i-1;
                }
                j = j+1;
            }
            return newarr;
    }
    
    public static int[] properInsertionSort(int[] arr) {
        int i = 1;
        int j = 0;
        while (i<arr.length) {
            j = i;
            while (j>0) {
                if (arr[j]<arr[j-1]) {
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    
                }
                j = j-1;
            }
            i = i+1;
        }
        return arr;
    }
    
    public static int[] slightlyMoreEfficientInsertionSort(int[] arr) {
        int i = 1;
        int j = 0;
        while (i<arr.length) {
           int temp = arr[i];
           j = i-1;
           while (j>=0 && arr[j]>temp) {
               arr[j+1] = arr[j];
               j = j-1;
           } 
           arr[j+1] = temp;
           i = i+1;
        }
        return arr;
    }
    
    /*public static int[] prettyRidiculousInsertionSort(int[] arr) {
        // citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.278.6654&rep=rep1&type=pdf
        int i = 1;
        int j = 1;
        if(a[i]<a[i-1]) {
            // Eh?
            if(a[i]>a[0]) {
                j = 0;
                
            }
        }
    }*/
    
    public static String arrToString(int[] arr) {
        int j = 0;
        String out = "";
        while (j<arr.length) {
            out = out+arr[j]+" ";
            j = j+1;
        }
        return out;
    }
}