He implementado el algoritmo de QuickSort del libro y puso raro de salida. Funciona, pero se organiza en orden descendente en lugar de ascender. Por ejemplo: [1, 5, 2, 10, 6, 9, 8, 3, 7, 4]
se ordena [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] no puedo parecen a encontrar la fuente en mi código:

private void quicksort(int[] A, int p, int r) {
    if (p < r) {
        int q = partition(A, p, r);
        quicksort(A, p, q);
        quicksort(A, q + 1, r);
    }
}

private int partition(int[] A, int p, int r) {
    int x = A[p]; //pivot
    int i = p;
    int j = r;
    while (true) {

        while (A[i] > x) {
            i++;
        }

        while (A[j] < x) {
            j--;
        }
        if (i < j) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        } else {
            return j;
        }
    }
}

LLAMADA INICIAL:

   quicksort(A, 0, A.length - 1);

¿cómo puedo calcular el espacio de la complejidad para el quicksort?

gracias chicos

  • Por favor, no pedir a dos preguntas diferentes en la misma pregunta. Para tu segunda pregunta que usted debe, probablemente, sólo en Google.
  • Usted debe usar un depurador paso a través de su programa línea por línea, con el fin de determinar donde su comportamiento se aparta de lo que esperaba.
  • O(N^2) es el peor de los casos. Promedio y los Mejores son los de O(log N)
  • im sorry pensé que ya que está relacionado con la misma pregunta que yo haría aquí, creo que debo modificar mi segunda pregunta ya que no es el punto de lo que es el espacio de la complejidad de la pregunta debería ser ¿cómo puedo calcular el espacio de la complejidad de la misma.
  • Que es mucho más involucrados pregunta y probablemente debería ser incluido en una pregunta aparte (aunque puede encajar mejor dentro de una Pila de sitio de Exchange.)
  • El espacio de la complejidad de la ordenación rápida puede variar de O(log n) O(n)
  • En realidad, ambos están equivocados. El mejor caso es O(n x log n), el promedio de caso también es O (n x log n) y el peor caso es O (n x n).
  • El espacio de la complejidad de quicksort es O(n) causar en su lugar. Hablar de su tiempo de ejecución de la complejidad (que es O(n^2) y O(n log n) en promedio).
  • No está incluido el espacio en la pila, que es el principal punto de quicksort del espacio de la complejidad. Sin tomar en cuenta, no es de O(n), pero exactamente cero — nada se asignan a partir del montón.

InformationsquelleAutor GGio | 2012-06-25

1 Comentario

  1. 3

    Es en su función de partición, que se ordenan en orden descendente.

     while(true) {
     //ignore all the numbers greater than X to left
     while (A[i] > x) {
            i++;
        }
     //ignore all numbers lesser than X to right
     while (A[j] < x) {
            j--;
     }
    
     //swap a number lesser than X on left with a number greater than X on right
        if (i < j) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++;
            j--;
        } else {
            //Now the array is so sorted, that all numbers lesser than X are on right of it and greater than X are to left of it. Hence return position of X
            return j;
        }
     }

    //para ascendente:

     while(true) {
    
     while (A[i] < x) {
            i++;
     }
    
     while (A[j] > x) {
            j--;
     }
    
        if (i < j) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++;
            j--;
        } else {
            return j;
        }
    }
    • gracias acabo de cambiar a[i] < x y[j] > x y se ordenan en orden ascendente.
    • se trabaja para que la prueba de que yo siempre en mi pregunta, pero si puedo probar en esta entrada se va a bucle infinito: int a[] = { 1, 5, 1, 2, 10, 6, 9, 8, 3, 7, 4 };
    • ah, estaba pensando en el mismo. espera, voy a actualizar mi respuesta
    • funciona! gracias mucho, he modificado muchas cosas pero nunca vino a mi mente para aumentar y disminuir los valores de i y j no.

Dejar respuesta

Please enter your comment!
Please enter your name here