Quicksort ist einer der weitverbreitesten Sortieralgorithmen. Vorteile sind das gute Laufzeitverhalten und die effiziente Speichernutzung. Mit steigender Elementzahl steigt der Berechnnugsaufwand nur in der Ordnung O(n*logn). Der größte Nachteil des Algorithmus ist die schwierige Implementierung, da diese exakt durchgeführt werden muss. Kleine Fehler im Programmcode können unsinnige Ergebnisse produzieren. Das Gesamtfeld wird durch Rekursion in verschiedene Teilfelder unterteilt.

Ablauf:

Wie in der theoretischen Einführung dargestellt, arbeitet der Algorithmus mit einer Zerlegung des Problems in zwei Teile. Anschließend wird der Sortieralgorithmus für die beiden Teilfelder ausgeführt. Der Ablauf der rekursiven Funktion ist im PAP dargestellt. Hier der Algorithmus nochmal in

Pseudocode:

PROCEDURE Quicksort(L,R) % L ist normalerweise 0, R = n-1
Hole zu sortierendes Feld
Falls L < R dann
BEGIN
zw1 := Feld[R]; % Speichere den Wert in Feld an Stelle R zwischen als "Pivotelement"
ii := L; % setze ii = 0
jj := R-1; % setze jj = links vom Pivotelement
REPEAT % Wiederhole 
Do While zw1 >= Feld(ii) AND ii < R %inkrementiere ii solange Feld(ii) <= Pivotelement und ii < R
ii = ii+1; 
Do While zw1 <= Feld(jj) AND jj > L %dekrementiere jj bis Feld(jj) >= Pivotelement und jj > L
jj = jj-1; 
Wenn ii < jj
zw2 := Feld(ii);
Feld(ii) := Feld(jj)
Feld(jj) := zw2
UNTIL ii >= jj %solange ii kleiner als jj tausche aktuelles Element in Feld(ii) mit Pivotelement
falls Feld(ii) > Pivotelement, tausche
zw2 := Feld(ii)
Feld(ii) := Feld(R) % An Stelle ii ist jetzt das Pivotelement
Feld(R) := zw2 
Quicksort(L,ii) %rufe Dich mit der linken Teilliste rekursiv auf
Quicksort(ii+1,R) % rufe Dich mit der rechten Teilliste rekursiv auf
END
END


In dieser Implementierung wird der Wert an der rechten Schranke zum Vergleich genutzt. Die Zeiger laufen aufeinander zu und immer, wenn in einem Teilfeld rechts ein kleinerer und links ein größerer Wert auftritt werden diese getauscht.

Ist der letzte Wert in Feld(ii) größer als das Pivotelement, werden diese getauscht. Nun teilt Feld(ii) die Liste und es können zwei Unterlisten mit dem Quicksort durchgearbeitet werden.

Wichtig:
MatLab beherrscht leider keine repeat-until Schleifen. Genauso gut können natürlich While- und Forschleifen verwendet werden.

 

Erstellen Sie ausgehend von den Beschreibungen und dem bestehenden PAP die MatLab-Funktion für den Quicksort. Um sinnvoll auf die Elemente zugreifen zu können, verwenden Sie die globale Definition von Variablen.

 

Lösungsvorschlag:

Quicksort

function quicksort(l,r)
global V swaps

if r > 1
p = V(r);
ii = l;
jj = r;


while ii < jj

 while (V(ii) <= p) && (ii<r-1)
  ii = ii + 1;
 end

 while (V(jj) >= p) && (jj>l)
  jj = jj-1;
 end

 if ii< jj
  t = V(ii)
  V(ii) = V(jj)
  V(jj) = t;
  swaps = swaps +1;
 end

 if V(ii) > p
  t = V(ii)
  V(ii) = p
  V(r) = t
  swaps = swaps +1;
 end
 quicksort(l,ii);
 quicksort(ii+1,r);
 end
end
end >> V = fix(100*rand(1,20));
>> quicksort(1,20);
>> disp(V)