package com.qiusongde;

import edu.princeton.cs.algs4.In;

import edu.princeton.cs.algs4.StdOut;

public class InsertionHalfExchange {

    public static void sort(Comparable[] a) {

        int N = a.length;

        for(int i = 1; i < N; i++) {

            Comparable temp = a[i];

            int j = i;

            while(j > 0 && less(temp, a[j-1])) {

                a[j] = a[j-1];

                j--;

            }

            a[j] = temp;

//            show(a);

        }

    }

    private static boolean less(Comparable v, Comparable w) {

        return v.compareTo(w) < 0;

    }

    private static void exch(Comparable[] a, int i, int j) {

        Comparable t = a[i];

        a[i] = a[j];

        a[j] = t;

    }

    private static void show(Comparable[] a) {

        //print the array, on a single line.

        for(int i = 0; i < a.length; i++) {

            StdOut.print(a[i] + " ");

        }

        StdOut.println();

    }

    public static boolean isSorted(Comparable[] a) {

        for(int i = 1; i < a.length; i++) {

            if(less(a[i], a[i-1]))

                return false;

        }

        return true;

    }

    public static void main(String[] args) {

        //Read strings from standard input, sort them, and print.

        String[] a = In.readStrings();

        show(a);

        sort(a);

        assert isSorted(a);

        show(a);

    }

}

S O R T E X A M P L E

O S R T E X A M P L E

O R S T E X A M P L E

O R S T E X A M P L E

E O R S T X A M P L E

E O R S T X A M P L E

A E O R S T X M P L E

A E M O R S T X P L E

A E M O P R S T X L E

A E L M O P R S T X E

A E E L M O P R S T X

A E E L M O P R S T X 

package com.qiusongde;

import edu.princeton.cs.algs4.Shell;

import edu.princeton.cs.algs4.StdOut;

import edu.princeton.cs.algs4.StdRandom;

public class SortCompare {

    public static double timeRandomInput(String alg, int N, int T) {

        double total = 0.0;

        Double[] a = new Double[N];

        for(int t = 0; t < T; t++) {

            for(int i = 0; i < N; i++)

                a[i] = StdRandom.uniform();

            total += time(alg, a);

        }

        return total;

    }

    public static double time(String alg, Double[] a) {

        Stopwatch timer = new Stopwatch();

        if(alg.equals("Selection"))

            Selection.sort(a);

        if(alg.equals("Insertion"))

            Insertion.sort(a);

        if(alg.equals("InsertionHalfExchange"))

            InsertionHalfExchange.sort(a);

        if(alg.equals("Shell"))

            Shell.sort(a);

        return timer.elapsedTime();

    }

    public static void main(String[] args) {

        String alg1 = "Insertion";

        String alg2 = "InsertionHalfExchange";

        int N = 1000;

        int T = 1000;

        double t1 = timeRandomInput(alg1, N, T);

        double t2 = timeRandomInput(alg2, N, T);

        StdOut.printf("For %d random Doubles %d trials\n", N, T, alg1);

        StdOut.printf("%s is %.1fs %s is %.1fs", alg1, t1, alg2, t2);

    }

}

For 1000 random Doubles 1000 trials

Insertion is 1.1s InsertionHalfExchange is 0.5s