using System;

using System.Collections.Generic;       

​

public class Program

{

    public static void QuickSort(List<int> arr, int start, int end)

    {

        if(start < end)

        {

            int pivotIdx = partition(arr, start, end);

            QuickSort(arr, start, pivotIdx - 1);

            QuickSort(arr, pivotIdx + 1, end);      

        }

    }

    public static int partition(List<int> arr, int start, int end)

    {

        int pivot = arr[end];

        int nextIdx = start;

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

        {

            if(arr[i] < pivot) 

            {

                swap(arr, i, nextIdx);

                nextIdx ++;

            }           

        }

        swap(arr, nextIdx, end);

        return nextIdx;

    }

    public static void Main()

    {       

        List<int> data = new List<int> {8, 5, 7, 1 ,9 ,3};

        QuickSort(data, 0, data.Count - 1);

        foreach(int i in data)

        {

            Console.WriteLine(i);

        }

    }

    public static void swap(List<int>data, int a, int b)

    {

        int temp = data[a];

        data[a] = data[b];

        data[b] = temp;

    }

}