﻿using System;
using System.Collections;
//NOT READY
//Write a program that sorts an array of strings using the quick sort algorithm
class QuickSortImplementation
{
    static void swap(ref int a, ref int b)
    {
        a = a ^ b;
        b = a ^ b;
        a = b ^ a;
    }
    struct Bounds
    {
        public int top;
        public int bot;
    }
    static void QuickSort(int[] Array)
    {
        Stack Steps = new Stack();
        Bounds firstStep;
        firstStep.top=Array.Length-1;
        firstStep.bot=0;
        Steps.Push(firstStep);
        while (Steps.Count != 0)
        {
            Bounds currentStep = (Bounds)Steps.Pop();
            int pivot = Array[currentStep.bot];
            int bot = currentStep.bot+1;
            int top = currentStep.top;
            while (top > bot)
            {
                while (Array[bot] < pivot && bot < top)
                {
                    bot++;
                }
                while (Array[top] >= pivot && top > bot)
                {
                    top--;
                }
                if (top > bot)
                {
                    swap(ref Array[top], ref Array[bot]);
                    //bot++;
                    //top--;
                }
            }
            if ((bot - 1) != currentStep.bot)
                swap(ref Array[currentStep.bot], ref Array[bot - 1]);
            if ((currentStep.top - top)>1)
            {
                Bounds tempStep;
                tempStep.top = currentStep.top;
                //tweak here;
                tempStep.bot = top ;
                Steps.Push(tempStep);
            }
            if ((  bot-currentStep.bot)>1)
            {
                Bounds tempStep;
                tempStep.bot = currentStep.bot;
                tempStep.top = bot-1;
                Steps.Push(tempStep);
            }
        }
    }
    static void Main()
    {
        int n;
        Console.Write("N=");
        while (!int.TryParse(Console.ReadLine(), out n) || n < 0)
        {
            Console.WriteLine("Incorrect input. Please try again:");
        }
        int[] SimpleIntArray = new int[n];
        for (int i = 0; i < n; i++)
        {
            Console.Write("N[{0}]=", i);
            while (!int.TryParse(Console.ReadLine(), out SimpleIntArray[i]))
            {
                Console.WriteLine("Incorrect input. Please try again:");
            }
        }
        QuickSort(SimpleIntArray);
        for (int i = 0; i < SimpleIntArray.Length; i++)
        {
            Console.WriteLine("N[{0}] = {1}",i,SimpleIntArray[i]);
        }
    }
}

