Quicksort: Die Wahl der Dreh

StackOverflow https://stackoverflow.com/questions/164163

Frage

Wenn Quicksort Umsetzung eines der Dinge, die Sie tun müssen, ist eine Pivot zu wählen. Aber wenn ich an Pseudo-Code so aussehen wie unten, ist es nicht klar, wie ich die Pivot wählen soll. Das erste Element der Liste? Etwas anderes? 

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Kann mir jemand helfen, das Konzept begreift einen Dreh Wahl und ob verschiedene Szenarien für unterschiedliche Strategien nennen.

War es hilfreich?

Lösung

ein zufälligen Pivot-Wahl die Möglichkeit minimiert, dass Sie Worst-Case-O begegnen (n 2 ) Leistung (immer die Wahl erste oder letzte würde dazu führen, Worst-Case-Leistung für fast sortierten oder nahezu umgekehrt -sortierte Daten). das mittlere Element der Wahl auch in der Mehrzahl der Fälle akzeptabel wäre.

Auch wenn Sie diese selbst implementieren, gibt es Versionen des Algorithmus, der an Ort und Stelle arbeiten (das heißt ohne zwei neue Listen zu erstellen und verketten sie dann).

Andere Tipps

Es hängt von Ihren Anforderungen. eine Pivot zufällig Wahl macht es schwieriger, einen Datensatz zu erzeugen, die O (N ^ 2) Leistung erzeugt. 'Median-of-three' (erster, letzter, Mitte) ist auch ein Weg, um Probleme zu vermeiden. Hüten Sie sich vor der relativen Performance von Vergleichen, obwohl; wenn Ihre Vergleiche teuer sind, dann tut Mo3 mehr Vergleiche als Auswahl (einen einzelnen Wert Pivot) nach dem Zufallsprinzip. Datenbankeinträge können teuer zu vergleichen.

Update:. Ziehen Kommentare in Antwort

mdkess behauptet:

  

‚Median von 3‘ ist nicht erst letzte Mitte. Wählen Sie drei zufällige Indizes und nehmen Sie den mittleren Wert dieser. Der springende Punkt ist, um sicherzustellen, dass Ihre Wahl schwenkt nicht deterministisch ist -. Wenn es ist, kann schlimmsten Fall Daten ganz leicht erzeugt werden

Worauf ich antwortete:

  • Analyse von Hoares Suche-Algorithmus mit Median-Of -drei Partition (1997) durch P Kirschenhofer, H Prodinger unterstützt C Martínez Ihren Anstoß (die Median-of-drei "sind drei Zufall Artikel).

  • Es ist ein Artikel beschrieben unter Portal .acm.org also etwa 'The Worst Case Permutation für Median-of-Three Quicksort' von Hannu Erkiö, in The Computer Journal, Band 27 veröffentlicht, Nr 3, 1984. [Update 2012-02-26: Haben Sie den Text für den Artikel . Abschnitt 2 ‚Der Algorithmus‘ beginnt: ‚ den Median der ersten, mittleren und letzten Elemente von A [L: R] Durch die Verwendung., Effiziente Partitionen in Teile ziemlich gleicher Größe kann in den meisten praktischen Situationen erreicht werden ‘So ist es der Erörterung der ersten Mittel letzten Mo3 Ansatz.]

  • Ein weiterer kurzer Artikel, der interessant ist, ist von MD McIlroy, "Ein Mörder Widersacher für Quicksort ", veröffentlicht in Software-Praxis und Erfahrung, Vol. 29 (0), 1-4 (0 1999). Es wird erläutert, wie fast jede Quicksort machen verhält quadratisch.

  • AT & T Bell Labs Tech Journal, Oktober 1984 „Theorie und Praxis in der Konstruktion eines Sortierroutine Arbeiten“, sagt „Hoare vorgeschlagene Partitionierung um den Median von mehreren zufällig ausgewählten Linien. Sedgewick [...] empfahl die Wahl Median der ersten [...] letzte [...] und Mitte“. Dies zeigt, dass beide Techniken für ‚Median-of-drei‘ sind in der Literatur bekannt. (Update 2014.11.23: Der Artikel erscheint unter zur Verfügung stehen IEEE Xplore oder von Wiley -., wenn Sie die Mitgliedschaft oder bereit sind, müssen eine Gebühr zu zahlen)

  • 'Technik eine Sortierfunktion' von JL Bentley und MD McIlroy, veröffentlicht in Software Praxis und Erfahrung, Band 23 (11), November 1993 geht in eine ausführliche Diskussion über die Fragen, und sie wählten einen adaptiven Partitionierungsalgorithmus teilweise auf der Größe der Daten basieren einstellen. Es gibt viele Diskussionen von Kompromissen für verschiedene Ansätze.

  • Eine Google-Suche nach 'Median-of-three' funktioniert recht gut für die weitere Verfolgung.

Danke für die Informationen; Ich hatte begegnet nur die deterministischen 'Median-of-three' vor.

Heh, lehrte ich nur diese Klasse.

Es gibt mehrere Optionen.
Ganz einfach: Wählen Sie das erste oder das letzte Element des Bereichs. (Schlecht in teilweise sortiert Eingang) Besser: Wählen Sie das Element in der Mitte des Bereichs. (Besser auf teilweise sortierten Eingang)

Allerdings läuft jedes beliebiges Element Kommissionierung die Gefahr von schlecht Partitionieren des Array der Größe n in zwei Reihen von der Größe 1 und n-1. Wenn man das oft genug tun, läuft IhrDeterm quicksort das Risiko der Werdens O (n ^ 2).

Eine Verbesserung, die ich gesehen habe, ist Median Pick (erste, letzte, Mitte); Im schlimmsten Fall kann es gehen noch auf O (n ^ 2), aber probabilistically, ist dies ein seltener Fall.

Für die meisten Daten, Kommissionierung der ersten oder letzten ausreichend ist. Aber, wenn Sie feststellen, dass Sie in der schlimmsten Fall laufen oft (teilweise sortierte Eingang), die erste Möglichkeit wäre, den zentralen Wert wählen (die eine statistisch gute Dreh für teilweise sortierten Daten ist).

Wenn Sie immer noch Probleme laufen, dann die mittlere Strecke gehen.

Sie niemals einen festen Dreh wählen - diese angegriffen werden können Ihren Algorithmus schlimmsten Fall O (n ^ 2) Laufzeit, der Ärger bringen wird nur zu nutzen. Quicksort schlimmste Fall tritt auf, wenn die Laufzeit Ergebnisse Partitionierung in einer Reihe von 1-Elemente, und einer Anordnung von n-1 Elemente. Angenommen, Sie das erste Element als Partition auswählen. Wenn jemand ein Array an Ihren Algorithmus-Feeds, die in absteigender Reihenfolge ist, wird Ihre erste Dreh die größte sein, so alles in der Reihe wird auf der linken Seite verschieben. Dann, wenn Sie Rekursion, wird das erste Element die größte wieder sein, so einmal mehr Sie alles links von mir ausdrückte, und so weiter.

Eine bessere Technik ist das Median-of-3-Verfahren, in dem Sie drei Elemente zufällig wählen, und in die Mitte wählen. Sie wissen, dass das Element, das Sie nicht das der erste oder der letzte, sondern auch durch den zentralen Grenzwertsatz wählen sein, die Verteilung des mittleren Element wird normal sein, was bedeutet, dass Sie in Richtung der Mitte neigen wird (und damit , n lg n Zeit).

Wenn Sie unbedingt wollen O (NLGN) Laufzeit für den Algorithmus zu gewährleisten, die Spalten-of-5-Methode des Median eines Arrays für die Suche läuft in O (n) Zeit, was bedeutet, dass die Rekursionsgleichung für quicksort in der schlimmster Fall wird T (n) = O (n) (den Median finden) + O (n) (Partition) + 2T (n / 2) (Rekursion links und rechts.) Nach dem Master-Theorem, das ist O (n lg n). Allerdings wird der konstante Faktor sehr groß sein, und wenn schlimmste Fall Leistung das primäre Anliegen ist, verwenden Sie eine Mergesort statt, die nur ein wenig langsamer als Quicksort im Durchschnitt ist und garantiert O (NLGN) Zeit (und wird viel schneller als diese lahm Median quicksort).

Erläuterung des Median des Mediane Algorithmus

Versuchen Sie nicht, und zu klug zu bekommen und Schwenk Strategien kombinieren. Wenn Sie Median von 3 mit zufälliger Dreh kombiniert durch den Median des ersten, letzten und ein zufälligen Index in der Mitte sammeln, dann werden Sie noch viele der Verteilungen anfällig sein, die mittleren von drei quadratischen senden (so seine wirklich schlechter als Ebene zufällige Pivot)

ZB ein Rohr Organverteilung (1,2,3 ... N / 2..3,2,1) erste und die letzte sein wird sowohl 1 als auch die Zufallsindex wird eine Zahl größer als 1 ist, wobei der Median gibt 1 ( entweder die erste oder letzte) und Sie erhalten eine extermely unausgeglichen Partitionierung erhalten.

Es ist völlig davon abhängig, wie Ihre Daten sortiert werden zu beginnen. Wenn Sie denken, es pseudo-zufällig sein wird dann Ihre beste Wette ist, um entweder eine zufällige Auswahl zu wählen oder die Mitte wählen.

Wenn Sie eine zufällige zugängliche Sammlung Sortierung (wie ein Array), ist es allgemein üblich, am besten das physische mittlere Element auszuwählen. Damit, wenn das Array ist alles fertig sortiert (oder fast sortierten), die beiden Partitionen werden in der Nähe auch zu, und du wirst die beste Geschwindigkeit bekommen.

Wenn Sie etwas mit nur linearem Zugriff sind Sortierung (wie eine verknüpfte Liste), dann ist es am besten auf das erste Element zu wählen, weil es der schnellste Punkt für den Zugriff ist. Hier aber, wenn die Liste bereits sortiert ist, sind Sie verschraubt -. Eine Partition immer null sein wird, und die anderen haben alles, was die schlimmste Zeit der Herstellung

Doch für eine verknüpfte Liste, nichts außer dem ersten Kommissionierung, wird nur noch schlimmer machen. Es nehmen Sie den mittleren Punkt in einer aufgelistet Liste, würden Sie durch sie auf jeder Partition Schritt für Schritt müssen - das Hinzufügen eines O (N / 2) Operation, die log N mal die insgesamt O (1,5 N · log N) durchgeführt wird und das ist, wenn wir wissen, wie lange die Liste ist, bevor wir beginnen - in der Regel haben wir nicht so würden wir müssen den ganzen Weg Schritt für Schritt durch, sie zu zählen, dann wird der Schritt auf halbem Weg durch die Mitte zu finden, dann wird der Schritt durch eine O (2,5 N · log N)

: zum dritten Mal die tatsächliche Partition zu tun

Es ist einfacher, den quicksort in drei Abschnitte zu brechen dies zu tun

  1. Exchange oder Swap-Datenelement Funktion
  2. Die Partitionsfunktion
  3. Die Verarbeitung der Partitionen

Es ist nur etwas mehr als eine ineffizientes lange Funktion, ist aber viel einfacher zu verstehen.

-Code folgt: 

/* This selects what the data type in the array to be sorted is */

#define DATATYPE long

/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */

void swap (DATATYPE *x, DATATYPE *y){  
  DATATYPE Temp;

  Temp = *x;        // Hold current x value
  *x = *y;          // Transfer y to x
  *y = Temp;        // Set y to the held old x value
};


/* This is the partition code */

int partition (DATATYPE list[], int l, int h){

  int i;
  int p;          // pivot element index
  int firsthigh;  // divider position for pivot element

  // Random pivot example shown for median   p = (l+h)/2 would be used
  p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point

  swap(&list[p], &list[h]);                   // Swap the values
  firsthigh = l;                                  // Hold first high value
  for (i = l; i < h; i++)
    if(list[i] < list[h]) {                 // Value at i is less than h
      swap(&list[i], &list[firsthigh]);   // So swap the value
      firsthigh++;                        // Incement first high
    }
  swap(&list[h], &list[firsthigh]);           // Swap h and first high values
  return(firsthigh);                          // Return first high
};



/* Finally the body sort */

void quicksort(DATATYPE list[], int l, int h){

  int p;                                      // index of partition 
  if ((h - l) > 0) {
    p = partition(list, l, h);              // Partition list 
    quicksort(list, l, p - 1);        // Sort lower partion
    quicksort(list, p + 1, h);              // Sort upper partition
  };
};

Im Idealfall sollte der Dreh der mittlere Wert im gesamten Array sein. Dies reduziert die Chancen von Worst-Case-Leistung zu bekommen.

Kurze Art der Komplexität variiert stark mit der Auswahl des Drehwertes. zum Beispiel, wenn Sie immer Komplexität erstes Element, das als Drehpunkt, Algorithmus wird als worst als O (n ^ 2) wählen. hier ist eine intelligente Methode Dreh Element- wählen 1. Wählen Sie das erste, mittleren letzte Element des Arrays. 2. Vergleichen Sie diese drei Zahlen und die Zahl finden, die größer als eins ist und kleiner als andere heißt Median. 3. macht dieses Element als Pivotelement.

Auswahl der Dreh durch dieses Verfahren spaltet in fast zwei Hälfte der Anordnung und damit die Komplexität reduziert sich auf O (nlog (n)).

Im Durchschnitt Median von 3 ist für kleine n gut. Median von 5 ist ein wenig besser für größere n. Die ninther, die der „Median von drei Mediane von drei“ ist noch besser für sehr große n.

Je höher gehen Sie mit der besseren Abtasten Sie erhalten, wenn n zunimmt, aber die Verbesserung dramatisch verlangsamt, wie Sie die Proben erhöhen. Und Sie entstehen den Aufwand für die Probenahme und Sortier Proben.

Ich empfehle den mittleren Index verwendet, da es leicht berechnet werden kann.

Sie können es berechnen durch Runden (Array.length / 2).

In einer wirklich optimierte Implementierung, wobei das Verfahren Pivot für die Wahl sollte auf der Array-Größe abhängen - für ein großes Array, lohnt es sich, mehr Zeit zu verbringen, ein gutes Dreh wählen. Ohne eine vollständige Analyse zu tun, würde ich „Mitte O (log (n)) Elemente“ erraten ist ein guter Anfang, und dies hat den zusätzlichen Bonus von nicht erfordert keine zusätzlichen Speicher: Die Verwendung Tail-Call auf die größere Partition und IN- Ort Partitionierungs, wir die gleiche O (log (n)) zusätzlichen Speicher an fast jeder Stufe des Algorithmus verwendet werden.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top