public class Hints {
    private static void bubbleSort(int[] array) {
        int tmp;

        for(int i = 0; i < array.length; i++) {
            for(int j = 1; j < array.length; j++) {
                if(array[i] < array[j - 1]) {
                    tmp = array[i];
                    array[i] = array[j - 1];
                    array[j - 1] = tmp;
                }
            }
        }
    }
    private static void selectionSort(int[] array) {
        int tmp;

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

            for(int j = i; j < array.length; j++) {
                if(array[j] < array[min])
                    min = j;
            }

            tmp = array[i];
            array[i] = array[min];
            array[min] = tmp;
        }
    }
    private static void insertionSort(int[] array) {
        int value;

        for(int i = 0; i < array.length; i++) {
            value = array[i];

            int j = i - 1;

            for(; j >= 0; j--) {
                if(value < array[j])
                    array[j + 1] = array[j];
                else
                    break;
            }

            array[j + 1] = value;
        }
    }
    private static void shuffleSort(int[] array) {
        int tmp;

        for(int i = 1; i < array.length; i++) {
            if(array[i] < array[i - 1]) {
                tmp = array[i - 1];
                array[i - 1] = array[i];
                array[i] = tmp;
            }

            for(int j = i - 1; (j - 1) >= 0; j--) {
                if(array[j] < array[j - 1]) {
                    tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
    private static void shellSort(int[] array) {
        int tmp;
        int range = array.length / 2;

        while (range >= 1) {
            for(int i = 0; i < array.length; i++) {
                for (int j = i - range; j >= 0; j -= range) {
                    if(array[j] > array[j + range]) {
                        tmp = array[j + range];
                        array[j + range] = array[j];
                        array[j] = tmp;
                    }
                }
            }

            range = range / 2;
        }
    }
    private static void sortMerge(int[] array) {
        if(array.length <= 1)
            return;

        int mid = array.length / 2;
        int[] left = new int[mid];
        int[] right = new int[array.length - mid];

        System.arraycopy(array, 0, left, 0, left.length);
        System.arraycopy(array, left.length, right, 0, right.length);

        sortMerge(left);
        sortMerge(right);

        merge(left, right, array);
    }
    private static void merge(int[] left, int[] right, int[] array) {
        int lPosition = 0, rPosition = 0, mPosition = 0;

        while (lPosition < left.length && rPosition < right.length){
            if(left[lPosition] < right[rPosition]) {
                array[mPosition] = left[lPosition];
                lPosition++;
            } else {
                array[mPosition] = right[rPosition];
                rPosition++;
            }

            mPosition++;
        }

        System.arraycopy(left, lPosition, array, mPosition, left.length - lPosition);
        System.arraycopy(right, rPosition, array, mPosition, right.length - rPosition);
    }

    private static void binarySearch(int[] array, int number) {
        int first = 0;
        int last = array.length - 1;
        int middle = (first + last) / 2;

        while (first <= last){
            if(array[middle] == number)
                break;
            else if(number < array[middle])
                last = middle - 1;
            else
                first = middle + 1;

            middle = (first + last) / 2;
        }

        System.out.println("Middle: " + middle + ", number: " + array[middle]);
    }
}