Schnellsortierung vs Auswahlsortierung (Java vs C ++)

Ihre Quicksort-Funktion gibt bei jedem rekursiven Aufruf Ihren gesamten Vektor als Wert zurück, auch wenn die Funktion dies an Ort und Stelle ändert. Vermutlich alle diese Provisorien zurückzugeben und sie dann wegzuschmeißen, schmerzt die Leistung.

Ändern Sie einfach die Funktion in void und entfernen Sie die Endrückgabe und sehen Sie, wie sie sich verhält.

BEARBEITEN: Wenn Sie mehr an Java gewöhnt sind, wo fast alles vergeudete Referenzen sind, beachten Sie, dass in C ++ eine Rückgabe nach Wert (wie beim Rückgabetyp) in der Regel eine Kopie von allem ergibt, was zurückgegeben wird. Und @Johannes Schaub - litb weist darauf hin, dass der Compiler nicht in der Lage ist, die Rückkehr zu optimieren, weil er keine automatische (lokale) Variable zurückgibt.

EDIT2: Wenn Sie dies nicht als Übung machen, sollten Sie entweder std::sort oder std::stable_sort verwenden (letzteres, wenn Sie wissen, dass Ihre Daten bereits fast sortiert sind oder Sie die Reihenfolge der Duplikate beibehalten müssen) ). Zum Beispiel std::sort(A.begin(), A.end());

Sie geben bei jedem rekursiven Aufruf einen vollständigen Vektor zurück. Das kostet viel Zeit (99,99% der Kopierzeit).

Übrigens, Sie können die STL-Sortierfunktion in C ++ verwenden, es ist garantiert ein Quicksort (obwohl das Ihr Profiling durcheinander bringen wird, weil Sie keinen echten Vergleich machen).

BEARBEITEN:

Anscheinend ist std::sort nicht garantiert Quicksort, aber es ist garantiert O (n * log (n)). Quelle

Es gibt noch ein weiteres Problem mit Ihrem C ++ - Code, auf den noch niemand hingewiesen zu haben scheint. Wenn wir den Timing-Code loswerden, wird es ziemlich offensichtlich:

Sie sortieren die Auswahl nach Daten, die bereits sortiert sind. Unter diesen Umständen macht es wahrscheinlich keinen großen Unterschied, hilft aber trotzdem einigen. Wenn Sie eine Einfügesortierung verwenden, würde dies praktisch sofort angezeigt.

Das Problem hängt wahrscheinlich mit Ihrer Implementierung von Quicksort zusammen. Wenn Sie die Überschrift einfügen und std::sort verwenden, was nicht Quicksort, sondern Introsort ist, eine Variante, die die Performance im schlechtesten Fall verbessern soll, sind die Ergebnisse ziemlich unterschiedlich:

Während ich mit Ihrer Implementierung von quicksort arbeite, bekomme ich ähnliche Ausgaben wie:

Die Hardware ist ein Core2-Duo 2GHz, und ich habe mit g++ -O3 -o CompareSorts CompareSorts.cpp kompiliert (beachte, dass -O3 wichtig ist: es teilt gcc mit, so viel wie möglich zu optimieren).

Ihr C ++ Code ist fehlgeschlagen. Erstens bietet der Standard bereits eine Quicksort- std::sort . Zweitens haben Sie ein std::vector - für ein Array mit statischer Größe ausgewählt? Drittens sind ftime und der Rest nicht gültige Profilierungstimer. Drittens, Sie geben immer Werte von quicksort zurück, obwohl die Funktion eine Referenz akzeptiert. Wenn Sie die Optimierungsflags nicht korrekt gesetzt haben, könnte dies die Leistung zerstören.

0,7 ms.

Ich stimme Mark B zu

Sie sollten auch Folgendes sicherstellen: - Führen Sie jeden Test einzeln aus - Führen Sie jeden Test mehrere Male durch, um einen Durchschnittswert zu erhalten - Verwenden Sie die gleichen Daten für alle Tests

Es gibt einige Probleme mit Ihrem Code, die dies verursachen. In der Java-Version sortieren Sie das Array, das Sie erhalten, während Sie in der C ++ - Version den Vektor sortieren UND eine Kopie davon zurückgeben (Sie machen jede Rekursion des Quicksort eine unnötige Kopie).

Vergessen Sie nicht, die C ++ - Version mit Optimierung (-O3) zu kompilieren.

Mark B traf den Nagel auf den Kopf in diesem. Ich wiederholte den Test mit dem aktualisierten Code auf meinem Rig mit den Ergebnissen

  

Java QS: 7ms

     

Java SS: 111 ms

vs

  

C ++ QS: 1 ms

     

C ++ SS: 72 ms