using System;
using System.IO;

namespace Ordenacion3
{
    public class MetodoQuicksort
    {

        public static void Main(string[] args)
        {
            int[] vector; int temp;

            Console.Write("¿Cuántos números deseas ordenar? ");
            temp = Leer.datoInt();

            vector = new int[temp];

            for (int i = 0; i < temp; i++)
            {
                Console.Write("Introduce el dato " + (i + 1) + " : ");
                vector[i] = Leer.datoInt();
            }

            Console.Write("Vector a ordenar: [ ");
            for (int j = 0; j < vector.Length; j++)
            {
                Console.Write(vector[j] + " ");
            }
            Console.Write("]\n");

            Quicksort(vector);

            Console.Write("Vector a ordenado: [ ");
            for (int j = 0; j < vector.Length; j++)
            {
                Console.Write(vector[j] + " ");
            }
            Console.Write("]\n");

            Console.ReadKey();
        }

        private static void Quicksort(int[] v)
        {
            Qs(v, 0, v.Length-1);
        }

        private static void Qs(int[] vector, int primero, int ultimo)
        {
            int i, j, central;
            double pivote;

            central = (primero + ultimo) / 2;
            pivote = vector[central];
            i = primero;
            j = ultimo;

            do
            {
                while (vector[i] < pivote) i++;
                while (vector[j] > pivote) j--;

                if (i <= j)
                {
                    int temp;
                    temp = vector[i];
                    vector[i] = vector[j];
                    vector[j] = temp;
                    i++;
                    j--;
                }
            } 
            while (i <= j);

            if (primero < j)
            {
                Qs(vector, primero, j);
            }

            if (i < ultimo)
            {
                Qs(vector, i, ultimo);
            }		
        }
    }

    public class Leer
    {
        public static int datoInt()
        {
            string dato;
            dato = System.Console.ReadLine();
            return int.Parse(dato);
        }
    }
}