Quick sort mit mittlere element als pivot

Mein Verständnis der schnellen Sorte ist

  1. Wähle ein pivot-element (in diesem Fall wähle ich mittlere element als
    pivot)
  2. Initialisieren linken und rechten Zeiger auf Extreme.
  3. Hier finden Sie das erste element auf der linken Seite des Drehpunktes, die größer ist als das pivot.
  4. Ebenso finden Sie das erste element auf der rechten Seite des pivot, der kleiner als der pivot -
  5. Swap-Elemente in 3 und 4.
  6. Wiederholen 3,4,5, es sei denn, Links >= rechts.
  7. Wiederholen Sie das ganze für linken und rechten subarray als pivot ist jetzt an seinem Platz.

Ich bin sicher, ich bin hier etwas fehlt, und das sehr dumm. Aber oben scheint nicht zu funktionieren fot dieses array:

  8,7,1,2,6,9,10,2,11 pivot: 6  left pointer at 8, right pointer at 11
  2,7,1,2,6,9,10,8,11 swapped 2,8  left pointer at 7, right pointer at 10

Was nun ? Es gibt kein element, die kleiner als 6 auf der rechten Seite.
Wie 7 wird zu gehen, um das Recht der 6 ?

InformationsquelleAutor Walt | 2015-01-11

  1. 4

    Es ist keine vorab-Aufteilung zwischen der linken und der rechten Seite. Insbesondere 6 ist, nicht die Teilung. Stattdessen ist die division durch verschieben der linken und rechten Zeiger näher an einander, bis Sie sich treffen. Das Ergebnis könnte sein, dass die eine Seite wesentlich kleiner als die anderen.

    Ihre Beschreibung des Algorithmus ist in Ordnung. Nirgends es sagen Sie haben zu stoppen in der Mitte element. Einfach weiter, die führen das als gegeben an.

    BTW.: Das pivot-element kann verschoben werden, während die Sortierung. Nur weiter zu vergleichen, gegen 6 auch wenn es verschoben wurde.

    Update:

    Tatsächlich gibt es ein paar kleine problem in der Beschreibung des Algorithmus. Einer ist, dass Sie entweder Schritt 3 oder Schritt 4, müssen Elemente, die gleich auf die pivot. Wir umschreiben es wie folgt:

    Mein Verständnis der schnellen Sorte ist

    1. Wähle einen pivot Wert (in diesem Fall, wählen Sie den Wert des mittleren Elements)
    2. Initialisieren linken und rechten Zeiger auf Extreme.
    3. Beginnend an der linken Zeiger und die sich nach rechts, finden Sie das erste element, die größer als oder gleich dem pivot-Wert.
    4. Ähnlich, beginnend mit dem rechten Mauszeiger und verschieben nach Links, hier finden Sie das erste element, das
      kleiner als pivot-Wert
    5. Swap-Elemente in 3 und 4.
    6. Wiederholen 3,4,5, bis die linken Mauszeiger ist größer oder gleich dem Zeiger.
    7. Wiederholen Sie das ganze für die beiden subarray Links und rechts von der linken Zeiger.
    pivot value: 6, left pointer at 8, right pointer at 11
8,7,1,2,6,9,10,2,11 left pointer stays at 8, right pointer moves to 2
2,7,1,2,6,9,10,8,11 swapped 2 and 8, left pointer moves to 7, right pointer moves to 2
2,2,1,7,6,9,10,8,11 swapped 2 and 7, left pointer moves to 7, right pointer moves to 1
pointers have now met /crossed, subdivide between 1 and 7 and continue with two subarrays
    Danke für die Antwort @Codo. Also in diesem besonderen Fall was meine rekursive Aufrufe Aussehen wird ? Was ich versuche zu verstehen, ist die Gültigkeit der Aussage, dass ich glaube, ich stieß überall - "Alle Elemente Links des pivot-sind kleiner und rechts neben dem Drehpunkt größer sein wird durch die Ende der iteration" ... ich verstehe, dass pivot bewegen kann .. aber ich sehe nicht, wie es bewegt sich in oben genannten Fall.
    warten zu hören, wieder von Ihnen. 🙂
    scheint mein update
    Meine einzige Sorge (die nicht wirklich gültig, glaube ich) ist, haben wir angefangen, mit 6 als Drehpunkt aber endlich array habe neu geordnet, so daß alle Elemente, die kleiner als 7 sind vor 7 und größer als 7 sind nach 7. Idealerweise sollten wir dies erreicht haben, für 6.
    Nach Ihren 4. Punkt, wie haben Sie Weg Vergangenheit durch 6 in Ihrer trocken-ausführen von code bei left pointer moves to 7, right pointer moves to 2? Nach der 4. Regel, es sollte aufhören, an 6 als 6 > 6 ist falsch. Wie bist du gegangen, vorbei an der 6 und ausgewählten 2? Oder bin ich etwas fehlt?

    InformationsquelleAutor Codo

  2. 0
    Quick Sort Given an array of n elements (e.g., integers):
-If array only contains one element, return
-Else
  pick one element to use as pivot.
  Partition elements into two sub-arrays:
    Elements less than or equal to pivot
    Elements greater than pivot
  Quicksort two sub-arrays
  Return results

Let i and j are the left and right pivots, then code for one array will look like this:

1) While data[i] <= data[pivot]
    ++i
2) While data[j] > data[pivot]
    --j
3) If i < j
    swap data[i] and data[j]
4) While j > i, go to 1.
5) Swap data[j] and data[pivot_index]

Position of index j is where array is to-be partitioned in two half and then same steps are applied to them recursively.

    Endlich Sie bekommt ein sortiertes array.

    InformationsquelleAutor Kush

Schreibe einen Kommentar