quicksort

Fragen
Quicksort ist ein von C. A. R. Hoare erfundener Sortieralgorithmus, der eine durchschnittliche Komplexität von O (n log n) und die quadratische Komplexität im ungünstigsten Fall aufweist. Es ist einer der schnellsten Allzweck-Sortieralgorithmen.
8
Antworten

C ++: Schnellste Möglichkeit zum Sortieren einer Liste von Zahlen und deren Index

Ich habe eine Frage, die sehr einfach erscheinen mag, aber in einem Kontext, in dem "jeder CPU-Tick zählt" (das ist ein Teil eines größeren Algorithmus, der auf Supercomputern verwendet wird). Das Problem ist ziemlich einfach: Wie sortiere ic...
23.04.2012, 20:38
8
Antworten

Schnellsortierung vs Auswahlsortierung (Java vs C ++)

Ich habe zwei Projekte erstellt. Eins in C ++ und eins in Java. Ich habe Zeittests für einen QuickSort und SelectionSort für beide durchgeführt. Seltsamerweise fand ich ein sehr seltsames Verhalten. Hier waren die Ergebnisse für ein Array der...
05.05.2011, 17:31
1
Antwort

C OpenMP parallel quickSort

Noch einmal bin ich fest, wenn ich openMP in C ++ benutze. Diesmal versuche ich einen parallelen Quicksort zu implementieren. Code: %Vor% Algorithmus: Um openMP für eine rekursive Funktion zu verwenden, verwendete ich einen Stapel,...
05.11.2011, 20:40
3
Antworten

Warum ist Quicksort im Durchschnitt schneller als andere?

Wie wir wissen, ist die Quicksort-Performance im Durchschnitt O (n * log (n)), aber die Merge- und Heapsort-Leistung ist auch O (n * log (n)) im Durchschnitt. Die Frage ist also, warum Quicksort im Durchschnitt schneller ist.     
26.11.2010, 22:46
3
Antworten

Quicksort Stapelgröße

Warum sortieren wir lieber die kleinere Partition einer Datei und schieben nach der Partitionierung den größeren auf den Stack für Quicksort (nicht-rekursive Implementierung)? Dadurch verringert sich die Platzkomplexität von Quicksort O (log n)...
15.07.2011, 15:02
3
Antworten

Optimaler Median der Medianauswahl - 3 Elementblöcke vs. 5 Elementblöcke?

Ich arbeite an einer Quicksort-Variante, die auf dem Select-Algorithmus basiert, um ein Gut auszuwählen Drehelement. Herkömmliche Weisheit scheint zu sein, das Array in 5-Element-Blöcke zu teilen, den Median von jedem zu nehmen und dann rekurs...
11.10.2010, 16:25
3
Antworten

Manuelle Implementierung von Hochleistungsalgorithmen in .NET

Als Lernerfahrung habe ich kürzlich versucht, Quicksort mit 3-Wege-Partitionierung in C # zu implementieren. Abgesehen von der Notwendigkeit, vor dem rekursiven Aufruf eine zusätzliche Bereichsüberprüfung der Variablen links / rechts hinzuz...
13.11.2009, 05:18
2
Antworten

randomisierte Quicksort: Wahrscheinlichkeit von zwei Elementen Vergleich?

Ich lese " Probability and Computing " von M.Mitzenmacher und E.Upfal. Ich habe Probleme zu verstehen, wie die Wahrscheinlichkeit des Vergleichs zweier Elemente berechnet wird. Eingabe: sortierte Liste (y1, y2, ..., yN) von Zahlen. Wir such...
01.05.2010, 16:42
3
Antworten

sortiert die Iteratoranforderungen schnell

tl; dr: Ist es möglich, Quicksort auf einer doppelt verknüpften Liste effizient zu implementieren? Mein Verständnis, bevor ich darüber nachdachte, war, nein, es ist nicht. Neulich hatte ich Gelegenheit, die Iteratoranforderungen für die gru...
28.09.2011, 16:46
1
Antwort

Vorteile von Quichesort

Ich habe dieses Programm für eine Aufgabe erstellt, in der wir eine Implementierung von Quichesort erstellen mussten. Dies ist ein hybrider Sortieralgorithmus, der Quicksort verwendet, bis er eine bestimmte Rekursionstiefe erreicht (log2 (N),...
21.12.2014, 18:34