1

Buenos días, llevo tiempo intentando aprender el algoritmo de quicksort. Lo he entendido pero no me termina de funcionar

public class QuickSort {

    public static int pivote(int[] vector, int i, int j) {

        int pivote = vector[i];

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

            if (vector[i] > pivote) {
                int auxIntercambio = vector[i];
                vector[i] = vector[j];
                vector[j] = auxIntercambio;
            }
        }
        return i;
    }

    public static void quickSort(int[] vector, int izquierda, int derecha) {
        int pivote = pivote(vector,izquierda,derecha);

        quickSort(vector, izquierda, pivote - 1);
        quickSort(vector, pivote, derecha);
    }

    public static void main(String a[]){

        int[] input = {24,2,45,20,56,75,2,56,99,53,12};
        QuickSort.quickSort(input,0, input.length-1);
        System.out.println(Arrays.toString(input));
    }
}

El error que me da es

Exception in thread "main" java.lang.StackOverflowError at QuickSort.quickSort(QuickSort.java:31) at QuickSort.quickSort(QuickSort.java:33) at QuickSort.quickSort(QuickSort.java:33) at QuickSort.quickSort(QuickSort.java:33) at QuickSort.quickSort(QuickSort.java:33) at QuickSort.quickSort(QuickSort.java:33) at QuickSort.quickSort(QuickSort.java:33) at QuickSort.quickSort(QuickSort.java:33)

Creo que lo que me falta es un if en cada una de las recursividades, pero no estoy seguro.

¿Alguien que me pueda echar un cable?

Saludos y gracias!.

2
  • me parece que el algoritmo esta mal, te dejo un link que espero que sea de ayuda vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html el 28 jun. 2017 a las 13:46
  • Cada vez que llama a quickSort hace dos llamadas más a quickSort y nunca sale sin llamar a ningún método. Así que el stack crecerá y crecerá hasta que lance la excepción.
    – SJuan76
    el 28 jun. 2017 a las 13:47

3 respuestas 3

1

Listo, ya lo solucione. Pongo la solución por si ha alguien le interesa.

http://www.jmonda.com/blog_post.php?n=algoritmo_quicksort_ordenamiento

Saludos.

public class QuickSort {

        public int partition(int arr[], int i, int j)
        {
              int tmp;
              int pivote = arr[(i + j) / 2]; //Valor del medio
              System.out.println("Pivote escogido: "+pivote);

              while (i <= j) { //Cuando i>j stop!
                    while (arr[i] < pivote) i++;
                    while (pivote < arr[j]) j--;
                    if (i <= j) {
                          tmp = arr[i];
                          arr[i] = arr[j];
                          arr[j] = tmp;
                          i++;
                          j--;
                    }
                    System.out.println("Ordenado: "+Arrays.toString(arr));
                    System.out.println("Finales: i="+i+" j="+j);
              }
              System.out.println("");
              return i;
        }

        public void quickSort(int arr[], int i, int j) {

              int pivote = partition(arr, i, j);
              if (i < pivote - 1){
                    System.out.println("////// i="+i+" j="+j+" p="+pivote+" Recursividad 1: "+i+"->"+(pivote-1));
                    quickSort(arr, i, pivote - 1);
              }
              if (pivote < j){
                    System.out.println("////// i="+i+" j="+j+" p="+pivote+" Recursividad 2: "+pivote+"->"+j);
                    quickSort(arr, pivote, j);
              }
        }

        public static void main(String a[]){

            int[] input = {1,12,5,26,7,14,3,7,2};
            System.out.println("////// i="+0+" j="+(input.length-1)+" Recursividad 0:");
            new QuickSort().quickSort(input,0, input.length-1);
            System.out.println("Lista final ordenada: "+Arrays.toString(input));
        }
}

Resultado obtenido:

////// i=0 j=8 Recursividad 0:
Pivote escogido: 7
Ordenado: [1, 2, 5, 26, 7, 14, 3, 7, 12]
Finales: i=2 j=7
Ordenado: [1, 2, 5, 7, 7, 14, 3, 26, 12]
Finales: i=4 j=6
Ordenado: [1, 2, 5, 7, 3, 14, 7, 26, 12]
Finales: i=5 j=5
Ordenado: [1, 2, 5, 7, 3, 14, 7, 26, 12]
Finales: i=5 j=4

////// i=0 j=8 p=5 Recursividad 1: 0->4
Pivote escogido: 5
Ordenado: [1, 2, 3, 7, 5, 14, 7, 26, 12]
Finales: i=3 j=3
Ordenado: [1, 2, 3, 7, 5, 14, 7, 26, 12]
Finales: i=3 j=2

////// i=0 j=4 p=3 Recursividad 1: 0->2
Pivote escogido: 2
Ordenado: [1, 2, 3, 7, 5, 14, 7, 26, 12]
Finales: i=2 j=0

////// i=0 j=2 p=2 Recursividad 1: 0->1
Pivote escogido: 1
Ordenado: [1, 2, 3, 7, 5, 14, 7, 26, 12]
Finales: i=1 j=-1

////// i=0 j=4 p=3 Recursividad 2: 3->4
Pivote escogido: 7
Ordenado: [1, 2, 3, 5, 7, 14, 7, 26, 12]
Finales: i=4 j=3

////// i=0 j=8 p=5 Recursividad 2: 5->8
Pivote escogido: 7
Ordenado: [1, 2, 3, 5, 7, 7, 14, 26, 12]
Finales: i=6 j=5

////// i=5 j=8 p=6 Recursividad 2: 6->8
Pivote escogido: 26
Ordenado: [1, 2, 3, 5, 7, 7, 14, 12, 26]
Finales: i=8 j=7

////// i=6 j=8 p=8 Recursividad 1: 6->7
Pivote escogido: 14
Ordenado: [1, 2, 3, 5, 7, 7, 12, 14, 26]
Finales: i=7 j=6

Lista final ordenada: [1, 2, 3, 5, 7, 7, 12, 14, 26]
0

supongamos que tienes 5,7,2,4,8,3 en tu arreglo, pivote empieza con 5, al empezar el while pivote[i] es igual a 5 , aumenta i, después pivote[i] va a ser igual a 7, dado que no es menos o igual pasa al siguiente while, vector[j] que es 3, no es mayor a 5, por lo que sale del while, después hace el cambio de vector[j] por vector[i] que cambia el 7 por el 3, entonces tu arreglo queda 5,3,2,4,8,7 después nuevamente entra el loop ahora cambia el 3 por el 8, y tu arreglo queda 5,8,2,4,3,7 una vez hecho esto ya no cambia numeros dado que salio del while e i termina siendo 2, por lo que tu quick se diviría en [5,8], [2,4,3,7]. Ahora para empezar ya está mal, pues nunca moviste el pivote y el 5 nunca se quedo en su lugar como debió haber sido, el 8 quedo del lado contrario además.

Después haces el quick con [5, 8] dado que el pivote terminará siendo 0, en el siguiente quick entrará de nuevo al quick con los mismos parametros lo que derivará en un loop infinito y por ende el error stackoverflow

0

Reabro tema.

Sigo con una duda, en el código publicado antes una vez elegido el pivote, incrementa i y decrementa j si el valor es menor/mayor que el pivote.

Después intercambia los valores de i y j.

La duda esta en: ¿El algoritmo una vez elegido el pivote lo que hace es poner a la izquierda los valores mas pequeño que el pivote y a su derecha los elementos mas grandes?

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.