using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QuickSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 6, 10, 5, 12, 3, 9, 20, 2, 15, 8, 18 };
            QuickSort(arr);
            PrintArray(arr);
            Console.ReadLine();
        }

        static void PrintArray(int[] s)
        {
            for (int i = 0; i < s.Length; i++)
            {
                Console.Write("{0} ", s[i]);
            }
            Console.WriteLine();
        }


        static void QuickSort(int[] s)
        {
            int n = s.Length;

            QSort(s, 0, n - 1);
        }

        static void QSort(int[] s, int a, int b)
        {
            int temp;
            if (a >= b) // base case: 0 or 1 element sublist
                return;
            int p = s[b];
            int l = a;
            int r = b - 1;
            while (l <= r)
            {
                while (l <= r && s[l] <= p) // find element on left side > pivot
                    l++;
                while (r >= l && s[r] >= p) // find element on right side < pivot
                    r--;
                if (l < r)
                {
                    // swap s[l] && s[r]--the two elements that are on the wrong sides
                    temp = s[l];
                    s[l] = s[r];
                    s[r] = temp;
                }
            }
            // swap s[l] and s[b]--place pivot in middle
            temp = s[l];
            s[l] = s[b];
            s[b] = temp;

            QSort(s, a, l - 1);
            QSort(s, l + 1, b);
        }
    }
}