Quicksort in C#

Zum Sortieren einer Zahlenreihe haben wir uns bereits den Bubblesort Algorithmus angeschaut. Der hat zwar seinen Zweck erfüllt, ist aber wie bereits erwähnt überhaupt nicht effizient. Eine alternative bildet hier der Quicksort Algorithmus. Dieser kann ebenfalls zum Sortieren von einem mit Elementen gefüllten Feld benutzt werden. In unserem Fall handelt es sich um die Reihe  welche mit Ganzzahligen Werten gefüllt ist. Wer will kann sich mein Videomaterial dazu angucken ansonsten werde ich den Algorithmus in einigen Schritten hier erklären.

 

1

Als erstes müssen wir beim diesem Algorithmus einen Pivot Punkt wählen. Einfachheitshalber werden wir immer das erste Element in einer Reihe als Pivot wählen. In diesem Fall ist a0 = 7 unser Pivot. Somit können wir gleich loslegen. Was machen wir?

  1.  Wir beginnen von links nach einem Element zu suchen welches größer oder gleich unserem Pivot Wert sind (x ≥ 7).
  2.  Gleichzeitig suchen wir von rechts her ein Element welches kleiner oder gleich Pivot ist (x ≤ 7).

Bei Punkt 1 ist die 13 bei a1 gleich die erste Zahl die größer als 7 ist. In Punkt 2 ist die 3 bei a7  die erste Zahl die kleiner als das Pivot Element 7 ist.

2

Haben wir die beiden Zahlen gefunden vertauschen wir sie einfach. Nun fahren wir genau wie oben fort und beginnen unsere Suche von links und rechts. Von links her finden wir die 12 bei a2 die größer ist als die 7. Von rechts ist die 4 bei a3 die erste Zahl die kleiner, gleich Pivot ist. Also vertauschen wir diese beiden ebenfalls.

3

Nun beginnt das Spiel von vorne wir suchen von links und rechts und werden bei den Elementen a3 = 12 von links und a2 = 4 von rechts fündig. Also vertauschen wir diese Elemente.

Wieder suchen wir von links und rechts und werden diesmal wieder bei den Elementen a3 und a2 fündig. Nur dieses Mal hat sich unsere Suche von links mit der Suche von rechts überkreuzt.

4

Da hier eine Überkreuzung stattgefunden hat, vertauschen wir unser Pivot mit dem Element in der Zelle a2.

5

Was ist passiert? Nun die Überkreuzung hat uns signalisiert, dass sich alle Elemente rechts der Zelle a2 größer als das Pivot ist und alle Elemente die links liegen kleiner sind als das Pivot. Also vertauschen wir die 4 und die 7. Somit können wir die 7 in der Zelle a2 als fertig markieren, denn sie befindet sich nun an der richtigen Position und wird nicht mehr verschoben werden.

Gleichzeitig ist noch etwas passiert. Unsere Zahlenreihe wurde in zwei Teile geteilt. Links ist die Reihe a0…a1 und rechts a3…a8. Das bedeutet aber nur, dass wir die oben genannten Regeln jetzt eben auf zwei Listen anwenden müssen. Wir beginnen mit der linken Seite, dabei ist unser Pivot das erste Element also a0.

6

Wir beginnen mit der Suche in der linken Liste. Ein Element dass größer, gleich 4 ist existiert nicht und das einzige Element kleiner, gleich 4 ist die 3 in a1.

7

Nun haben sich die Suchen wieder überkreuzt. Also vertauschen wir Pivot mit dem Element in a1 und markieren die 4 als fertig. Jetzt haben wir wieder zwei Teillisten wobei die linke lediglich ein Element enthält, a0 = 3. Eine Liste mit nur einem Element gilt jedoch als sortiert und kann somit ebenfalls als fertig markiert werden. Jetzt da wir nur noch die rechte Liste haben setzen wir das Pivot bei a3 und verfahren wie gehabt.

8

So machen wir weiter bis alle Elemente in der Zahlenreihe als fertig markiert sind.

9

Bei dem Code handelt es sich um die C# Implementierung des Pseudocodes auf Wikipedia.

//Bekommt eine Liste aus Inegern als Parameter
        public static List<int> QuicksortInt(List<int> array)
        {
            //Eine Liste die nur aus einem Element besteht gilt als sortiert, Abbruchkriterium.
            if (array.Count <= 1)
            {
                return array; //An array of Zero ot one elements is already sorted
            }

            //Das Pivot legen wir immer auf das erste Element in einer Liste
            int pivot = 0;
            List<int> less = new List<int>();
            List<int> greater = new List<int>();

            //Hier teilen wir ein array in ein array mit Elementen die kleiner als das Pivot sind
            //und in eine Liste mit Elementen die größer sind.
            for (int i = 1; i < array.Count; i++)
            {
                if (array[i] <= array[pivot])
                {
                    less.Add(array[i]);
                }
                else
                {
                    greater.Add(array[i]);
                }
            }

            //Hier kombinieren wir die Listen und setzen das Pivot dazwischen.
            List<int> combined = QuicksortInt(less);
            combined.Add(array[pivot]);
            combined.AddRange(QuicksortInt(greater));

            //Liefert sortierte Liste zurück.
            return combined;

        }
Advertisements
Dieser Beitrag wurde unter .NET, Algorithmen, Beispiel, Beispiel, c#, Programmierung, Sortieralgorithmus, Uncategorized abgelegt und mit , , , , , , , , verschlagwortet. Setze ein Lesezeichen auf den Permalink.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

w

Verbinde mit %s