Studienseminar Koblenz - Fachseminar Informatik Visualisierung von Sortieralgorithmen

Martin Jakobs (2005) 1

Thema: Visualisieren von Sortieralgorithmen in Delphi (am Beispiel: Bubblesort und Quicksort) Ziel ist es, eine Animation des Bubblesort- und Quicksort-Algorithmus in Delphi für die Anwendung im Unterricht zu programmieren1. Die Vorgehensschritte der visuellen Umsetzung können mehr oder weniger einfach auf andere Visualisierungsprobleme (Sortieralgorithmen) übertragen werden. Animationen von Sortieralgorithmen gibt es im Internet inzwischen wie „Sand am Meer“, Animationen, die sich im Unterricht methodisch gut einsetzen lassen, sind jedoch rar. Manko der gängigen Animationen ist die fehlende regelbare Geschwindigkeit und das Fehlen eines „Einzelschrittmodus“, in dem der Schüler2 Vermutungen über ein zu erwartendes Verhalten des Algorithmus im nächsten Sortierschritt treffen und die Vermutungen überprüfen kann. Quicksort beinhaltet hier zudem eine farbliche Visualisierung des Bereichs, auf dem die rekursive Prozedur gerade arbeitet. Im Zentrum steht also eine Benutzeroberfläche, die dem Schüler Einzelschritte der Algorithmen und eine in der Geschwindigkeit regelbare Animation ermöglichen. Auf einen „guten Programmierstil“ wird hier Aufgrund einer gewissen Effizienz verzichtet, da diese Art der Visualisierungen für den Unterricht „quick and dirty“ programmiert ihren Zweck erfüllen und die Schüler/innen nur mit dem „Ergebnis“, der Visualisierung arbeiten sollen, das Programm also nicht selbst programmieren oder nachprogrammieren müssen.

1) Bubblesort: Das Programm wird wie folgt aussehen:

Bei der folgenden Vorgehensweise steht die Umwandlung des Sortieralgorithmus’ in eine als Einzelschritt ausführbare Prozedur im Focus.

1 Minsort kann als Programm geladen werden, wird hier aber nicht zusätzlich aufgearbeitet.

2 Schüler wird in seiner generischen Bedeutung gebraucht.

Studienseminar Koblenz - Fachseminar Informatik Visualisierung von Sortieralgorithmen

Martin Jakobs (2005) 2

Schritt 1: Der klassische Bubblesort:

for j := n-1 downto 2 do for i := 1 to j do if a[i] > a[i+1] then vertausche (i, j);

Schritt 2: Umwandlung der for-Schleifen in while-Schleifen

j := n; // wegen: while (i < j) while (j > 1) do begin i := 1; while (i < j) do begin if a[i] > a[i+1] then vertausche (i, j); inc (i); end; dec (j); end;

Schritt 3: Die „Schleifensteuerung“ wird in den Außenbereich der Prozedur Einzelschritt gelegt, i und j werden zu globalen Variablen und in der Prozedur, die das Feld mit Zufallszahlen belegt, initialisiert (kein guter Programmierstil, zugegeben, aber man sollte das Ziel nicht aus den Augen lassen)

procedure Einzelschritt; begin if (j > 1) then begin if (i < j) then begin if a[i] > a[i+1] then vertausche (i, i+1); zeichne (i, clblack); inc (i); zeichne (i, clred); end else begin i := 1; dec (j); end; end; end; procedure FeldErzeugen (Groesse : integer); var k : integer; begin j := Groesse; i := 1; end;

Studienseminar Koblenz - Fachseminar Informatik Visualisierung von Sortieralgorithmen

Martin Jakobs (2005) 3

Damit ist der Algorithmus für den Einsatz fertig. Nachfolgend steht der Quelltext der zentralen Prozeduren, hier können weitere Informationen entnommen werden. Quelltext (Auswahl):

1) Die Prozedur zeichne visualisiert einen dem Feldinhalt entsprechenden Balken im Zeichenfeld: procedure zeichne (pos : integer; farbe : TColor); begin Form1.Image1.Canvas.Pen.Width := 5; Form1.Image1.Canvas.Pen.color := farbe; Form1.Image1.Canvas.MoveTo(pos*7,0); Form1.Image1.Canvas.LineTo(pos*7, a[pos]*3); end;

2) FeldErzeugen belegt ein globales Array mit Zufallszahlen und zeichnet den “Inhalt” in die Zeichenfläche procedure FeldErzeugen (Groesse : integer); var k : integer; begin randomize; Form1.Image1.Canvas.Pen.Width := 5; Form1.Image1.Canvas.Pen.color := clwhite; Form1.Image1.Canvas.MoveTo(2,0); Form1.Image1.Canvas.LineTo(2,420); for k := 1 to Groesse do begin // +++ Feld löschen +++ Form1.Image1.Canvas.Pen.color := clwhite; Form1.Image1.Canvas.MoveTo(k*7,0); Form1.Image1.Canvas.LineTo(k*7,360); // +++ neues Feld erzeugen und zeichnen a[k] := random (120) + 1; zeichne(k , clblack); end; // Belegung der Laufvariablen j := Groesse; i := 1; end;

3) vertausche als Hilfsprozedur zum Vertauschen und neu zeichnen zweier Feldinhalte: procedure vertausche (i, j : integer); var hilf : integer; begin zeichne (i, clwhite); zeichne (j, clwhite); // i,j vertauschen hilf := a[i]; a[i] := a[j]; a[j] := hilf; // i, j schwarz zeichnen zeichne (i, clblack);

zeichne (j, clred); end;

4) Die Eingangs erwähnte Prozedur Einzelschritt: procedure Einzelschritt; begin if (j > 1) then begin if (i < j) then begin if a[i] > a[i+1] then vertausche (i, i+1); zeichne (i, clblack); inc (i); zeichne (i, clred); end else begin i := 1; dec (j); end; end; end;

5) Die Timersteuerung mit TrackBar: procedure TForm1.Timer1Timer(Sender: TObject); begin Einzelschritt; end; procedure TForm1.Button3Click(Sender: TObject); begin if (Timer1.Enabled) then begin Timer1.Enabled := false; Button1.Enabled := true; Button2.Enabled := true; end else begin Timer1.Enabled := true; Button1.Enabled := false; Button2.Enabled := false; end; end; procedure TForm1.TrackBar1Change(Sender: TObject); begin Timer1.Interval := TrackBar1.Position; end; end.

Studienseminar Koblenz - Fachseminar Informatik Visualisierung von Sortieralgorithmen

Martin Jakobs (2005) 4

2) Quicksort: Das Programm wird wie folgt aussehen:

Kern der Vorgehensweise ist es, die rekursive Funktion soweit „aufzubrechen“, dass sie als Einzelschrittprozedur ausgeführt werden kann: Schritt 1: Der klassische Quicksort

procedure sortieren (l, r : integer); var i, j : integer; trennwert , hilf : integer; begin i := l; j := r; trennwert := a[(l+r) div 2]; repeat while a[i] < trennwert do i := i + 1; while trennwert < a[j] do j := j-1; if i <= j then begin hilf := a[i];

Studienseminar Koblenz - Fachseminar Informatik Visualisierung von Sortieralgorithmen

Martin Jakobs (2005) 5

a[i] := a[j]; a[j] := hilf; i := i+1; j := j-1; end; until i>j; if l < j then sortieren (l, j); if i < r then sortieren (i, r); end;

Schritt 2: Die beim rekursiven Aufruf übergebenen Grenzen werden in einer separaten Datenstruktur IntegerQueue abgelegt und beim „rekursiven Aufruf“ wieder entnommen. (Denkbar ist hier auch ein Stack, der aber visuell Nachteile hat.)

type TIntegerQueue = class a : array of integer; index : integer; procedure enqueue (wert : integer); function dequeue : integer; function isempty : boolean; constructor create (Feldgroesse : integer); end; implementation constructor TIntegerQueue.create (Feldgroesse : integer); begin index := 0; setlength (a, Feldgroesse + 1); end; procedure TIntegerQueue.enqueue (wert : integer); begin if index < length(a) then begin inc(index); a[index] := wert; end; end; function TIntegerQueue.dequeue : integer; var i : integer; begin if not isempty then begin result := a[1]; dec(index); for i := 1 to index do a[i] := a[i+1]; end else result := -1; end;

Studienseminar Koblenz - Fachseminar Informatik Visualisierung von Sortieralgorithmen

Martin Jakobs (2005) 6

function TIntegerQueue.isempty : boolean; begin result := (index = 0); end;

Schritt 3: Mit den Grenzen des gerade sortierten Feldes als globale Variablen kann der Algorithmus in der Einzelschrittprozedur nun wie folgt umgewetzt werden:

procedure Einzelschritt; begin if (not fertig) then begin if GrenzenHolen then begin l := keller.dequeue; r := keller.dequeue; sortierbereich (l, r, cllime); GrenzenHolen := false; trennwert := a[(l+r) div 2]; zeichne (i, clblack); i := l; zeichne (i, clred); zeichne (j, clblack); j := r; zeichne (j,clblue); trennwertMarkieren(i, j); end; // +++ Schleifen +++ if (i <= j) then //repeat Schleife begin if (a[i] < trennwert) then begin zeichne(i, clblack); i := i + 1; zeichne (i, clred); trennwertMarkieren(i, j); end else if (trennwert < a[j]) then begin zeichne (j, clblack); j := j-1; zeichne (j, clblue); trennwertMarkieren(i, j); end else if i <= j then // while Schleife begin vertauschen (i, j); zeichne (i, clblack); i := i+1; zeichne (i, clred); zeichne (j, clblack); j := j-1; zeichne (j, clblue); trennwertMarkieren(i, j); end; end;

Studienseminar Koblenz - Fachseminar Informatik Visualisierung von Sortieralgorithmen

Martin Jakobs (2005) 7

Quelltext:

unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Buttons, ExtCtrls, unit2, ComCtrls; type TForm1 = class(TForm) Button1: TButton; Image1: TImage; Timer1: TTimer; Button2: TButton; Button3: TButton; TrackBar1: TTrackBar; Panel1: TPanel; Panel2: TPanel; Label1: TLabel; procedure Button1Click(Sender: TObject); procedure FormCreate(Sender: TObject); procedure Button2Click(Sender: TObject); procedure Timer1Timer(Sender: TObject); procedure Button3Click(Sender: TObject); procedure TrackBar1Change(Sender: TObject); private { Private-Deklarationen } public { Public-Deklarationen } end; const n = 100; var Form1: TForm1; a : array [1..n] of integer; keller : TIntegerQueue; // +++ globale Variablen für den Einzelschritt ++ i : integer = 1; j : integer = n; r, l , lauf : integer; trennwert , hilf : integer; fertig, GrenzenHolen : boolean; procedure FeldErzeugen (Groesse : integer); procedure vertauschen (i , j :integer); // graphisch procedure Einzelschritt; procedure zeichne (pos : integer; farbe : TColor); procedure trennwertMarkieren (i , j : integer); procedure Sortierbereich (m, n : integer; farbe : TColor); implementation {$R *.dfm} procedure zeichne (pos : integer; farbe : TColor); begin Form1.Image1.Canvas.Pen.Width := 5; Form1.Image1.Canvas.Pen.color := farbe; Form1.Image1.Canvas.MoveTo(pos*7,0); Form1.Image1.Canvas.LineTo(pos*7, a[pos]*3);

end; procedure FeldErzeugen (Groesse : integer); var i : integer; begin randomize; Form1.Image1.Canvas.Pen.Width := 5; Form1.Image1.Canvas.Pen.color := clwhite; Form1.Image1.Canvas.MoveTo(2,0); Form1.Image1.Canvas.LineTo(2,420); for i := 1 to Groesse do begin // +++ Feld löschen +++ Form1.Image1.Canvas.Pen.color := clwhite; Form1.Image1.Canvas.MoveTo(i*7,0); Form1.Image1.Canvas.LineTo(i*7,360); // +++ neues Feld erzeugen und zeichnen a[i] := random (120) + 1; zeichne(i , clblack); end; keller.enqueue(1); keller.enqueue(n); fertig := false; GrenzenHolen := true; end; procedure vertauschen (i, j : integer); var hilf : integer; begin zeichne (i, clwhite); zeichne (j, clwhite); // i,j vertauschen hilf := a[i]; a[i] := a[j]; a[j] := hilf; // i, j schwarz zeichnen zeichne (i, clred); zeichne (j, clblue); end; procedure trennwertMarkieren (i, j : integer); var k : integer; markiert : boolean; begin markiert := false; for k := j-1 downto i+1 do if (a[k] = trennwert) then begin //zeichne (k, cllime); markiert := not markiert; break; end; if ((not markiert) and (i+1 < j)) then if (trennwert = a[i]) then // zeichne (i+1, cllime) else // zeichne (j-1, cllime); end; procedure Sortierbereich (m, n : integer; farbe : TColor); begin Form1.Image1.Canvas.Pen.Width := 3;

Studienseminar Koblenz - Fachseminar Informatik Visualisierung von Sortieralgorithmen

Martin Jakobs (2005) 8

Form1.Image1.Canvas.Pen.color := farbe;

Form1.Image1.Canvas.MoveTo(m*7-4,0);

Form1.Image1.Canvas.LineTo(m*7-4, 370); Form1.Image1.Canvas.MoveTo(n*7+4,0); Form1.Image1.Canvas.LineTo(n*7+4, 370); end; procedure Einzelschritt; begin if (not fertig) then begin if GrenzenHolen then begin l := keller.dequeue; r := keller.dequeue; sortierbereich (l, r, cllime); GrenzenHolen := false; trennwert := a[(l+r) div 2]; zeichne (i, clblack); i := l; zeichne (i, clred); zeichne (j, clblack); j := r; zeichne (j,clblue); trennwertMarkieren(i, j); end; // +++ Schleifen +++ if (i <= j) then //repeat Schleife begin if (a[i] < trennwert) then begin zeichne(i, clblack); i := i + 1; zeichne (i, clred); trennwertMarkieren(i, j); end else if (trennwert < a[j]) then begin zeichne (j, clblack); j := j-1; zeichne (j, clblue); trennwertMarkieren(i, j); end else if i <= j then // while Schleife begin vertauschen (i, j); zeichne (i, clblack); i := i+1; zeichne (i, clred); zeichne (j, clblack); j := j-1; zeichne (j, clblue); trennwertMarkieren(i, j); end; end; // +++ "rekursiver Aufruf" +++ if (i > j) then begin if (i < r) then begin keller.enqueue(i);

keller.enqueue(r); end;

if l < j then begin keller.enqueue (l); keller.enqueue(j); end; GrenzenHolen := true; sortierbereich (l, r , clwhite); end; end; end; // procedure Einzelschritt // +++ ButtonClick Methode +++ procedure TForm1.Button1Click(Sender: TObject); begin unit1.Felderzeugen(n); Button2.Enabled := true; Button3.Enabled := true; end; procedure TForm1.Button2Click(Sender: TObject); begin Einzelschritt; end; // +++ Form Create +++ procedure TForm1.FormCreate(Sender: TObject); begin Image1.Canvas.Brush.Color := clwhite; Form1.Image1.Canvas.Pen.Width:= 5; keller := TIntegerQueue.Create(n); Felderzeugen (n); end; procedure TForm1.Timer1Timer(Sender: TObject); begin Einzelschritt; end; procedure TForm1.Button3Click(Sender: TObject); begin if (Timer1.Enabled) then begin Timer1.Enabled := false; Button1.Enabled := true; Button2.Enabled := true; end else begin Timer1.Enabled := true; Button1.Enabled := false; Button2.Enabled := false; end; end; procedure TForm1.TrackBar1Change(Sender: TObject); begin Timer1.Interval := TrackBar1.Position; end; end.

Studienseminar Koblenz - Fachseminar Informatik Visualisierung von Sortieralgorithmen

Martin Jakobs (2005) 9

unit Unit2;

interface type TIntegerQueue = class a : array of integer; index : integer; procedure enqueue (wert : integer); function dequeue : integer; function isempty : boolean; constructor create (Feldgroesse : integer); end; implementation constructor TIntegerQueue.create (Feldgroesse : integer); begin index := 0; setlength (a, Feldgroesse + 1); end; procedure TIntegerQueue.enqueue (wert : integer); begin

if index < length(a) then begin

inc(index); a[index] := wert; end; end; function TIntegerQueue.dequeue : integer; var i : integer; begin if not isempty then begin result := a[1]; dec(index); for i := 1 to index do a[i] := a[i+1]; end else result := -1; end; function TIntegerQueue.isempty : boolean; begin result := (index = 0); end; end.