/**
 * An implementation of InsertionSort
 *
 * Main.java
 *
 * @author Stefan Löwen <stefan.loewen@googlemail.com>
 *
 */

public class Main {
    public static void main(String[] args) {
        int[] array = { 6,5,4,3,2,1 };

        /*
         * print the initial array
         */
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ", ");
        }
        System.out.println();


        /*
         * sort the array
         * ala Wikipedia
         */
        /*
        for (int i = 1; i < array.length; i++) {
            int clipboard = array[i]; // Lesezugriff

            int j = i;
            while (j>0 && array[j-1]>clipboard) {   // 1 Vergleich
                array[j] = array[j-1];  // Tauschoperation
                j--;
            }

            array[j] = clipboard; // Schreibzugriff
        }
        */

        /*
         * sort the array
         * using bubbles
         */
        int tauschOps = 0;
        int vergleichOps = 0;

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

            /* bubble it up */
            while (true) {
                if (! (j>0)) {
                    break;
                }

                vergleichOps++;

                if (! (array[j-1]>array[j])) {
                    break;
                }

                /* do the switch */
                int clipboard = array[j];
                array[j] = array[j-1];
                array[j-1] = clipboard;
                tauschOps++;

                j--;
            }
        }
        System.out.println("#Vergleich:\t" + vergleichOps);
        System.out.println("#Tausch:\t" + tauschOps);

        /*
         * print the sorted array
         */
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ", ");
        }
    }
}

/*
 * Laufzeitanalyse
 * ---
 * 2 Elemente:
 *  BestCase:
 *      1 Vergleich
 *      0 Tausch
 *  WorstCase:
 *      1 Vergleich
 *      1 Tausch
 * ---
 * 3 Elemente:
 *  BestCase:
 *      2 Vergleich
 *      0 Tausch
 *  WorstCase:
 *      3 Vergleich
 *      3 Tausch
 * ---
 * 4 Elemente:
 *  BestCase:
 *      3 Vergleich
 *      0 Tausch
 *  WorstCase:
 *      6 Vergleich
 *      6 Tausch
 * ---
 * 5 Elemente:
 *  BestCase:
 *      4 Vergleich
 *      0 Tausch
 *  WorstCase:
 *      10 Vergleich
 *      10 Tausch
 * ---
 * 6 Elemente:
 *  BestCase:
 *      5 Vergleich
 *      0 Tausch
 *  WorstCase:
 *      15 Vergleich
 *      15 Tausch
 */