QUICK SORT

 

Este método supone que se tiene REG que es el arreglo a ordenar y MAXREG el numero de elementos a ordenar que se encuentran dentro del arreglo. El ordenamiento se hace a través de un proceso iterativo. Para cada paso, se escoge un elemento "a" de alguna posición específica dentro del arreglo.

 

Ese elemento "a" es el que se procederá a colocar en el lugar que le corresponda. Por conveniencia se seleccionará a "a" como el primer elemento del arreglo. El elemento "a" se procede a comparar con el resto de los elementos del arreglo.

 

Una forma puede ser: comparar "a" con el Ultimo elemento del arreglo. En la comparación, si el elemento "a" toma la Última posición y el Último elemento toma la posición 1 se procede a seguir comparando a "a" pero ahora con el segundo elemento. Si "a" resulta ser menor que el segundo elemento se hace el intercambio y se procede a comparar "a" con el penúltimo y así sucesivamente hasta que "a" se compara con todos los elementos restantes del arreglo. Note que cada vez que ocurre un intercambio de valores, la comparación de "a" se hace con los elementos del arreglo que se encuentran en posición contraria a la que se está haciendo.

Una vez que se terminó de comparar "a" con todos los elementos, "a" ya se encuentra en su lugar y a la izquierda de "a" quedan todos los elementos menores a él y a su derecha todos los mayores.

Se toma el subarreglo izquierdo (los menores de "a") y se realiza el mismo procedimiento. Se toma el subarreglo derecho (los mayores de "a") y se realiza el mismo procedimiento. Este proceso se realiza hasta que los subarreglos sean de un elemento.

En el módulo que se describe a continuación, se tiene como parámetros las posiciones del primero y oeltimo elementos del arreglo en vez de la cantidad MAXREG de elementos.

Es uno de los sorts internos más rápidos, lo que lo hace un poco más complicado que los demás.

Sea X un arreglo de "n" componentes

Técnica:

Se selecciona arbitrariamente un elemento de reg; sea "a" dicho elemento a = reg[1]
Los elementos restantes se arreglan de tal forma que "a" quede en la posición j, donde:

1.Los elementos en las posiciones 1 a (j-1) deben ser <= que "a".
2.Los elementos en las posiciones j+1 deben ser >= que "a".

Se realiza el mismo proceso para los subgrupos que se formen.

Procedure Quick (reg: arreglo; primero, último:integer);

var

  j:integer;



Procedure reacomoda (primero, último: integer; var j:integer);

var

  a, arriba, abajo :integer;

    begin

      a := reg[primero];

      j := primero;

      arriba := último;

      abajo := primero;

      repeat

      while (arriba > abajo) AND (reg[arriba] >= a) do

/* mientras a² que el elemento que se compara y haya más elementos con quien comparar */

      arriba := arriba -1;

      j := arriba;

      if arriba <> abajo then begin /* si a fue que el elemento comparado,realiza el intercambio*/

      reg[abajo] := reg[arriba];

      while (arriba <> abajo) AND (reg[abajo] <= a) do

      abajo := abajo + 1; /* moverse hacia la derecha

      j := abajo;

      if abajo <> arriba then

      reg[arriba] := reg[abajo];

    end;

      until (abajo = arriba);

      reg[j] := a;

end;/* reacomoda */



        begin

          if primero < ultimo then begin

          reacomoda(primero, ultimo, j);

          quick(reg, primero, j-1);

          quick(reg, j+1, oeltimo);

        end;

end;