using System;

public class Program

{

    public static void Main()

    {

        var arr = new int[] {2,1,5,3,4};

        Quicksort(ref arr, 0, arr.Length -1);

        for(int i = 0; i <arr.Length; i++)

        {

            Console.WriteLine(arr[i]);

        }

    }

    public static void Quicksort(ref int[] arr, int start, int end)

    {

        Console.WriteLine("  " + start + " " + end);

        if(start >= end)

            return;

        else

        {

            var part = Partition(ref arr, start, end);

            Console.WriteLine("  part " + part + " " + start + " " + end);

            Quicksort(ref arr, part + 1, end);

            Quicksort(ref arr, 0, part -1);

        }

    }

    public static int Partition(ref int[] arr, int start, int end)

    {

        var pivot = arr[end];

        int i = start - 1;

        for(int j = start; j < end; j++)

        {

            if(arr[j] <= pivot)

            {

                i++;

                Console.WriteLine("  swap  " + i + " " + j);

                if(i != j)

                    Swap(ref arr, i, j);

            }   

        }

        i++;

        Swap(ref arr, i, end);

        return i;

    }

    public static void Swap(ref int[] arr, int i, int j)

    {

        var t = arr[i];

        arr[i] = arr[j];

        arr[j] = t;

    }

}