package sortierverfahren;

import java.util.Arrays;

public class Sortierverfahren {

    //Marius Spangenberger, Filipp Roos, Dominik Erbacher, Übungsgruppe 07.

    public static void main(String[] args) {
        int[] feld = {43, 53, 3, 2, 4, 1, 56, 98, 14};
        insertionSort(feld, 0, feld.length-1);
        //easySort(feld);
        //quickSort(feld, 0, feld.length - 1);
        //linearSort(feld, 4);
        System.out.println(Arrays.toString(feld));

    }

    public static void insertionSort(int[] a, int l, int r) {
        for (int j = l+1; j < r + 1; j++) {
            int key = a[j];
            int i;
            for (i = j; i > l && a[i-1] > key; i--) {
                a[i] = a[i-1];
            }
            a[i] = key;
        }
    }

    public static void easySort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = a[i];
            int indexMin = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < min) {
                    min = a[j];
                    indexMin = j;
                }
            }
            a[indexMin] = a[i];
            a[i] = min;

        }
        //      for (int i =0; i< a.length; i++){
        //          System.out.print(a[i] + " ");
        //      }
    }

    public static void quickSort(int[] a, int l, int r) {//0, länge-1
        if (l < r) {
            int m = partition(a, l, r);
            quickSort(a, l, m - 1);
            quickSort(a, m + 1, r);
        }
    }

    public static int partition(int[] a, int l, int r) {
        int pivot = a[r];
        int i = l;
        for (int j = l; j < r; j++) {
            if (a[j] <= pivot) {
                swap(a, i, j);
                i++;
            }
        }
        swap(a, i, r);
        return i;
    }

    public static void swap(int[] a, int i, int r) {
        int help = a[i];
        a[i] = a[r];
        a[r] = help;
    }

    public static void linearSort(int[] a, int k) {
        int[] c = new int[k + 1];
        for (int i = 0; i < a.length; i++) {
            c[a[i]]++;
        }

        for (int i = 0; i < k; i++) {
            c[i + 1] += c[i];
        }
        int[] b = new int[a.length];
        for (int j = a.length - 1; j >= 0; j--) {
            b[c[a[j]] - 1] = a[j];
            c[a[j]]--;
        }
        System.arraycopy(b, 0, a, 0, a.length);
    }

    public static void combinedSort(int[] a, int t) {
        combinedSort(a, 0, a.length-1, t);
    }

    public static void combinedSort(int[] a, int l, int r, int t) {
        if (l < r) {
            if((r - l) > t) {
                int m = partition(a, l, r);
                quickSort(a, l, m - 1);
                quickSort(a, m + 1, r);
            } else {
                insertionSort(a, l, r);
            }
        }
    }
}