Udemy: Master Coding Interview - Quick Sort - #179

using System;

class MainClass {
    static void Main() {
        int[] numbers = {99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0};
        Console.WriteLine("Unsorted:  " + ToString(numbers));
        QuickSort(numbers);
        Console.WriteLine("QuickSort: " + ToString(numbers));
    }
    
    public static void QuickSort(int[] numbers) {
        QuickSortRecurive(numbers, 0, numbers.Length-1);
    }
    
    public static void QuickSortRecurive(int[] numbers, int low, int high) {
        if (low < high) {
            int partitioningIndex = Partition(numbers, low, high);
            QuickSortRecurive(numbers, low, partitioningIndex - 1);
            QuickSortRecurive(numbers, partitioningIndex + 1, high);
        }
    }
    
    public static int Partition(int[] numbers, int low, int high) {
        int pivotValue = numbers[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (numbers[j] < pivotValue) {
                i++;
                int temp = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = temp;
            }
        }
        int temp2 = numbers[i+1];
        numbers[i+1] = numbers[high];
        numbers[high] = temp2;
        return i+1;
    }
    
    public static string ToString(int[] numbers) {
        string s = "{";
        for (int i = 0; i < numbers.Length; i++) {
            if (i > 0) {
                s += ", ";
            }
            s += "" + numbers[i];
        }
        s += "}";
        return s;
    }
}