namespace SortingVisualization.Algorithms {
    public class Quicksort : SortingAlgorithm {
        public override string GetAlgorithmName() => "Quicksort";
        public override void Sort(ref DataSet set) {
            Simulate(ref set);
            System.Console.WriteLine("Doing {0}...", this.GetAlgorithmName());
            SortRecursion(ref set, 0, set.Size - 1);
            System.Console.WriteLine("{0} complete!", this.GetAlgorithmName());
            if (!set.SimulateMode)
                set.FinalizeVideo();
        }
        public static void SortRecursion(ref DataSet set, int l, int r) {
            int i = l, j = r;
            int pivot = (l + r) / 2;
            while (i <= j) {
                while (set.LessThan(i, pivot))
                    i++;
                while (set.GreaterThan(j, pivot))
                    j--;

                if (i <= j) {
                    set.Swap(i, j);
                    if (pivot == i)
                        pivot = j;
                    else if (pivot == j)
                        pivot = i;
                    i++;
                    j--;
                }
            }
            if (l < j)
                SortRecursion(ref set, l, j);
            if (i < r)
                SortRecursion(ref set, i, r);
        }
    }
}