QuickSort und Hoare-Partition

Es fällt mir schwer, QuickSort mit Hoare-Partitionierung in C-Code zu übersetzen, und kann nicht herausfinden, warum. Der Code, den ich verwende, ist unten gezeigt:

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;
    }
}

Ich verstehe auch nicht wirklich warum HoarePartition funktioniert. Kann jemand erklären, warum es funktioniert, oder mich zumindest auf einen Artikel verlinken, der funktioniert?

Ich habe eine schrittweise Durcharbeitung des Partitionierungsalgorithmus gesehen, aber ich habe kein intuitives Gefühl dafür. In meinem Code scheint es nicht einmal zu funktionieren. Zum Beispiel angesichts des Arrays

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

Es wird Pivot 13 verwenden, aber am Ende mit dem Array enden

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

Und wird zurückkehren j welches ist a[j] = 11. Ich dachte, es sollte wahr sein, dass das Array, das an diesem Punkt beginnt und weitergeht, Werte haben sollte, die alle größer als der Pivot sind, aber das stimmt hier nicht, weil 11 < 13.

Hier ist Pseudocode für die Hoare-Partitionierung (von CLRS, zweite Ausgabe), falls dies nützlich ist:

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 

Vielen Dank!

BEARBEITEN:

Der richtige C-Code für dieses Problem lautet am Ende:

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;
    }
}

Um die Frage “Warum funktioniert die Hoare-Partitionierung?” zu beantworten:

Vereinfachen wir die Werte im Array auf nur drei Arten: L Werte (die kleiner als der Pivot-Wert sind), E Werte (die gleich dem Pivot-Wert sind) und G -Wert (jene, die größer als der Pivot-Wert sind).

Wir werden auch einem Ort im Array einen speziellen Namen geben; Wir nennen diesen Ort sund es ist der Ort, an dem die j Zeiger ist, wenn die Prozedur beendet ist. Wissen wir im Voraus, an welchem ​​Ort s ist? Nein, aber das wissen wir etwas Standort wird dieser Beschreibung entsprechen.

Mit diesen Begriffen können wir das Ziel des Partitionierungsverfahrens in etwas anderen Begriffen ausdrücken: Es besteht darin, ein einzelnes Array in zwei kleinere Sub-Arrays aufzuteilen, die sind nicht falsch sortiert in Bezug aufeinander. Die Anforderung „nicht falsch sortiert“ ist erfüllt, wenn die folgenden Bedingungen zutreffen:

1. Das “niedrige” Unterarray, das vom linken Ende des Arrays bis zu und einschließlich reicht senthält Nr G Werte.
2. Das “hohe” Sub-Array, das unmittelbar danach beginnt s und fährt bis zum rechten Ende fort, enthält Nr L Werte.

Das ist wirklich alles, was wir tun müssen. Wir müssen uns nicht einmal darum kümmern, wo die E Werte landen bei jedem gegebenen Pass. Solange jeder Durchlauf die Sub-Arrays in Bezug zueinander richtig macht, kümmern sich spätere Durchläufe um jede Unordnung, die innerhalb eines Sub-Arrays existiert.

Wenden wir uns nun der Frage von der anderen Seite zu: Wie stellt das Partitionierungsverfahren sicher, dass es keine gibt G Werte ein s oder links davon, und nein L Werte rechts von s?

Nun, “der Satz von Werten rechts von s” ist dasselbe wie “der Satz von Zellen der j Zeiger bewegt sich, bevor er erreicht s“. Und “der Satz von Werten links von und einschließlich s” ist dasselbe wie “der Satz von Werten, den die ich Zeiger bewegt sich vor j erreicht s“.

Das bedeutet, dass alle Werte, die sind falsch platziert wird sich bei einer Iteration der Schleife unter einem unserer beiden Zeiger befinden. (Nehmen wir der Einfachheit halber an, es ist die j Zeiger zeigt auf a L Wert, obwohl es genau das gleiche für die funktioniert ich Zeiger zeigt auf a G Wert.) Wo wird die ich Zeiger sein, wenn die j Zeiger steht auf falschem Wert? Wir wissen, dass es sein wird:

1. an einer Stelle im “niedrigen” Subarray, wo die L Wert kann ohne Probleme gehen;
2. zeigt auf einen Wert, der entweder ein ist E oder ein G Wert, der die leicht ersetzen kann L Wert unter dem j Zeiger. (Wenn es nicht auf einem war E oder ein G Wert, es hätte hier nicht aufgehört.)

Beachten Sie, dass manchmal die ich und j Der Zeiger wird tatsächlich beide anhalten E Werte. In diesem Fall werden die Werte vertauscht, obwohl dies nicht erforderlich ist. Das schadet aber nicht; Wir sagten vorher, dass die Platzierung der E -Werte können keine Fehlsortierung zwischen den Unterarrays verursachen.

Zusammenfassend funktioniert die Hoare-Partitionierung aus folgenden Gründen:

1. Es trennt ein Array in kleinere Sub-Arrays, die relativ zueinander nicht falsch sortiert sind;
2. Wenn Sie dies weiterhin tun und die Unterarrays rekursiv sortieren, bleibt am Ende nichts von dem Array übrig, das unsortiert ist.

Ich glaube, dass es zwei Probleme mit diesem Code gibt. Für den Anfang möchten Sie in Ihrer Quicksort-Funktion die Zeilen neu anordnen

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

damit du sie so hast:

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

Sie sollten jedoch noch mehr tun; insbesondere sollte dies lesen

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

Der Grund dafür ist, dass die Hoare-Partition nicht richtig funktioniert, wenn der Bereich, den Sie zu partitionieren versuchen, die Größe Null oder Eins hat. In meiner Ausgabe von CLRS wird dies nirgends erwähnt; Ich musste gehen die Errata-Seite des Buches um dies zu finden. Dies ist mit ziemlicher Sicherheit die Ursache des Problems, auf das Sie mit dem Fehler “Zugriff außerhalb des Bereichs” gestoßen sind, da Sie mit dieser defekten Invariante möglicherweise direkt aus dem Array laufen!

Was eine Analyse der Hoare-Partitionierung anbelangt, würde ich vorschlagen, damit zu beginnen, sie einfach von Hand nachzuvollziehen. Es gibt auch eine detailliertere Analyse hier. Intuitiv funktioniert es, indem zwei Bereiche von den Enden des Bereichs zueinander wachsen – einer auf der linken Seite, der Elemente enthält, die kleiner als der Pivot sind, und einer auf der rechten Seite, der Elemente enthält, die größer als der Pivot sind. Dies kann leicht modifiziert werden, um den Bentley-McIlroy-Partitionierungsalgorithmus (auf den im Link verwiesen wird) zu erzeugen, der gut skaliert, um gleiche Schlüssel zu verarbeiten.

Hoffe das hilft!

Ihr endgültiger Code ist falsch, da der Anfangswert von j sollte sein r + 1 Anstatt von r. Andernfalls ignoriert Ihre Partitionsfunktion immer den letzten Wert.

Eigentlich funktioniert HoarePartition, weil für jedes Array A[p...r] die mindestens 2 Elemente enthält (z p < r), jedes Element von A[p...j] ist <= jedes Element von A[j+1...r] wenn es endet. Die nächsten beiden Segmente, auf denen der Hauptalgorithmus wiederkehrt, sind also [start...q] und [q+1...end]

Der richtige C-Code lautet also wie folgt:

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;
    }
}

Weitere Klarstellungen:

1. Partitionsteil ist nur die Übersetzung des Pseudocodes. (Beachten Sie, dass der Rückgabewert ist j)

2. Beachten Sie für den rekursiven Teil, dass die Basisfallprüfung (end <= start Anstatt von end <= start + 1 andernfalls überspringen Sie die [2 1] Subarray)

Zunächst einmal hat u den Partitionsalgorithmus von Hoare missverstanden, was aus dem übersetzten Code in c ersichtlich ist, da u Pivot als ganz linkes Element des Subarrays betrachtete.

Ich werde erklären, dass Sie das Element ganz links als Drehpunkt betrachten.

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

Hier stellen p und r die untere und obere Grenze des Arrays dar, die auch Teil eines größeren Arrays (Subarray) sein können, das partitioniert werden soll.

Also beginnen wir mit den Zeigern (Marker), die zunächst auf vor und nach den Endpunkten des Arrays zeigen (einfach bcoz mit do while-Schleife).

i=p-1,

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

Jetzt wollen wir gemäß der Partitionierung, dass jedes Element links von Pivot kleiner oder gleich Pivot und größer als auf der rechten Seite von Pivot ist.

Also bewegen wir die Markierung ‘i’, bis wir ein Element erhalten, das größer oder gleich Pivot ist. Und ähnlich ‘j’-Marker, bis wir ein Element finden, das kleiner oder gleich Pivot ist.

Wenn nun i < j, tauschen wir die Elemente aus, weil beide Elemente im falschen Teil des Arrays sind. Code wird also sein

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

Wenn nun ‘i’ nicht kleiner als ‘j’ ist, bedeutet dies, dass jetzt kein Element dazwischen zum Austauschen vorhanden ist, sodass wir die Position ‘j’ zurückgeben.

Jetzt ist das Array nach der partitionierten unteren Hälfte von ‘start to j’

obere Hälfte ist von ‘j+1 bis Ende’

so wird der Code aussehen

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);
}

Einfache Implementierung in 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;
    }
}

Ihr letzter C-Code funktioniert. Aber es ist nicht intuitiv. Und jetzt studiere ich glücklicherweise CLRS. Meiner Meinung nach ist der Pseudocode von CLRS falsch. (Bei 2e) Endlich finde ich, dass es richtig wäre, wenn man einen Ort ändert.

 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

Ja, Austausch A hinzufügen[r] ↔ A[i] kann es zum Laufen bringen. Wieso den? Weil ein[i] ist jetzt größer als A[r] ODER ich == r. Wir müssen also austauschen, um die Funktion einer Partition zu gewährleisten.

1. Pivot zuerst verschieben. (z. B. Mittelwert von drei verwenden. Wechseln Sie zu Einfügesortierung für kleine Eingabegröße.)
2. Teilung,
   • tausche wiederholt die aktuell ganz linke 1 mit der aktuell ganz rechten 0 aus.
     0 – cmp(Wert, Drehpunkt) == wahr, 1 – cmp(Wert, Drehpunkt) == falsch.
     stoppen, wenn nicht links < rechts.
   • Tauschen Sie danach den Pivot mit der ganz rechten 0 aus.