Partición QuickSort y Hoare

Tengo dificultades para traducir QuickSort con partición Hoare en código C, y no puedo averiguar por qué. El código que estoy usando se muestra a continuación:

void QuickSort(int a[],int start,int end) {
    int q=HoarePartition(a,start,end);
    if (end<=start) return;
    QuickSort(a,q+1,end);
    QuickSort(a,start,q);
}

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r;
    while (1) {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);

        if  (i < j)
            swap(&a[i],&a[j]);
        else
            return j;
    }
}

Además, realmente no entiendo por qué HoarePartition obras. ¿Alguien puede explicar por qué funciona, o al menos vincularme a un artículo que lo haga?

He visto un trabajo paso a paso del algoritmo de partición, pero no tengo una sensación intuitiva para ello. En mi código, ni siquiera parece funcionar. Por ejemplo, dada la matriz

13 19  9  5 12  8  7  4 11  2  6 21

Usará el pivote 13, pero terminará con la matriz

 6  2  9  5 12  8  7  4 11 19 13 21 

y regresará j cual es a[j] = 11. Pensé que se suponía que era cierto que la matriz que comienza en ese punto y avanza debe tener valores que son todos más grandes que el pivote, pero eso no es cierto aquí porque 11

Aquí hay un pseudocódigo para la partición de Hoare (de CLRS, segunda edición), en caso de que sea útil:

Hoare-Partition (A, p, r)
    x ← A[p]
    i ← p − 1
    j ← r + 1
    while  TRUE
        repeat   j ←  j − 1
            until     A[j] ≤ x
        repeat   i ←  i + 1
            until     A[i] ≥ x
        if  i < j
            exchange  A[i] ↔ A[j]
        else  return   j 

¡Gracias!

EDITAR:

El código C correcto para este problema terminará siendo:

void QuickSort(int a[],int start,int end) {
    int q;
    if (end-start<2) return;
    q=HoarePartition(a,start,end);
    QuickSort(a,start,q);
    QuickSort(a,q,end);
}

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r;
    while (1) {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);
        if  (i < j) 
            swap(&a[i],&a[j]);
        else 
            return j+1;
    }
}

Para responder a la pregunta “¿Por qué funciona la partición de Hoare?”:

Simplifiquemos los valores en la matriz a solo tres tipos: L valores (aquellos menores que el valor pivote), mi valores (aquellos iguales al valor pivote), y GRAMO valor (aquellos más grandes que el valor de pivote).

También le daremos un nombre especial a una ubicación en la matriz; llamaremos a esta ubicación sy es el lugar donde el j puntero es cuando finaliza el procedimiento. ¿Sabemos de antemano qué ubicación s ¿es? No, pero sabemos que algunos la ubicación cumplirá con esa descripción.

Con estos términos, podemos expresar el objetivo del procedimiento de partición en términos ligeramente diferentes: es dividir un solo arreglo en dos sub-arreglos más pequeños que son no mal clasificado uno con respecto al otro. Ese requisito de “no mal clasificado” se cumple si se cumplen las siguientes condiciones:

1. El subarreglo “bajo”, que va desde el extremo izquierdo del arreglo hasta e incluye sno contiene GRAMO valores.
2. El subarreglo “alto”, que comienza inmediatamente después s y continúa hacia el extremo derecho, no contiene L valores.

Eso es realmente todo lo que tenemos que hacer. Ni siquiera tenemos que preocuparnos de dónde está el mi los valores terminan en cualquier paso dado. Siempre y cuando cada paso tenga los subconjuntos correctos entre sí, los pases posteriores se encargarán de cualquier desorden que exista dentro de cualquier subconjunto.

Así que ahora abordemos la pregunta desde el otro lado: ¿cómo garantiza el procedimiento de partición que no haya GRAMO valores en s o a la izquierda de él, y no L valores a la derecha de s?

Bueno, “el conjunto de valores a la derecha de ses lo mismo que “el conjunto de celdas j el puntero se mueve antes de llegar s“. Y “el conjunto de valores a la izquierda de e incluyendo s” es lo mismo que “el conjunto de valores que el I el puntero se mueve antes j alcanza s“.

Eso significa que cualquier valor que están mal colocado estará, en alguna iteración del bucle, bajo uno de nuestros dos punteros. (Por conveniencia, digamos que es el j puntero apuntando a un L valor, aunque funciona exactamente igual para el I puntero apuntando a un GRAMO valor.) ¿Dónde estará el I puntero ser, cuando el j puntero está en un valor fuera de lugar? Sabemos que será:

1. en una ubicación en el subarreglo “bajo”, donde el L el valor puede ir sin problemas;
2. apuntando a un valor que es un mi o un GRAMO valor, que puede reemplazar fácilmente el L valor bajo el j puntero. (Si no fuera en un mi o un GRAMO valor, no se habría detenido allí.)

Tenga en cuenta que a veces el I y j el puntero en realidad se detendrá en mi valores. Cuando esto sucede, los valores se cambiarán, aunque no sea necesario. Sin embargo, esto no hace ningún daño; decíamos antes que la colocación de la mi los valores no pueden causar una clasificación incorrecta entre los subconjuntos.

Entonces, para resumir, la partición de Hoare funciona porque:

1. Separa una matriz en sub-matrices más pequeñas que no están mal ordenadas entre sí;
2. Si continúa haciendo eso y ordenando recursivamente los sub-arreglos, eventualmente no quedará nada del arreglo sin ordenar.

Creo que hay dos problemas con este código. Para empezar, en su función Quicksort, creo que desea reordenar las líneas

 int q=HoarePartition(a,start,end);
 if (end<=start) return;

para que los tengas así:

 if (end<=start) return;
 int q=HoarePartition(a,start,end);

Sin embargo, debe hacer incluso más que esto; en particular esto debería leer

 if (end - start < 2) return;
 int q=HoarePartition(a,start,end);

La razón de esto es que la partición de Hoare no funciona correctamente si el rango que está tratando de particionar tiene un tamaño cero o uno. En mi edición de CLRS esto no se menciona en ninguna parte; tuve que ir a página de erratas del libro para encontrar esto. Es casi seguro que esta es la causa del problema que encontró con el error “acceso fuera de rango”, ya que con ese invariante roto, ¡podría salirse de la matriz!

En cuanto a un análisis de la partición de Hoare, sugeriría comenzar simplemente trazándolo a mano. También hay un análisis más detallado. aquí. Intuitivamente, funciona haciendo crecer dos rangos desde los extremos del rango uno hacia el otro: uno en el lado izquierdo que contiene elementos más pequeños que el pivote y otro en el lado derecho que contiene elementos más grandes que el pivote. Esto se puede modificar ligeramente para producir el algoritmo de particionamiento de Bentley-McIlroy (al que se hace referencia en el enlace) que escala muy bien para manejar claves iguales.

¡Espero que esto ayude!

Su código final es incorrecto, ya que el valor inicial de j debiera ser r + 1 en lugar de r. De lo contrario, su función de partición siempre ignorará el último valor.

En realidad, HoarePartition funciona porque para cualquier matriz A[p...r] que contiene al menos 2 elementos (es decir, p < r), cada elemento de A[p...j] es <= cada elemento de A[j+1...r] cuando termina. Entonces, los siguientes dos segmentos en los que recurre el algoritmo principal son [start...q] y [q+1...end]

Entonces, el código C correcto es el siguiente:

void QuickSort(int a[],int start,int end) {
    if (end <= start) return;
    int q=HoarePartition(a,start,end);
    QuickSort(a,start,q);
    QuickSort(a,q + 1,end);
}

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r+1;
    while (1) {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);
        if  (i < j) 
            swap(&a[i],&a[j]);
        else 
            return j;
    }
}

Más aclaraciones:

1. parte de la partición es solo la traducción del pseudocódigo. (Tenga en cuenta que el valor de retorno es j)

2. para la parte recursiva, tenga en cuenta que la verificación del caso base (end <= start en lugar de end <= start + 1 de lo contrario, se saltará el [2 1] subarreglo)

En primer lugar, entendió mal el algoritmo de partición de Hoare, que se puede ver en el código traducido en c, ya que consideró el pivote como el elemento más a la izquierda del subarreglo.

Te explicaré si consideras el elemento más a la izquierda como pivote.

int HoarePartition (int a[],int p, int r) 

Aquí p y r representan el límite inferior y superior de la matriz que también puede ser parte de una matriz más grande (sub-matriz) para ser dividida.

así que comenzamos con los punteros (marcadores) que apuntan inicialmente a los puntos finales antes y después de la matriz (simplemente porque usamos do while loop). Por lo tanto,

i=p-1,

j=r+1;    //here u made mistake

Ahora, según la partición, queremos que cada elemento a la izquierda del pivote sea menor o igual que el pivote y mayor que en el lado derecho del pivote.

Así que moveremos el marcador ‘i’ hasta que obtengamos un elemento que sea mayor o igual que el pivote. Y de manera similar, el marcador ‘j’ hasta que encontremos un elemento menor o igual que el pivote.

Ahora, si i

do  j--; while (a[j] <= x);                 //look at inequality sign
do  i++; while (a[i] >= x);
if  (i < j) 
    swap(&a[i],&a[j]);

Ahora, si ‘i’ no es menor que ‘j’, eso significa que ahora no hay ningún elemento intermedio para intercambiar, por lo que regresamos a la posición ‘j’.

Entonces ahora la matriz después de la mitad inferior particionada es de ‘inicio a j’

la mitad superior es desde ‘j+1 hasta el final’

entonces el código se verá como

void QuickSort(int a[],int start,int end) {
    int q=HoarePartition(a,start,end);
    if (end<=start) return;
    QuickSort(a,start,q);
    QuickSort(a,q+1,end);
}

Implementación sencilla en java.

public class QuickSortWithHoarePartition {

    public static void sort(int[] array) {
        sortHelper(array, 0, array.length - 1);
    }

    private static void sortHelper(int[] array, int p, int r) {
        if (p < r) {
            int q = doHoarePartitioning(array, p, r);
            sortHelper(array, p, q);
            sortHelper(array, q + 1, r);
        }
    }

    private static int doHoarePartitioning(int[] array, int p, int r) {
        int pivot = array[p];
        int i = p - 1;
        int j = r + 1;

        while (true) {

            do {
                i++;
            }
            while (array[i] < pivot);

            do {
                j--;
            }
            while (array[j] > pivot);

            if (i < j) {
                swap(array, i, j);
            } else {
                return j;
            }
        }

    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Su último código C funciona. Pero no es intuitivo. Y ahora estoy estudiando CLRS por suerte. En mi opinión, el pseudocódigo de CLRS está mal. (En 2e) Por fin, encuentro que estaría bien si cambiara de lugar.

 Hoare-Partition (A, p, r)
 x ← A[p]
     i ← p − 1
     j ← r + 1
 while  TRUE
        repeat   j ←  j − 1
            until     A[j] ≤ x
    repeat   i ←  i + 1
            until     A[i] ≥ x
    if  i < j
              exchange  A[i] ↔ A[j]
    else  
              exchnage  A[r] ↔ A[i]  
              return   i

Sí, agregar un intercambio A[r] ↔ un[i] puede hacer que funcione. ¿Por qué? Porque un[i] ahora es más grande que A[r] O yo == r. Entonces debemos intercambiar para garantizar la característica de una partición.

1. mover el pivote a primera. (p. ej., use la mediana de tres. cambie a ordenación por inserción para tamaño de entrada pequeño).
2. dividir,
   • intercambiar repetidamente el 1 actualmente más a la izquierda con el 0 actualmente más a la derecha.
     0 — cmp(val, pivote) == verdadero, 1 — cmp(val, pivote) == falso.
     detener si no izquierda
   • después de eso, cambie el pivote con el 0 más a la derecha.