Java - QuickSort utilizando el Partition Dutch flag sobre arreglos

 
Vista:

QuickSort utilizando el Partition Dutch flag sobre arreglos

Publicado por Maria (2 intervenciones) el 04/11/2020 14:38:11
tengo que implementar el algoritmo QuickSort, utilizando un método partitionDutchFlag que use el algoritmo de la bandera Holandesa de Dijkstra para realizar la partición. Utilizando estos métodos:
private static <T extends Comparable<? super T>> int partitionDutchFlag(T[] array, int posInicial, Int posFinal, int pivote)
private static <T extends Comparable<? super T>> void quickSort2(T[] array,int begin, int end)
private static <T extends Comparable<? super T>> void quickSort2(T[] array,int begin, int end)
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Rodrigo
Val: 2.152
Oro
Ha mantenido su posición en Java (en relación al último mes)
Gráfica de Java

QuickSort utilizando el Partition Dutch flag sobre arreglos

Publicado por Rodrigo (576 intervenciones) el 04/11/2020 16:14:31
La 2da y 3ra linea parecen ser la misma.
Quicksort funciona eligiendo el pivote, particionando y llamando recursivamente para cada particion.

Supongo que lo unico novedoso seria lo de la particion?
No es claro que es lo que preguntas, podrias elaborar mas en lo que estas preguntando especificamente?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

QuickSort utilizando el Partition Dutch flag sobre arreglos

Publicado por Maria (2 intervenciones) el 04/11/2020 18:18:36
Mí duda es como representar el método partitionDutchFlag, para luego utilizarlo en el QuickSort, sabiendo que como parámetro, voy a tener el arreglo, posición inicial, pivote, posición final
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Rodrigo
Val: 2.152
Oro
Ha mantenido su posición en Java (en relación al último mes)
Gráfica de Java

QuickSort utilizando el Partition Dutch flag sobre arreglos

Publicado por Rodrigo (576 intervenciones) el 05/11/2020 00:34:07
Quicksort tiene que elegir un pivote, no se como haras esto, pero para la explicacion, supongamos que eliges el valor que esta en la mitad del rango entre begin y end. O puedes elegir el valor que esta en el indice begin o el que esta en end, o tomar los 3 valores y elegir el que matematicamente este mas cerca de la mitad de ellos, etc.

Como sea que elijas el pivote, invocar la funcion esta de dutch con los parametros que ya tienes.
Despues de esto tendras un arreglo que ha sido particionado y que ha dejado el pivote en el lugar correcto.
No queda mas que invocar recursivamente Quicksort con la mitad izquierda del arreglo (a la izquierda del pivote) y la mitad derecha.

Tienes que considerar que hacer cuando begin y end sean iguales o begin sea mayor que end (por ejemplo salir inmediatamente sin hacer nada, pues no hay nada que hacer)
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar