SorterClassForCS

namespace HelloWorld
{
    class Sorter
    {

    // ---------------------------------------- Bubble Sort ---------------------------------------- //

    public static void bubbleSort(double[] array) { // Method to Run
        for (int i = 0; i < array.Length - 1; i++)
            for (int j = 0; j < array.Length - i - 1; j++)
                if (array[j] > array[j + 1])
                    swap(array, j, j + 1);
    }


    // ---------------------------------------- Insertion Sort ---------------------------------------- //

    public static void insertionSort(double[] array) { // Method to Run
        for (int i = 1; i < array.Length; i++) {
            double temp = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > temp) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;
        }
    }


    // ---------------------------------------- Merge Sort ---------------------------------------- //

    public static void mergeSort(double[] array) { // Method to Run
        Console.WriteLine("Mergesort is currently not working (Stack Overflow)...");
    }

    public static void ERRORmergeSort(double[] array) { // Method to Run
        int length = array.Length;

        int middle = length / 2;
        double[] leftArray = new double[middle];
        double[] rightArray = new double[length - middle];

        int i = 0;
        int j = 0;

        for (; i < length; i++) {
            if (i < middle)
                leftArray[i] = array[i];
            else {
                rightArray[j] = array[i];
                j++;
            }
        }
        mergeSort(leftArray);
        mergeSort(rightArray);
        merge(leftArray, rightArray, array);
    }

    private static void merge(double[] leftArray, double[] rightArray, double[] array) {
        int leftSize = array.Length / 2;
        int rightSize = array.Length - leftSize;
        int i = 0, l = 0, r = 0;

        while (l < leftSize && r < rightSize) {
            if (leftArray[l] < rightArray[r]) {
                array[i] = leftArray[l];
                i++; l++;
            } else {
                array[i] = rightArray[r];
                i++; r++;
            }
        }
        while (l < leftSize) {
            array[i] = leftArray[l];
            i++; l++;
        }
        while (r < rightSize) {
            array[i] = rightArray[r];
            i++; r++;
        }
    }


    // ---------------------------------------- Quick Sort ---------------------------------------- //

    public static void quickSort(double[] array) { // Method to Run
        quickSort(array, 0, array.Length - 1);
    }

    private static void quickSort(double[] array, int start, int end) {
        if (end <= start) return;

        int pivot = partition(array, start, end);
        quickSort(array, start, pivot - 1);
        quickSort(array, pivot + 1, end);
    }

    private static int partition(double[] array, int start, int end) {
        double pivot = array[end];
        int i = start - 1;

        for (int j = start; j <= end - 1; j++) {
            if (array[j] < pivot) {
                i++;
                double tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
        i++;

        double temp = array[i];
        array[i] = array[end];
        array[end] = temp;
        return i;
    }

    // ---------------------------------------- Selection Sort ---------------------------------------- //

    public static void selectionSort(double[] array) { // Method to Run
        for (int i = 0; i < array.Length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < array.Length; j++) {
                if (array[min] > array[j])
                    min = j;
            }

            double temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }


    // ---------------------------------------- Shell Sort ---------------------------------------- //

    public static void shellSort(double[] array) { // Method to Run
        int h = 1;
        while (h <= array.Length / 4) {
            h = h * 4 + 1;
        }

        while (h > 0) {
            for (int outer = h; outer < array.Length; outer++) {
                double tmp = array[outer];
                int inner = outer;
                while (inner > h - 1 && array[inner - h ] >= tmp) {
                    array[inner] = array[inner - h];
                    inner -= h;
                }
                array[inner] = tmp;
            }
            h = (h - 1) / 4;
        }
    }


    // ---------------------------------------- Heap Sort ---------------------------------------- //

    public static void heapSort(double[] array) { // Method to Run
        buildMaxHeap(array);
        for (int i = array.Length - 1; i > 0; i--) {
            swap(array, i, 0);
            seep(array, 0, i);
        }
    }
    // create maxHeap tree in array
    private static void buildMaxHeap(double[] arr) {
        for (int i = (arr.Length / 2) - 1; i >= 0 ; i--) {
            seep(arr, i, arr.Length);
        }
    }
    // seep - Downheap
    private static void seep(double[] arr, int i, int j) {

        while (i <= (j / 2) - 1) {

            // left child
            int childIndex = ((i + 1) * 2) - 1;
            // right child
            if (childIndex + 1 <= j - 1) {
                if (arr[childIndex] < arr[childIndex + 1]) {
                    childIndex++;
                }
            }
            // check if seep is neccessary
            if (arr[i] < arr[childIndex]) {
                swap(arr, i, childIndex);
                i = childIndex;
            } else break;
        }
    }



    // ---------------------------------------- Counting Sort ---------------------------------------- //

    public static void countingSort(double[] array) { // Method to Run
        double max = array[0];
        for (int i = 1; i < array.Length; i++)
            if (array[i] > max) max = array[i];

        int[] helpArray = new int[(int)max + 1];
        for (int i = 0; i < array.Length; i++)
            helpArray[(int)array[i]]++;

        int pos = 0;
        for (int i = 0; i <= max; i++) {
            for (int j = 0; j < helpArray[i]; j++) {
                array[pos] = i;
                pos++;
            }
        }
    }


    // ---------------------------------------- Radix Sort ---------------------------------------- //

    public static void radixSort(double[] array) { // Method to Run
        double max = array[0];
        for (int i = 1; i < array.Length; i++)
            if (array[i] > max) max = array[i];

        for (int factor = 1; max / factor > 0; factor *= 10)
            countingsort(array, factor);
    }

    private static void countingsort(double[] array, int factor) {
        int len = array.Length;
        double[] output = new double[len];
        int a;
        int[] counting = new int[10];
        for (a = 0; a < 10; a++)
            counting[a] = 0;

        for (a = 0; a < len; a++)
            counting[ (int)(array[a] / factor) % 10 ]++;
        for (a = 1; a < 10; a++)
            counting[a] += counting[a - 1];

        for (a = len - 1; a >= 0; a--) {
            output[counting[ (int)(array[a] / factor) % 10 ] - 1] = array[a];
            counting[ (int)(array[a] / factor) % 10 ]--;
        }

        for (a = 0; a < len; a++)
            array[a] = output[a];
    }


    // ---------------------------------------- Bucket Sort ---------------------------------------- //

    public static void bucketSort(double[] array) { // Method to Run
        double max = array[0];
        for (int i = 1; i < array.Length; i++)
            if (array[i] > max) max = array[i];
        double[] bucket = new double[(int)max + 1];

        for (int i = 0; i < array.Length; i++)
            bucket[(int)array[i]]++;

        int outPos = 0;
        for (int i = 0; i < bucket.Length; i++) {
            for (int j = 0; j < bucket[i]; j++) {
                array[outPos++] = i;
            }
        }
    }

    // ---- Swap ---- //

    private static void swap(double[] arr, int a, int b) {
        double k = arr[a];
        arr[a] = arr[b];
        arr[b] = k;
    }

    }
}