Quick Sort - Implementierung

136774
Software Engineer

Kann in diesem Code etwas verbessert werden?

#include <iostream>
using namespace std;

void print(int *a, int n)
{
    int i=0;
    while(i<n){
        cout<<a[i]<<",";
        i++;
    }
}

void swap(int i,int j, int *a){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}


void quicksort(int *arr, int left, int right){
    int min = (left+right)/2;
    cout<<"QS:"<<left<<","<<right<<"\n";

    int i = left;
    int j = right;
    int pivot = arr[min];

    while(left<j || i<right)
    {
        while(arr[i]<pivot)
        i++;
        while(arr[j]>pivot)
        j--;

        if(i<=j){
            swap(i,j,arr);
            i++;
            j--;
        }
        else{
            if(left<j)
                quicksort(arr, left, j);
            if(i<right)
                quicksort(arr,i,right);
            return;
        }
    }
}


int main() {
    int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};
    quicksort(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1);
    print(arr, (sizeof(arr)/sizeof(arr[0])));
    return 0;
}
Antworten
7
Bearbeiten Sie den Originalcode nicht auf der Grundlage von Antworten. Jamal vor 5 Jahren 2
Es ist sehr interessant, dass niemand erwähnt, dass bei kleinen Arrays eine etwas kompliziertere, aber schnellere Sortierung mit zwei oder drei Pivots verwendet wird. Erwägen Sie die Überprüfung einer professionellen Java-Implementierung, wenn in C ++ noch keine verfügbar ist: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/46c727d6ecc2/src/share/classes/java/util/DualPivotQuicksort.java David McManamon vor 3 Jahren 0

4 Antworten auf die Frage

28
rolfl

Im Allgemeinen ist der Code sauber und leicht zu befolgen. Der QuickSort-Algorithmus ist relativ traditionell und die Teile, die ich erwarte, beziehen sich auf den Ort, an dem sie erwartet werden.

Lass uns die Probleme durchgehen, die ich sehe ... und einige von ihnen sind ernsthaft ...

Namensräume

Die Verwendung namespace::stdist im Allgemeinen eine schlechte Idee. Die Möglichkeit einer Namensraumverschmutzung ist real. Sie haben zwar eine swapFunktion implementiert und es gibt bereits eine std::swap, aber wir werden darauf eingehen.

Stil

  • Sie haben eine Variable min, aber das sollte sein mid.

  • Manchmal setzen Sie die Funktionsparameter mit den Links / Rechts-Indizes vor dem Array und manchmal danach. Du hast:

    void quicksort(int *arr, int left, int right) {
    

    und du hast auch:

    void swap(int i,int j, int *a) {
    

    Wählen Sie eine aus und bleiben Sie dabei. Ich würde persönlich empfehlen, zuerst das Array und danach die Indizes zu setzen.

  • Verwenden Sie Leerzeichen entsprechend. Operatoren wie der <<Operator coutsind Operatoren wie alle anderen. Nutzen Sie den Platz, um die Lesbarkeit zu verbessern:

    cout<<"QS:"<<left<<","<<right<<"\n";
    

    sollte sein:

    std::cout << "QS:" << left << "," << right << "\n";
    

Bugs

Sie haben hier ein paar Fehler, die behoben werden sollten:

  1. Bei der Berechnung des Mittelpunkts besteht die Möglichkeit eines Ganzzahlüberlaufs. Dies ist ein "berühmter" Fehler . Ihr Code int min = (left+right)/2;sollte folgendermaßen erfolgen:

    int mid = left + (right - left) / 2;
    

    Die obige Lösung läuft nicht über.

  2. Wenn Sie die Daten partitionieren, sollten Sie Werte, die dem Pivotwert entsprechen, entweder links oder rechts vom Pivot betrachten. Ihren Code verwenden Sie streng <oder >abhängig davon, ob Sie rechts oder links sind. Eines davon sollte enthalten =. Ihr Code wird so wie er ist den aktuellen Pivot-Wert durchlaufen und ein paar funky Geschäfte damit machen. Am Ende bewegen Sie den Drehpunkt auf verschiedene Weise.

  3. Sie haben möglicherweise einen möglichen Überlauf (Pufferüberlauf) in Ihren Schleifenbedingungen. Es ist möglich, wenn Sie im Schwenkbereich zu dieser Linie kommen:

        while(arr[i]<pivot)
            i++;
    

    damit ich am Ende des Arrays abläuft. Wenn alle verbleibenden Werte unter dem Pivot liegen, gibt es nichts, was den Abbruch verhindert. Sie müssen immer noch in diesen Schleifen gegen j prüfen.

Wechsel

C ++ hat eine Swap-Funktion, verwenden Sie sie . Um es von C ++ 11 #include<utility>und davor zu bekommen#include<algorithm>

Algorithmus

Die klassische Schnellauswahl erfolgt in 5 Schritten:

  1. Finden Sie einen Pivot-Wert.
  2. Verschieben Sie alle Werte unterhalb (oder gleich) des Pivot-Werts nach 'links'.
  3. Verschieben Sie alle Werte, die größer als der Drehpunkt sind, nach 'rechts'.
  4. Schnelles Sortieren der Werte unter (oder gleich)
  5. Werte schnell größer sortieren als.

Beachten Sie, dass viele Lehrbücher die ersten 3 Stufen in eine Partitionierungsfunktion extrahieren. Der Zweck dieser Funktion besteht darin, den Pivot-Wert zu identifizieren, die Kandidaten zu verschieben und dann den Pivot-Wert wieder in die Daten an der richtigen Stelle einzufügen.

Der letzte Teil ist der Schlüssel, er lässt den Pivot-Wert an der Stelle liegen, an der er sich befinden soll. Das bedeutet, dass Sie diesen Pivot-Wert nie wieder in die Sortierungen aufnehmen müssen.

Lassen Sie uns diese Logik in ihre Methoden aufschlüsseln, mit der Annahme, dass es eine "schwenkende" Funktion gibt, die die ersten drei Schritte ausführt. Dies führt zu einem einfacheren Quicksort, der wie folgt aussieht:

void quicksort(int *arr, const int left, const int right){

    if (left >= right) {
        return;
    }

    int part = partition(arr, left, right);

    quicksort(arr, left, part - 1, sz);
    quicksort(arr, part + 1, right, sz);
}

Beachten Sie oben, dass die Überprüfung der Gültigkeit der Eingaben beim Eintritt in die rekursive Funktion erfolgt. Dies vereinfacht den letzten Teil der Funktion. Der gleiche Code könnte alternativ ähnlich wie Ihr geschrieben werden:

void quicksort(int *arr, const int left, const int right, const int sz){

    int part = partition(arr, left, right);
    std::cout << "QSC:" << left << "," << right << " part=" << part << "\n";
    print (arr, sz);

    if (left < part - 1) {
        quicksort(arr, left, part - 1, sz);
    }
    if (part + 1 < right) {
        quicksort(arr, part + 1, right, sz);
    }
}

Ich bevorzuge den ersten .... es macht es einfacher, den Rekursionsabschluss zu erkennen.

Das ist jetzt ein einfacheres Quicksort: Partitionieren Sie die Daten, sortieren Sie jede Partition (aber nicht den tatsächlichen Partitionierungswert, der sich an der richtigen Stelle befindet).

Wie partitionieren Sie die Daten?

Der Trick hier ist, den Pivot-Wert an den Anfang der Sequenz zu vertauschen, die restlichen Werte zu partitionieren und dann den Pivot-Wert wieder dahin zu vertauschen, wo er hingehört:

int partition(int *arr, const int left, const int right) {
    const int mid = left + (right - left) / 2;
    const int pivot = arr[mid];
    // move the mid point value to the front.
    std::swap(arr[mid],arr[left]);
    int i = left + 1;
    int j = right;
    while (i <= j) {
        while(i <= j && arr[i] <= pivot) {
            i++;
        }

        while(i <= j && arr[j] > pivot) {
            j--;
        }

        if (i < j) {
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i - 1],arr[left]);
    return i - 1;
}

Beachten Sie, wie der obige Code den Pufferüberlauf überprüft.

Wenn ich das alles zusammenstelle und einige der Debug-Anweisungen, die Sie haben, belassen würde, hätte ich den Code:

#include <iostream>
#include <algorithm>

void print(int *a, int n)
{
    int i = 0;
    while(i < n){
        std::cout << a[i] << ",";
        i++;
    }
    std::cout << "\n";
}

int partition(int *arr, const int left, const int right) {
    const int mid = left + (right - left) / 2;
    const int pivot = arr[mid];
    // move the mid point value to the front.
    std::swap(arr[mid],arr[left]);
    int i = left + 1;
    int j = right;
    while (i <= j) {
        while(i <= j && arr[i] <= pivot) {
            i++;
        }

        while(i <= j && arr[j] > pivot) {
            j--;
        }

        if (i < j) {
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i - 1],arr[left]);
    return i - 1;
}

void quicksort(int *arr, const int left, const int right, const int sz){

    if (left >= right) {
        return;
    }


    int part = partition(arr, left, right);
    std::cout << "QSC:" << left << "," << right << " part=" << part << "\n";
    print (arr, sz);

    quicksort(arr, left, part - 1, sz);
    quicksort(arr, part + 1, right, sz);
}

int main() {
    int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};
    int sz = sizeof(arr)/sizeof(arr[0]);
    print(arr, sz);
    quicksort(arr, 0, sz - 1, sz);
    print(arr, sz);
    return 0;
}

Ich habe das auch in Ideone gesetzt .

7
Martin York

Technik:

Statt Indizes in ein Array zu schreiben, sollten Sie Ihren Algorithmus in Iteratoren schreiben.

quicksort(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1);

Viel einfacher zu schreiben als:

quicksort(std::begin(arr), std::end(arr));

Der Iterator scheidet Ihren Algorithmus von dem Container ab, an dem er gerade arbeitet. Es funktioniert also genauso gut mit Arrays und std :: Vectors und std :: array etc ..

Klarheit

Du solltest diese Magie nicht mehr brauchen (sizeof(arr)/sizeof(arr[0]))-1. Ein paar Probleme damit. Es ist sehr anfällig für das Ausschneiden und Einfügen von Problemen (da Arrays sehr schnell in Zeiger zerfallen, funktionieren die obigen Funktionen möglicherweise sehr schnell, wenn sie zu einer Funktion verschoben werden (wenn sie nicht korrekt ausgeführt werden)).

In Sachen Code-Klarheit sollten Sie eine Funktion schreiben, die für Sie Größe hat:

template <typename T, std::size_t N>
constexpr std::size_t getSize(T const (&)[N])
{ 
    return N;
}

Nun wird Ihr Code selbstdokumentierend:

quicksort(arr, 0, getSize(arr)-1);

Es zeigt auch deutlicher, dass Sie nicht idiomatisches C ++ (-1) verwenden. Bereiche in C ++ werden in Ausdrücken ausgedrückt [beginning, end). dh. endist eins hinter dem Ende des Containers. Dies geschieht überall in C ++ - Code. Wenn Sie von dieser Redewendung abbrechen, werden Sie mit anderen C ++ - Entwicklern sehr verwirrt.

Compiler-Job

Keine Arbeit, die der Compiler für Sie erledigen kann:

int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};

Der Compiler ist sowieso besser als Sie und verhindert Fehler. Sie haben gesagt, die Anzahl der Elemente ist 8. Als Mensch kann ich nicht erkennen, dass ich sie auf einen Blick zählen könnte, aber als Mensch bin ich faul und gehe davon aus, dass Sie es richtig verstanden haben. Wenn Sie es nicht richtig verstanden haben, werden wir Probleme haben.

Lassen Sie den Compiler es herausfinden.

int arr[] = {110, 5, 10,3 ,22, 100, 1, 23};

Wenn nun die Größe des Arrays geändert wird, müssen Sie nur noch eine Sache (die Daten) ändern. Anstatt zwei Dinge (Daten und Größe).

4
Hosch250

Ich sehe hier ein paar Dinge, die verbessert werden können und die sehr falsch aussehen. Das sieht sehr falsch aus:

while(arr[i]<pivot)
i++;
while(arr[j]>pivot)
j--;

Es sieht fast so aus, als ob Sie das nicht beabsichtigt hätten, weil Sie keine geschweiften Klammern haben und die Einrückungsebene gleich ist.

Dies sollte so geschrieben werden:

while (arr[i]<pivot) {
    i++;
}
while (arr[j]>pivot) {
    j--;
}

Ihr Code ist in der Regel sehr ordentlich, aber Ihr Stil ist ein bisschen abwegig. In C ++ werden normalerweise geschweifte Klammern verwendet :

void SomeFunction()
{
    while (condition) {
        // some code here
    }

    if (condition) {
        // some code here
    } else {
        // else code here
    }

    // and so on

    // Many people use the Stroustrup variant too, without a cuddled else:
    if (condition) {
        // some code here
    }
    else {
        // else code here
    }
}

Ihre Zahnspangen haben nicht immer den gleichen Stil, und manchmal verwenden Sie überhaupt keine Zahnspangen. Sie sollten immer Klammern verwenden, auch wenn nur eine Anweisung im Block enthalten ist, und Sie sollten immer denselben Stil verwenden.

Es ist auch üblich, Leerzeichen um Operatoren zu setzen, um die Lesbarkeit zu verbessern: left < jstatt left<j.


Schließlich ist es nicht empfehlenswert, die Funktion immer einzuschließen, using namespace std;da sich Namen in Namespaces manchmal überlappen, was zu Compiler-Fehlern oder undefiniertem Verhalten führt. Stattdessen sollten Sie genau angeben, welchen Namespace Sie verwenden, indem Sie std::vor dem Namen platzieren.

3
Brythan

Ich gehe davon aus, dass Sie qsort(C-Implementierung von Quicksort) und std::sort(C ++ - Sortierroutine) kennen. Daher machen Sie dies als Programmierübung. Es gibt ein Erkennungszeichen für das , wenn Sie in Zukunft etwas ähnliches tun.

using namespace std;

Warum ist die Verwendung von Namespace std eine schlechte Praxis? Beachten Sie, dass die Kurzversion darin besteht, dass sie zu Codekonflikten führen und es schwierig machen kann, den Ursprung des Codes zu bestimmen. Zum Beispiel könnte jemand, der sich Ihren Code ansieht, denken, dass Sie ihn benutzt haben std::swap.

int i=0;
while(i<n){
    cout<<a[i]<<",";
    i++;
}

Dies ist möglicherweise ein guter Zeitpunkt, um eine forSchleife zu verwenden. Der Hauptgrund ist, dass die Logik genau übereinstimmt.

// decrement n so as not to have an extra comma at the end
--n;
for ( int i = 0; i < n; ++i ) {
    std::cout << a[i] << ", ";
}

// print the last entry without a trailing comma
std::cout << a[n] << std::endl;

Jetzt ist die Loop-Definition auf einer Zeile und nicht über drei Zeilen verteilt. Es gibt Zeiten, in denen es Ihnen genauso gut geht, a whileals a zu verwenden for, aber dies ist keine davon.

Beachten Sie, dass wir das nachgestellte Komma auch entfernen können, indem Sie die Schleifengrenze anpassen.

Fügt außerdem einige horizontale Leerzeichen hinzu, damit Sie leichter erkennen können, wo ein Zeichen endet und ein anderes beginnt.

Fügt ein Zeilenende hinzu (wodurch auch die Ausgabe geleert wird), da dies in diesem Code sinnvoll war. Sie können dies deaktivieren, wenn Sie möchten, dass der Code etwas allgemeiner ist. Dann sollten Sie es in Ihrer mainFunktion tun . Andernfalls beginnen Sie mit dem Cursor in derselben Zeile wie die Ausgabe, was verwirrend ist.

void quicksort(int *arr, int left, int right){

Durch den Variablennamen arrfühle ich mich immer wie ein Pirat. Es ist nicht so viel beschreibender als a.

cout<<"QS:"<<left<<","<<right<<"\n";

Dies ist ein Debugging-Code. Wenn Sie eine Codeüberprüfung erhalten, sollte Ihr Debugging-Code nicht mehr in Ihrer Funktion sein.

std::cout << "QS:" << left << "," << right << std::endl;

Wenn Sie Debugging-Code verwenden, sollten Sie std::endlstatt a verwenden "\n". Dies ist etwas langsamer, da es einen Flush auslöst, aber beim Debuggen ist es wahrscheinlich besser, wenn der Code etwas langsamer ist und der Ausgabepuffer nichts enthält. Wenn Ihr Programm abstürzt, können Sie auf diese Weise sehen, wie weit es gekommen ist.

int min = (left+right)/2;

Ich finde diesen Namen verwirrend. Der Name ist minnormalerweise eine Abkürzung für Minimum, aber Sie wählen nicht das Minimum aus. Sie nehmen tatsächlich das mittlere Element des Bereichs. Ein typischerer Name wäre mid, obwohl ich den ganzen Weg gehen und sagen würde middle.

Sie können jedoch eine bessere durchschnittliche Leistung erzielen, wenn Sie einen zufälligen Drehpunkt auswählen. Die Auswahl des mittleren Elements kann im ungünstigsten Fall zu einer Komplexität von \ $ O (n ^ 2) \ $ führen. Das Problem tritt auf, wenn das mittlere Element immer entweder das kleinste oder das größte Element im Bereich ist.

    while(arr[i]<pivot)
    i++;

Das ist unklar. Sie sollten den Inhalt der Schleifen immer relativ zum Schleifenbefehl einrücken. Auf diese Weise können wir leicht erkennen, dass sich die Anweisung in der Schleife befindet.

    while ( arr[i] < pivot )
        i++;

Noch besser, gehen Sie den ganzen Weg und schreiben Sie

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

Dies macht nicht nur deutlich, was sich in der Schleife befindet und was nicht, sondern schützt vor dem zufälligen Hinzufügen einer Anweisung außerhalb der Schleife, in der Sie beabsichtigt waren. In der Praxis dauert das Debuggen eines Fehlers mehr Zeit als das Hinzufügen von tausend geschweiften Klammerpaaren.

int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};

Es kann eine Ausrede geben, um es arrin der quicksortFunktion aufzurufen, bei der Sie nicht wirklich wissen, was es bedeutet. Hier sollte man es jedoch als etwas Beschreibenderes bezeichnen test_data.

int test_data[8] = {110, 5, 10,3 ,22, 100, 1, 23};
int test_data_count = sizeof(test_data)/sizeof(test_data[0]);

Ich würde auch vorgehen und die Anzahl der Elemente vorab bestimmen. Sie verwenden denselben Ausdruck zweimal. Anstatt sich zu wiederholen, berechne es vor.

quicksort(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1);
print(arr, (sizeof(arr)/sizeof(arr[0])));

Jetzt müssen wir dies an unsere vorherigen Änderungen anpassen.

quicksort(test_data, 0, test_data_count-1);
print(test_data, test_data_count);

Dies hat den Nebeneffekt, dass es viel einfacher wird, zu sehen, was Sie tun. Dieser Ausdruck zählt die Anzahl der Elemente in test_data. Wir übergeben dann einen dritten quicksortWert als dritten Parameter an und wir übergeben den genauen Betrag an print.