import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Sort {

    /*
     * Used to avoid the penalty of loading the Sort class
     */
    public static void dummy()
    {
    }

    /*
     * BubbleSort
     *
     * https://www.geeksforgeeks.org/bubble-sort/
     */
    public static void bubbleSort(int[] array)
    {
        int n = array.length;
        boolean swap;
        for (int i = 0; i < n - 1; i++) {
            swap = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // swap array[j + 1] and array[j]
                    swap = true;
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            if (!swap) {
                break;
            }
        }
    }

    /*
     * SelectionSort
     *
     * https://www.geeksforgeeks.org/selection-sort/
     */
    public static void selectionSort(int[] array)
    {
        int n = array.length;

        // One by one move boundary of unsorted sub-array
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[min_idx]) {
                    min_idx = j;
                }
            }

            // Swap the found minimum element with the first
            // element
            int temp = array[min_idx];
            array[min_idx] = array[i];
            array[i] = temp;
        }
    }

    /*
     * InsertionSort
     *
     * https://www.geeksforgeeks.org/insertion-sort/
     */
    public static void insertionSort(int[] array)
    {
        int n = array.length;
        for (int i = 1; i < n; ++i) {
            int key = array[i];
            int j = i - 1;

            /* Move elements of array[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }

    /*
     * HeapSort
     *
     * https://www.geeksforgeeks.org/java-program-for-heap-sort/
     */
    public static void heapSort(int[] array)
    {
        int n = array.length;

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }

        // One by one extract an element from heap
        for (int i = n - 1; i >= 0; i--) {
            // Move current root to end
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // call max heapify on the reduced heap
            heapify(array, i, 0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in array[]. n is size of heap
    private static void heapify(int[] array, int n, int i)
    {
        int largest = i;  // Initialize largest as root
        int l = 2 * i + 1;  // left = 2 * i + 1
        int r = 2 * i + 2;  // right = 2 * i + 2

        // If left child is larger than root
        if (l < n && array[l] > array[largest]) {
            largest = l;
        }

        // If right child is larger than largest so far
        if (r < n && array[r] > array[largest]) {
            largest = r;
        }

        // If largest is not root
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(array, n, largest);
        }
    }

    /*
     * Quicksort
     *
     * https://www.geeksforgeeks.org/quick-sort/
     */
    public static void quicksort(int[] array, int low, int high)
    {
        if (low < high) {
            /* pi is partitioning index, array[pi] is
              now at right place */
            int pi = partition(array, low, high);

            // Recursively sort elements before
            // partition and after partition
            quicksort(array, low, pi - 1);
            quicksort(array, pi + 1, high);
        }
    }

    private static int partition(int[] array, int low, int high)
    {
        int pivot = array[high];
        int i = (low - 1); // index of smaller element
        for (int j = low; j < high; j++) {
            // If current element is smaller than the pivot
            if (array[j] < pivot) {
                i++;

                // swap array[i] and array[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // swap array[i+1] and array[high] (or pivot)
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;

        return i + 1;
    }

    /*
     * ShellSort
     *
     * https://www.geeksforgeeks.org/shellsort/
     */
    public static void shellSort(int[] array)
    {
        int n = array.length;

        // Start with a big gap, then reduce the gap
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // Do a gapped insertion sort for this gap size.
            // The first gap elements a[0..gap-1] are already
            // in gapped order keep adding one more element
            // until the entire array is gap sorted
            for (int i = gap; i < n; i += 1) {
                // add a[i] to the elements that have been gap
                // sorted save a[i] in temp and make a hole at
                // position i
                int temp = array[i];

                // shift earlier gap-sorted elements up until
                // the correct location for a[i] is found
                int j;
                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                    array[j] = array[j - gap];
                }

                // put temp (the original a[i]) in its correct
                // location
                array[j] = temp;
            }
        }
    }

    /*
     * Mergesort
     *
     * https://www.geeksforgeeks.org/merge-sort/
     */
    public static void mergesort(int[] array, int l, int r)
    {
        if (l < r) {
            // Find the middle point
            int m = (l + r) / 2;

            // Sort first and second halves
            mergesort(array, l, m);
            mergesort(array, m + 1, r);

            // Merge the sorted halves
            merge(array, l, m, r);
        }
    }

    private static void merge(int[] array, int l, int m, int r)
    {
        // Find sizes of two sub-arrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int[] L = new int[n1];
        int[] R = new int[n2];

        /* Copy data to temp arrays */
        if (n1 >= 0) {
            System.arraycopy(array, l, L, 0, n1);
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = array[m + 1 + j];
        }

        /* Merge the temp arrays */

        // Initial indexes of first and second sub-arrays
        int i = 0, j = 0;

        // Initial index of merged sub-array array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                array[k] = L[i];
                i++;
            }
            else {
                array[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            array[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            array[k] = R[j];
            j++;
            k++;
        }
    }

    /*
     * BucketSort
     * Sort a large set of floating point numbers which are in range from 0.0 to 1.0
     * and are uniformly distributed across the range.
     * https://www.geeksforgeeks.org/bucket-sort-2/
     */
    public static void bucketSort(float[] array, int n)
    {
        if (n <= 0) {
            return;
        }

        // 1) Create n empty buckets
        @SuppressWarnings("unchecked")
        List<Float>[] buckets = new List[n];

        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 2) Put array elements in different buckets
        for (int i = 0; i < n; i++) {
            float idx = array[i] * n;
            buckets[(int) idx].add(array[i]);
        }

        // 3) Sort individual buckets
        for (int i = 0; i < n; i++) {
            Collections.sort(buckets[i]);
        }

        // 4) Concatenate all buckets into array[]
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                array[index++] = buckets[i].get(j);
            }
        }
    }

    /*
     * RadixSort
     * Non-negative integers
     * https://www.geeksforgeeks.org/radix-sort/
     */
    public static void radixSort(int[] array)
    {
        int n = array.length;

        // Find the maximum number to know number of digits
        int m = getMax(array, n);

        // Do counting sort for every digit. Note that
        // instead of passing digit number, exp is passed.
        // exp is 10^i where i is current digit number
        for (int exp = 1; m / exp > 0; exp *= 10) {
            countSort(array, n, exp);
        }
    }

    // A utility function to get maximum value in arr[]
    private static int getMax(int[] array, int n)
    {
        int mx = array[0];
        for (int i = 1; i < n; i++) {
            if (array[i] > mx) {
                mx = array[i];
            }
        }
        return mx;
    }

    // A function to do counting sort of arr[] according to
    // the digit represented by exp.
    private static void countSort(int[] array, int n, int exp)
    {
        int[] output = new int[n]; // output array
        int i;
        int[] count = new int[10];
        Arrays.fill(count, 0);

        // Store count of occurrences in count[]
        for (i = 0; i < n; i++) {
            count[(array[i] / exp) % 10]++;
        }

        // Change count[i] so that count[i] now contains
        // actual position of this digit in output[]
        for (i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Build the output array
        for (i = n - 1; i >= 0; i--) {
            output[count[(array[i] / exp) % 10] - 1] = array[i];
            count[(array[i] / exp) % 10]--;
        }

        // Copy the output array to array[], so that array[] now
        // contains sorted numbers according to current digit
        for (i = 0; i < n; i++) {
            array[i] = output[i];
        }
    }
}