03.n Método para Ordenar - QuickSort Recursivo (2351) El método más rápido de los sencillos para ordenar una lista de datos. contact Created,Modified 2009-04-10 08:34:53, 2009-05-07 19:13:30 Author,Nick Gustavo Guillermo Perez, (madgus) [myblog]

Método QuickSort Recursivo

Este método para ordenar, es recursivo, si entendimos el ejemplo anterior, pudimos ver que la ejecución del algoritmo era secuencial, es decir 1 sola función hizo todo el trabajo en si misma.

Este algoritmo implementa la división en dos grupos del arreglo a ordenar y por lo tanto la misma operación se realiza con cada subgrupo que a su vez se vuelve a dividir, y como es la misma operación se llama a la misma función varias veces.

Esto tiene una desventaja, la plataforma que corre nuestra implementación debe producir una interrupción del proceso de ejecución para llamar a otra función, esto no tiene nada de malo excepto que cuando sean demasiados elementos la cantidad de veces que una función llamó a la misma función que llamó a la misma función puede ser tan larga que podría producir un agotamiento de recursos que ralentice o impida la ejecución de este tipo de algoritmos, en conclusión este método es muy difícil implementarlo de manera secuencial pero la cantidad de comparaciones se reduce notablemente.{1}{2}

1. public static void quicksort_menormayor(int[] listado,int i,int j){

2. if (i>=j){return;}

3. int p = dividiren_menormayor(listado,i,j);

4. quicksort_menormayor(listado,i,p-1);

5. quicksort_menormayor(listado,p+1,j);

6. }//final del método principal de quicksort

8. public static int dividiren_menormayor(int[] listado,int i,int j){

9. int p= i; i++;

10. while (true){

11. while (i < j && listado[i]<=listado[p]){i++;}

12. while (i < j && listado[j]>=listado[p]){j--;}

13. if (i == j) break;

14. swap(listado,i,j);

15. }

16. if (listado[p]<listado[i]){i--;}

17. swap(listado,p,i);

18. return i;

19. }//final del método que divide y ordena

En el código de ejemplo vemos que se declararon varias funciones, la función swap hace el intercambio con la variable temporal como en el método anterior, la función dividiren es la más importante de este procedimiento, es no solo la que divide sino la que intercambia los elementos que se van ordenando. Y por supuesto quicksort se llama así misma por cada subsegmento.

Cada segmento se recorre hacia arriba y hacia abajo saltándose los menores e iguales y mayores e iguales que el elemento inferior, cuando no hay nada que saltar, se intercambian los valores de manera que quedan por encima y debajo de p los mayores y los menores.

Ahora veamos la misma función pero ordenando de mayor a menor, como podemos ver sólo cambian los signos de comparación referentes a los contenidos del listado.

1. public static void quicksort_mayormenor(int[] listado,int i,int j){

2. if (i>=j){return;}

3. int p = dividiren_mayormenor(listado,i,j);

4. quicksort_mayormenor(listado,i,p-1);

5. quicksort_mayormenor(listado,p+1,j);

6. }//final del método principal de quicksort

8. public static int dividiren_mayormenor(int[] listado,int i,int j){

9. int p= i; i++;

10. while (true){

11. while (i < j && listado[i]>=listado[p]){i++;}

12. while (i < j && listado[j]<=listado[p]){j--;}

13. if (i == j) break;

14. swap(listado,i,j);

15. }

16. if (listado[p]>listado[i]){i--;}

17. swap(listado,p,i);

18. return i;

19. }//final del método que divide y ordena

Otros mecanismos para ordenar.

Existen otros mecanismos que no podemos tratar en este momento porque es necesario implementar objetos, así que ese será el próximo tema, algunos son, por inserción, por fusión, de shell y con un árbol binario.

leavecomment

---