// Es esta una clase que implementa el algoritmo Quick Sort para ordenar un vector
// El codigo original fue copiado de WIkipedia, estoy trabajando en otra manera de esta misma
// implementacion
class
qsrt
    {
        internal void Quicksort(ref int[] v, int prim, int ult)
        {
            if (prim < ult)
            {
                /* Selecciona un elemento del vector y coloca los menores
                 que él a su izquierda y los mayores a su derecha */
                int p = Pivote(v, prim, ult, ult);

                /* Repite el proceso para cada una de las
                 particiones generadas en el paso anterior */

                Quicksort(ref v, prim, p – 1);
                Quicksort(ref v, p + 1, ult);
            }
        }

        /* Implementación no clásica de la función Pivote. En lugar de
        recorrer el vector simultáneamente desde ambos extremos hasta el
        cruce de índices, se recorre desde el comienzo hasta el final */
        int Pivote(int[] v, int prim, int ult, int piv)
        {
            int p = v[piv];
            int j = prim;

            // Mueve el pivote a la última posición del vector
            Intercambia(v, piv, ult);

            /* Recorre el vector moviendo los elementos menores
             o iguales que el pivote al comienzo del mismo */
            for (int i = prim; i < ult; i++)
            {
                if (v[i] <= p)
                {
                    Intercambia(v, i, j);
                    j++;
                }
            }

            // Mueve el pivote a la posición que le corresponde
            Intercambia(v, j, ult);

            return j;
        }

        void Intercambia(int[] v, int a, int b)
        {
            if (a != b)
            {
                int tmp = v[a];
                v[a] = v[b];
                v[b] = tmp;
            }
        }
    }

Anuncios