package sorting;

import java.util.*;

class Demo {
    public static void main(String[] args) {
        runSort(new SelectionSort(), "Selection Sort");
        runSort(new InsertionSort(), "Insertion Sort");
        runSort(new MergeSort(), "Merge Sort");
        runSort(new QuickSortBad(), "Not So Good Quick Sort");
        runSort(new BubbleSort(), "Bubble Sort");
        runSort(new BetterBubbleSort(), "Better Bubble Sort");
        runSort(new QuickSort(), "Better Quick Sort");
    }

    static void runSort(Sort sorter, String sortName) {
        System.out.println("\n" + sortName + "\n");
        // Use 25600 for Selection, Insertion and Bubble
        // Use 409600 for Mergesort and Quick Sort (fast)
        // Use 6400 for Bad Quick Sort
        for (int SIZE = 100; SIZE <= 12800; SIZE *= 2) {
            long start, end;
            long elapsed1 = 0, elapsed2 = 0, elapsed3 = 0;
            Comparable[] a = new Integer[SIZE];

            // sorted input
            for (int i = 0; i < SIZE; i++)
                a[i] = new Integer(i);
            start = System.currentTimeMillis();
            sorter.sort(a);
            end = System.currentTimeMillis();
            elapsed1 = end - start;
            checkSort(a);

            // reverse sorted input
            for (int i = 0; i < SIZE; i++)
                a[i] = new Integer(SIZE - i);
            start = System.currentTimeMillis();
            sorter.sort(a);
            end = System.currentTimeMillis();
            elapsed2 = end - start;
            checkSort(a);

            // random input
            Random r = new Random();
            for (int i = 0; i < SIZE; i++)
                a[i] = new Integer(r.nextInt(SIZE));
            start = System.currentTimeMillis();
            sorter.sort(a);
            end = System.currentTimeMillis();
            elapsed3 = end - start;
            checkSort(a);

            System.out.println("size: " + SIZE + "\tsorted: " + elapsed1
                    + "\treverse: " + elapsed2 + "\trandom: " + elapsed3);
        }
    }

    static void checkSort(Comparable[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i].compareTo(array[i + 1]) > 0) {
                System.out.println("array not sorted array[" + i + "]="
                        + array[i] + " array[" + (i + 1) + "]=" + array[i + 1]);
            }
        }
    }
}

interface Sort {
    public void sort(Comparable[] a);
}

class SelectionSort implements Sort {
    public void sort(Comparable[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++)
                if (a[j].compareTo(a[min]) < 0)
                    min = j;
            Comparable tmp = a[min];
            a[min] = a[i];
            a[i] = tmp;
        }
    }
}

class InsertionSort implements Sort {
    public void sort(Comparable[] a) {
        for (int p = 1; p < a.length; p++) {
            Comparable tmp = a[p];
            int j;
            for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--)
                a[j] = a[j - 1];
            a[j] = tmp;
        }
    }
}

class BubbleSort implements Sort {
    public void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - 1; j++) {
                if (a[j].compareTo(a[j + 1]) > 0) {
                    Comparable tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                }
            }
        }
    }
}

class BetterBubbleSort implements Sort {
    public void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            boolean swap = false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j].compareTo(a[j + 1]) > 0) {
                    Comparable tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                    swap = true;
                }
            }
            if (!swap)
                break;
        }
    }
}

class MergeSort implements Sort {
    public void sort(Comparable[] a) {
        mergeSort(a, 0, a.length - 1);
    }

    static void mergeSort(Comparable[] a, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(a, left, center);
            mergeSort(a, center + 1, right);
            merge(a, left, center, right);
        }
    }

    static void merge(Comparable[] a, int left, int center, int right) {
        int size = right - left + 1;
        Comparable[] tmp = new Comparable[size];
        int i = 0;
        int leftPos = left;
        int rightPos = center + 1;
        while (leftPos <= center && rightPos <= right)
            if (a[leftPos].compareTo(a[rightPos]) <= 0)
                tmp[i++] = a[leftPos++];
            else
                tmp[i++] = a[rightPos++];
        while (leftPos <= center)
            tmp[i++] = a[leftPos++];
        while (rightPos <= right)
            tmp[i++] = a[rightPos++];
        for (i = 0; i < size; i++)
            a[left + i] = tmp[i];
    }
}

class QuickSort implements Sort {
    public void sort(Comparable[] a) {
        quicksort(a, 0, a.length - 1);
    }

    private static final int CUTOFF = 10;

    public static final void swapReferences(Object[] a, int index1, int index2) {
        Object tmp = a[index1];
        a[index1] = a[index2];
        a[index2] = tmp;
    }

    private static void quicksort(Comparable[] a, int low, int high) {
        if (low + CUTOFF > high)
            insertionSort(a, low, high);
        else {
            // Sort low, middle, high
            int middle = (low + high) / 2;
            if (a[middle].compareTo(a[low]) < 0)
                swapReferences(a, low, middle);
            if (a[high].compareTo(a[low]) < 0)
                swapReferences(a, low, high);
            if (a[high].compareTo(a[middle]) < 0)
                swapReferences(a, middle, high);

            // Place pivot at position high - 1
            swapReferences(a, middle, high - 1);
            Comparable pivot = a[high - 1];

            // Begin partitioning
            int i, j;
            for (i = low, j = high - 1;;) {
                while (a[++i].compareTo(pivot) < 0)
                    ;
                while (pivot.compareTo(a[--j]) < 0)
                    ;
                if (i >= j)
                    break;
                swapReferences(a, i, j);
            }

            // Restore pivot
            swapReferences(a, i, high - 1);

            quicksort(a, low, i - 1); // Sort small elements
            quicksort(a, i + 1, high); // Sort large elements
        }
    }

    private static void insertionSort(Comparable[] a, int low, int high) {
        for (int p = low + 1; p <= high; p++) {
            Comparable tmp = a[p];
            int j;

            for (j = p; j > low && tmp.compareTo(a[j - 1]) < 0; j--)
                a[j] = a[j - 1];
            a[j] = tmp;
        }
    }
}

class QuickSortBad implements Sort {
    public void sort(Comparable[] a) {
        quicksortBad(a, 0, a.length - 1);
    }

    static void quicksortBad(Comparable[] a, int low, int high) {
        if (low < high) {
            int pivot = partition(a, low, high);
            quicksortBad(a, low, pivot - 1);
            quicksortBad(a, pivot + 1, high);
        }
    }

    static int partition(Comparable[] a, int low, int high) {
        Comparable pivot = a[low];
        int i = low;
        int j = high + 1;
        while (i < j) {
            do
                i++;
            while (i < j && a[i].compareTo(pivot) < 0);
            do
                j--;
            while (i <= j && a[j].compareTo(pivot) > 0);
            if (i < j) {
                Comparable temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        a[low] = a[j];
        a[j] = pivot;
        return j;
    }
}