Können Sie einen beliebigen Drehpunkt in Quicksort auswählen?

Ich sah vor kurzem Quick Sort - Computerphile Video auf Youtube über wie Quicksort funktioniert (auf Papier) und ich habe eine Frage. Stellen Sie sich vor, dass wir ein Array haben, das zum Beispiel "27,6,19,2,15,9,10" enthält. An erster Stelle wähle ich 10 als Pivot und das Array wird so: 9,2,6 |10| 27,19,15. Dann wähle ich 6 als Pivot für die linke unsortierte Array und es wird 2 |6| 9 und für die richtige wähle ich 19 als ein Pivot und die richtige unsortierte Array wird 15 |19| 27. Die Frage ist: Kann ich einen beliebigen Drehpunkt wählen, um meine Arbeit zu erleichtern (wie ich es in diesem Beispiel getan habe) oder gibt es etwas mehr?Können Sie einen beliebigen Drehpunkt in Quicksort auswählen?

Edit: Wenn ich 27 anstelle von 19 als Pivot wählte, wie das Array wäre?

Quelle

2016-08-09 lor

Werfen Sie einen Blick auf this Frage und Antwort.

Es gibt eine Diskussion, die zeigt, dass die Auswahl eines zufälligen Pivots in den meisten Szenarien wahrscheinlich die beste Wahl ist.

Quelle

2016-08-09 15:37:33

Ein zufälliger Pivot ist in der Tat eine gute Wahl. Es sollte jedoch nur in Versionen verwendet werden, die zu einem alternativen Algorithmus für kurze Subarrays wechseln. Andernfalls können die Kosten der Zufallszahlengenerierung einen erheblichen Mehraufwand darstellen. –

Ich habe die Frage gesehen. In diesem einfachen Szenario mit einem 7-Elemente-Array, ist meine Technik gut oder nicht? Ich habe die Frage mit einer letzten Frage aktualisiert. Bitte schau es dir an. – lor

@ YvesDaoust eine billige Pseudo Random wäre in Ordnung. Sie könnten wahrscheinlich einfach 'count ++% array.length' verwenden. – Bohemian

Sie können einen beliebigen Wert wählen, sodass kein Teil der Partition leer ist, d. H. Nicht kleiner als der kleinste oder größer als der größte. (Der Wert muss nicht ein Element des Arrays sein.)

Je ausgeglichener die Partition (also je näher am Median), desto besser. Auch wenn dies nie gemacht wird, könnte das arithmetische Mittel ausreichen. Eine gemeinsame Strategie ist der Median von drei (erste, zentrale und letzte Elemente).

Quelle

2016-08-09 15:38:43

Ich habe die Frage nach dem ** letzten ** Teil, den du sagst, aktualisiert. Bitte schau es dir an. – lor

@lor: Ich sehe nicht die Beziehung zwischen Ihrer Bearbeitung und meinem letzten Satz. –

Mein schlechtes. Ich tippte zuletzt statt zuerst. Ich muss angeben, dass, wenn wir einen anderen Drehpunkt wählen als die, die ich gewählt habe, wie 2 statt 6 und 27 statt 19, was wäre der Unterschied? Das Unterfeld würde wie | 2 | aussehen 6 9 und 15 19 | 27 | oder hätten wir hier etwas anderes? – lor

Im Prinzip können Sie jedes Array-Element als Drehpunkt verwenden; Der Algorithmus wird funktionieren. Wenn Sie in der Praxis das kleinste oder größte Element des Arrays als Pivot auswählen, erreicht ein Durchlauf des Quicksort-Algorithmus sehr wenig. Angenommen, Sie haben die Zahlen von 1 bis 100 in zufälliger Reihenfolge und wählen 1 als Pivot, dann haben Sie immer noch ein Array mit 99 Elementen zum Sortieren. Der schlimmstmögliche Fall ist das Auswählen des ersten Arrayelements als Pivot, wenn das Array bereits sortiert ist.

Quelle

2016-08-09 16:14:51 gnasher729

Können Sie einen beliebigen Drehpunkt in Quicksort auswählen?

Antwort

Verwandte Themen