Visualisierung des Mergesort-Algorithmus

1. Aufgabe

Der Mergesort-Algorithmus gehört zu den bekanntesten Sortieralgorithmen. Die Idee des Algorithmus besteht darin, die zu sortierende Folge in irgendeiner Weise zunächst in kleinere Teile zu zerlegen, um das Endergebnis (die sortierte Folge) dadurch zu berechnen, dass man die Teile wieder zusammenfügt (daher der Name „Mergesort“). Die zu sortierende Folge wird einfach in der Mitte geteilt, so dass zwei etwa gleich große Teilfolgen entstehen. Beide Teilfolgen werden getrennt sortiert – natürlich wiederum mit dem Mergesort-Algorithmus. Danach wird die Ergebnisfolge durch „Zusammenmischen“ aus den beiden Teilfolgen gebildet.

In Abbildung 1 finden Sie ein Beispiel vor, das die Arbeitsweise des Mergesort-Algorithmus demonstriert:

Ein Beispiel zur Arbeitsweise des Mergesort-Algorithmus.

Abbildung 1. Ein Beispiel zur Arbeitsweise des Mergesort-Algorithmus.


Die anfängliche Zahlenfolge aus Abbildung 1, bestehend aus 7 Elementen, ist zu groß, um ohne mentalen Einsatz sortiert zu werden. Aus diesem Grund wird sie einfach in der Mitte geteilt, es entstehen zwei kleinere Zahlenfolgen mit 4 bzw. 3 Elementen. Wir stellen uns auf den Standpunkt, dass auch diese Folgen für eine direkte Sortierung zu groß sind. Es tritt also wiederum der Aspekt des Teilens in Kraft, es werden insgesamt drei Folgen der Länge 2 und eine einelementige Folge durch Zerlegung gebildet. Die einelementige Folge ist nun ohne jeglichen Arbeitsaufwand sortierbar (sie ist bereits sortiert), die anderen zweielementigen Folgen werden noch einmal unterteilt.

Nach den wiederholten Aufteilungsphasen kommt es zum Verschmelzen der gebildeten Teilfolgen. Dieser Verschmelzungsschritt (Merge-Schritt) ähnelt dem Reißverschlussverfahren, mit dem sich Autos von zwei auf eine Spur einordnen. Es entscheidet (im Gegensatz zum Autofahren) die Größe des jeweiligen Elements am Anfang der Teilfolge, wer als nächstes einfädeln darf.

1.1. Standardimplementierung des Mergesort-Algorithmus (Modell)

Für eine Implementierung des Mergesort-Algorithmus kommt man mit nur zwei Methoden aus: Einer Methode Sort, die im Wesentlichen nur eine Folge in zwei Teilfolgen aufteilt und die Arbeit rekursiv an die zwei Teilfolgen weiterreicht. Eine zweite Methode Merge ist dafür zuständig, zwei sortierte Teilfolgen zu einer sortierten Gesamtfolge zusammenzusetzen. In Abbildung 2 finden Sie zunächst eine Beschreibung der Sort-Methode in Pseudocode-Darstellung vor:

Pseudocode der Methode Sort.

Abbildung 2. Pseudocode der Methode Sort.


Die Pseudocode-Darstellung der Sort-Methode in Abbildung 2 dürfte selbsterklärend sein. Der zweite Schritt sieht komplizierter aus, als er eigentlich ist: Das Vereinen zweier sortierter Teilfolgen ähnelt dem schon zitierten Reißverschlussverfahren. Es entscheidet der Wert der zwei Elemente am Anfang der zwei Teilfolgen, welches Element als nächstes in die (zu Beginn leere) Resultatfolge aufgenommen wird. Da die zwei Teilfolgen sortiert vorliegen, ist die auf diese Weise entstehende Resultatfolge dann ebenfalls sortiert (Abbildung 3):

Pseudocode der Methode Merge.

Abbildung 3. Pseudocode der Methode Merge.


Die Arbeitsweise der Merge-Methode finden Sie noch einmal grafisch veranschaulicht in Abbildung 4 vor:

Arbeitsweise der Merge-Methode.

Abbildung 4. Arbeitsweise der Merge-Methode.


Implementieren Sie eine Klasse MergeSorterModel auf Basis der Hinweise aus Tabelle 1:

Methode

Schnittstelle und Beschreibung

Eigenschaft Numbers

List<int> Numbers { get; set; };

Dient zum Schreiben oder Lesen einer Liste von Zahlen, die auf Basis des Mergesort-Algorithmus zu sortieren sind.

Methode Start

public void Start();

Startet den Mergesort-Algorithmus.

Methode Reverse

public void Reverse();

Erzeugt im Zahlenfeld der Eigenschaft Numbers eine absteigend sortierte Liste ganzer Zahlen. Derartige Zahlenlisten eignen sich gut zum Testen des Modells bzw. einer ganzen Anwendung.

Methode Random

public void Random();

Erzeugt im Zahlenfeld der Eigenschaft Numbers eine Liste zufällig erzeugter ganzer Zahlen.

Methode Sort

public void Sort();

Sortiert die Elemente der Liste Numbers auf Basis des Mergesort-Algorithmus. Das Resultat wird wiederum in der Eigenschaft Numbers abgelegt.

Tabelle 1. Öffentliche Eigenschaft und Methoden der Klasse MergeSortModel.


Bemerkung: Sie können alternativ zur generischen Klasse List<int> auch einfach int-Arrays verwenden.

Die zentrale Einstiegsmethode Sort aus Tabelle 1 benötigt zwei Hilfsmethoden Sort (Überladung) und Merge, so wie sie in Abbildung 2 und Abbildung 3 algorithmisch beschrieben wurden. Diese beiden privaten Hilfsmethoden finden Sie in Tabelle 2 vor.

Methode

Schnittstelle und Beschreibung

Hilfsmethode Merge

private List<int> Merge (int offset, List<int> L1, List<int> L2);

Fügt zwei sortierte Teilfolgen zu einer neuen sortierten Teilfolge zusammen. Die zwei Teilfolgen L1 und L2 werden nicht geändert, das Ergebnis des Zusammenfügens wird als Rückgabewert von Merge zurückgegeben.

Hilfsmethode Sort

private List<int> Sort (int offset, List<int> L);

Sortiert die Elemente der Liste L auf Basis des Mergesort-Algorithmus. Das Resultat wird als Rückgabewert von Sort zurückgegeben.

Tabelle 2. Private Hilfsmethoden Sort und Merge der Klasse MergeSortModel.


Es folgt ein wichtiger Hinweis, den Sie in Ihrer Implementierung bitte beachten. Bei beiden Methoden in Tabelle 2 finden Sie einen Parameter mit dem Namen offset vor. Welchem Zweck dient er? Um neben dem reinen Sortieren einer Folge von Zahlen auch eine Visualisierung zu betrachten, ist an der Beschreibung des Algorithmus in den einleitenden Abschnitten eine Ergänzung vorzunehmen. Die vielen Teilfolgen, die rekursiv sortiert werden, sind in der vorgestellten Variante des Algorithmus alles Listen (Arrays), deren erstes Element immer (trivialerweise) den Index 0 besitzt! Dies erleichtert zunächst das Sortieren und führt auch zum korrekten Ergebnis, wenn man nur an der Berechnung einer sortierten Liste interessiert ist. Bei einer Visualisierung verliert man bei den einzelnen Teilsortierungen aber den Bezug zur tatsächlichen Position eines einzelnen Elements innerhalb der Ursprungsliste. Zu diesem Zweck müssen deshalb die zwei Methoden Sort und Merge aus Tabelle 2 um einen zusätzlichen Parameter (hier: offset vom Typ int) ergänzt werden, der angibt, auf welche tatsächliche Position in der Ursprungsliste sich die jeweils vorliegende Teilliste tatsächlich bezieht (Offset zum Anfang der Ursprungsliste). Mit Hilfe dieses Offsets kann man dann einer Visualisierungskomponente einen korrekten Auftrag zum Zeichnen entsprechender Balken geben.

Mit diesem Hinweis sind wir nun abschließend in der Lage, die zwei Ereignisse des Modells zu betrachten. Beim Sortieren (Hilfsmethode Sort) und Zusammenfügen (Hilfsmethode Merge) feuert das Modell jeweils ein Ereignis (Tabelle 3):

Methode

Beschreibung

Ereignis SortRangeChanged

public event SortRangeChangedHandler SortRangeChanged;

Wann immer ein Feld halbiert wird und (rekursiv) die Methode Sort mit einem neuen Feld aufgerufen wird, wird das Event SortRangeChanged ausgelöst. Der Delegatetyp SortRangeChangedHandler ist wie folgt definiert:

public delegate void SortRangeChangedHandler (int start, int count);

Die Parameter start und count des Ereignisses beschreiben, welcher Teilbereich neu sortiert wird.

Ereignis ValueChanged

public event ValueChangedHandler ValueChanged;

Beim Zusammenfügen zweier sortierter Teilfelder in ein neues Teilfeld wird pro Einfügeoperation das Ereignis ValueChanged ausgelöst:

public delegate void ValueChangedHandler (int index, int value);

Die Parameter beschreiben, welches Feldelement (Parameter index) im neuen Feld mit welchem Wert (Parameter value) eingefügt wird.

Tabelle 3. Öffentliche Ereignisse der Klasse MergeSortModel.


Beachten Sie bei den beiden Parametern start (Ereignis SortRangeChanged) und index (Ereignis ValueChanged): Wenn Sie die aktuellen Werte dieser Parameter für eine Visualisierung verwenden wollen, dann müssen diese sich immer auf den Anfang der Ursprungsliste beziehen.

1.2. Visualisierung des Algorithmus: Die MergeSortView-Klasse (Ansicht)

Implementieren Sie zur Visualisierung des Mergesort-Algorithmus eine Spezialisierung der WPF-Basisklasse Canvas (aus dem Namensraum System.Windows.Controls) eine Klasse MergeSortView.

Ein MergeSortView-Objekt kann im Wesentlichen

  • vertikale Balken darstellen und

  • eine Gruppe von Balken mit einem Rahmen zusammenfassen.

Ein konkretes MergeSortView-Objekt sieht beispielsweise so aus (Abbildung 5):

Ein MergeSortView-Objekt mit Balken und einem Rechteck, das zwei Balken gruppiert.

Abbildung 5. Ein MergeSortView-Objekt mit Balken und einem Rechteck, das zwei Balken gruppiert.


Die öffentliche Schnittstelle der Klasse MergeSortView finden Sie in Tabelle 4 vor:

Element

Schnittstelle und Beschreibung

Eigenschaft Numbers

public List<int> Numbers { set; };

Mit dieser Eigenschaft übergibt man zum Zwecke der Visualisierung eine Zahlenliste an das Canvas-Objekt. Die Elemente der Liste werden gemäß ihrem Wert mit vertikalen Balken ansprechend dargestellt.

Methode ChangeValue

public void ChangeValue (int index, int value);

Mit ChangeValue lassen sich während des Sortiervorgangs Werte in der Liste (an der Position index) ändern. Der neue Wert wird durch value spezifiziert.

Methode SelectRange

public void SelectRange (int from, int to, Color c);

Der Mergesort-Algorithmus betrachtet während des Sortierens immer bestimmte Teilabschnitte aus der Ursprungsliste. Mit SelectRange werden derartige Teilbereiche grafisch hervorgehoben. Ein schwarzes Rechteck markiert Teilbereiche, die aktuell durch Halbierung einer Liste entstehen. Rote Rechtecke kennzeichnen Bereiche, die durch das Verschmelzen zweier Teilfolgen entstehen.

Tabelle 4. Öffentliche Elemente der Klasse MergeSortView.


Die übrigen, nicht-öffentlichen Methoden der Klasse MergeSortView dürfen Sie nach Ihrem eigenen Gusto entwickeln.

1.3. Steuerung des Algorithmus (Controller)

Mit einzelnen Controller-Objekten kann man die Dynamik der Simulation beeinflussen. Unter Controller-Objekten verstehen wir im Folgenden eine Reihe von Button- und ComboBox-Objekten wie zum Beispiel die Start-Schaltfläche, die eine Simulation startet. Mit der Random-Schaltfläche kann man die Zahlen in einer Liste fester Länge mischen. Die Größe der Liste kann mit einigen Standardwerten durch ein ComboBox-Steuerelement eingestellt werden. Für Testzwecke empfiehlt sich schließlich eine Reverse-Schaltfläche, die die Zahlen in der Liste in absteigender Reihenfolge anordnet. Auf diese Weise kann man das Sortieren im Verlauf einer Simulation einfacher verfolgen. Der Teilausschnitt der Anwendung mit den Controller-Objekten sollte in etwa wie in Abbildung 6 gezeigt aussehen:

Ein MergeSortController-Objekt mit zahlreichen Bedienelementen.

Abbildung 6. Ein MergeSortController-Objekt mit zahlreichen Bedienelementen.


Für die Simulation sind die Hilfsmittel des Multithreadings anzuwenden. Achten Sie bzgl. Start und Beenden einer Simulation auf die korrekte Anwendung der Klasse Thread (oder auch Task). Die Simulationsgeschwindigkeit kann mit Hilfe der Auswahlkomponente Interval durch den Controller geändert werden!

1.4. Die Anwendung im Überblick

Legen Sie bei der Integration der zuvor beschriebenen Teilkomponenten zu einer Gesamtanwendung das Model-View-Controller-Paradigma zugrunde. Das Aussehen der Gesamtanwendung sollte in etwa wie in Abbildung 7 aussehen:

Die WPF-MergeSort-Anwendung im Gesamtüberblick.

Abbildung 7. Die WPF-MergeSort-Anwendung im Gesamtüberblick.

2. Lösung

Die Beschreibung der Aufgabe legt eine Aufteilung des Projekts in drei Teilkomponenten nahe. In Listing 1 beginnen wir mit der Implementierung des Modells im Kontext eines .NET Class Library-Projekts:

001: namespace MergeSortModel
002: {
003:     public delegate void ListChangedHandler (List<int> numbers);
004:     public delegate void ValueChangedHandler(int index, int value);
005:     public delegate void SortRangeChangedHandler
006:         (int start, int count, MergeSortPhase phase);
007: 
008:     public enum MergeSortPhase { Divide, Conquer };
009: 
010:     public interface IMergeSort
011:     {
012:         // data
013:         List<int> Numbers { get; set; }
014:         int Delay { get; set; }
015: 
016:         // methods
017:         void Start();
018:         void Reverse();
019:         void Random();
020: 
021:         // events
022:         event ListChangedHandler ListChanged;
023:         event SortRangeChangedHandler SortRangeChanged;
024:         event ValueChangedHandler ValueChanged;
025:     }
026: 
027:     public class MergeSortModelImpl : IMergeSort
028:     {
029:         public event ListChangedHandler ListChanged;
030:         public event SortRangeChangedHandler SortRangeChanged;
031:         public event ValueChangedHandler ValueChanged;
032: 
033:         private List<int> numbers;
034:         private int delay;
035:         private Random rand;
036: 
037:         public MergeSortModelImpl()
038:         {
039:             this.numbers = new List<int>();
040:             this.rand = new Random();
041:             this.delay = 100;
042:         }
043: 
044:         public List<int> Numbers
045:         {
046:             set
047:             {
048:                 this.numbers = new List<int>(value);
049: 
050:                 if (this.ListChanged != null)
051:                     this.ListChanged.Invoke(new List<int>(this.numbers));
052:             }
053: 
054:             get
055:             {
056:                 return new List<int>(this.numbers);
057:             }
058:         }
059: 
060:         public int Delay
061:         {
062:             set
063:             {
064:                 this.delay = value;
065:             }
066: 
067:             get
068:             {
069:                 return this.delay;
070:             }
071:         }
072: 
073:         public void Start()
074:         {
075:             this.Sort();
076:         }
077: 
078:         public void Reverse()
079:         {
080:             for (int i = 0; i < this.numbers.Count; i++)
081:                 this.numbers[this.numbers.Count - 1 - i] = (i + 1);
082: 
083:             if (this.ListChanged != null)
084:                 this.ListChanged.Invoke(new List<int>(this.numbers));
085:         }
086: 
087:         public void Random()
088:         {
089:             for (int i = 0; i < this.numbers.Count; i++)
090:                 this.numbers[i] = i + 1;
091: 
092:             // shake entries of list
093:             for (int i = 0; i < 100; i++)
094:             {
095:                 int j = this.rand.Next(this.numbers.Count);
096:                 int k = this.rand.Next(this.numbers.Count);
097:                 int tmp = this.numbers[j];
098:                 this.numbers[j] = this.numbers[k];
099:                 this.numbers[k] = tmp;
100:             }
101: 
102:             if (this.ListChanged != null)
103:                 this.ListChanged.Invoke(new List<int>(this.numbers));
104:         }
105: 
106:         public void Sort()
107:         {
108:             this.numbers = this.Sort(0, this.numbers);
109:         }
110: 
111:         // private helper methods
112:         private List<int> Sort(int offset, List<int> list)
113:         {
114:             if (this.SortRangeChanged != null)
115:                 this.SortRangeChanged(
116:                     offset, list.Count, MergeSortPhase.Divide);
117: 
118:             if (this.Delay > 0)
119:                 Thread.Sleep(this.Delay);
120: 
121:             if (list.Count > 1)
122:             {
123:                 int len = list.Count / 2;
124: 
125:                 List<int> l1 = list.GetRange(0, len);
126:                 List<int> l2 = list.GetRange(len, list.Count - len);
127: 
128:                 l1 = Sort(offset, l1);
129:                 l2 = Sort(offset + len, l2);
130: 
131:                 List<int> l = Merge(offset, l1, l2);
132:                 return l;
133:             }
134:             else
135:             {
136:                 return list;
137:             }
138:         }
139: 
140:         private List<int> Merge(int offset, List<int> l1, List<int> l2)
141:         {
142:             List<int> result = new List<int>();
143: 
144:             if (this.SortRangeChanged != null)
145:                 this.SortRangeChanged(
146:                     offset, l1.Count + l2.Count, MergeSortPhase.Conquer);
147: 
148:             if (this.Delay > 0)
149:                 Thread.Sleep(this.Delay);
150: 
151:             int index = 0;
152:             int n = -1;
153: 
154:             while (l1.Count > 0 && l2.Count > 0)
155:             {
156:                 if (l1[0] < l2[0])
157:                 {
158:                     n = l1[0];
159:                     l1.RemoveAt(0);
160:                 }
161:                 else
162:                 {
163:                     n = l2[0];
164:                     l2.RemoveAt(0);
165:                 }
166: 
167:                 result.Add(n);
168: 
169:                 if (this.ValueChanged != null)
170:                     this.ValueChanged(offset + index, n);
171: 
172:                 if (this.Delay > 0)
173:                     Thread.Sleep(this.Delay);
174: 
175:                 index++;
176:             }
177: 
178:             if (l1.Count > 0)
179:             {
180:                 for (int i = 0; i < l1.Count; i++)
181:                 {
182:                     int n1 = l1[i];
183: 
184:                     result.Add(n1);
185: 
186:                     if (this.ValueChanged != null)
187:                         this.ValueChanged(offset + index, n1);
188: 
189:                     if (this.Delay > 0)
190:                         Thread.Sleep(this.Delay);
191: 
192:                     index++;
193:                 }
194:             }
195:             if (l2.Count > 0)
196:             {
197:                 for (int i = 0; i < l2.Count; i++)
198:                 {
199:                     int n2 = l2[i];
200: 
201:                     result.Add(n2);
202: 
203:                     if (this.ValueChanged != null)
204:                         this.ValueChanged(offset + index, n2);
205: 
206:                     if (this.Delay > 0)
207:                         Thread.Sleep(this.Delay);
208: 
209:                     index++;
210:                 }
211:             }
212: 
213:             return result;
214:         }
215:     }
216: }

Beispiel 1. Implementierung des Modells: .NET Class Library.


Wir fahren mit der Realisierung der Ansicht fort. Dieses Mal handelt es sich in Listing 2 um ein WPF Custom Control Library-Projekt:

001: namespace MergeSortView
002: {
003:     public class MergeSortViewControl : Canvas
004:     {
005:         // constant data
006:         private const int LeftBorder = 30;
007:         private const int BottomBorder = 30;
008: 
009:         private const int BarWidth = 25;
010:         private const int BarGap = 16;
011:         private const int ScaleFactor = 25;
012: 
013:         private const int RectMargin = 4;
014:         private const int RectStrokeThickness = 5;
015: 
016:         // data
017:         private List<int> numbers;
018:         private int maximum;
019: 
020:         private Rectangle range;
021: 
022:         // c'tor
023:         public MergeSortViewControl()
024:         {
025:             this.numbers = new List<int>();
026:             this.Background = new SolidColorBrush(Colors.LightGreen);
027: 
028:             // setup range rectangle
029:             this.CreateRectangle();
030:         }
031: 
032:         // public properties and methods
033:         public List<int> Numbers
034:         {
035:             set
036:             {
037:                 this.numbers = new List<int>(value);
038: 
039:                 // compute maximum value of array
040:                 this.maximum = this.numbers[0];
041:                 for (int i = 1; i < this.numbers.Count; i++)
042:                     if (this.maximum < this.numbers[i])
043:                         this.maximum = this.numbers[i];
044: 
045:                 this.DrawBars();
046: 
047:                 this.range.Visibility = Visibility.Hidden;
048:             }
049:         }
050: 
051:         public void ChangeValue(int index, int value)
052:         {
053:             if (this.Dispatcher.CheckAccess())
054:             {
055:                 if (this.Children.Count <= 1)
056:                     return;
057: 
058:                 // skip first children (range rectangle)
059:                 Rectangle r = (Rectangle) this.Children[index + 1];
060:                 r.Height = value * ScaleFactor;
061:             }
062:             else
063:             {  
064:                 this.Dispatcher.Invoke(
065:                     (Action)(() => { this.ChangeValue(index, value); })
066:                 );
067:             }
068:         }
069: 
070:         public void SelectRange(int start, int count, Color color)
071:         {
072:             if (start < 0 || count < 0)
073:                 return;
074: 
075:             if (this.Dispatcher.CheckAccess())
076:             {
077:                 this.UpdateRectangle(start, count, color);
078:             }
079:             else
080:             {
081:                 this.Dispatcher.Invoke(
082:                     (Action)(() => {
083:                         this.SelectRange(start, count, color);
084:                     })
085:                 );
086:             }
087:         }
088: 
089:         // private helper methods
090:         private void DrawBars()
091:         {
092:             // clear list of children, but don't remove rectangle shape
093:             int count = this.Children.Count;
094:             if (count > 1)
095:                 this.Children.RemoveRange(1, count - 1);
096: 
097:             for (int i = 0; i < this.numbers.Count; i++)
098:                 DrawBar(i);
099:         }
100: 
101:         private void DrawBar(int i)
102:         {
103:             Rectangle bar = new Rectangle();
104:             bar.Width = BarWidth;
105:             bar.Height = this.numbers[i] * ScaleFactor;
106: 
107:             bar.SetCurrentValue(Canvas.LeftProperty,
108:                 (double)(LeftBorder + i * (BarWidth + BarGap)));
109:             bar.SetCurrentValue(Canvas.BottomProperty,
110:                 (double) BottomBorder);
111: 
112:             bar.Fill = Brushes.Yellow;
113: 
114:             bar.Stroke = new SolidColorBrush(Colors.Blue);
115:             bar.StrokeThickness = 4;
116: 
117:             this.Children.Add(bar);
118:         }
119: 
120:         private void CreateRectangle()
121:         {
122:             this.range = new Rectangle();
123:             this.range.Stroke = new SolidColorBrush(Colors.Black);
124:             this.range.StrokeThickness = RectStrokeThickness;
125: 
126:             this.range.Visibility = Visibility.Hidden;
127: 
128:             // fixed rectangle's dependancy properties
129:             double bottom = BottomBorder - RectMargin - RectStrokeThickness;
130:             this.range.SetCurrentValue(Canvas.BottomProperty, bottom);
131: 
132:             this.Children.Add(this.range);
133:         }
134: 
135:         private void UpdateRectangle(int start, int count, Color color)
136:         {
137:             this.range.Visibility = Visibility.Visible;
138: 
139:             this.range.Stroke =
140:                 (color.Equals (Colors.Black)) ? Brushes.Black : Brushes.Red;
141: 
142:             // need to update with, height and left position of rectangle
143:             this.range.Width =
144:                 count * (BarWidth + BarGap) +
145:                 2 * RectMargin - RectStrokeThickness;
146:             this.range.Height =
147:                 this.maximum * ScaleFactor +
148:                 2 * RectMargin + 2 * RectStrokeThickness;
149: 
150:             double left =
151:                 LeftBorder + start * (BarWidth + BarGap) -
152:                 RectMargin - RectStrokeThickness;
153:             this.range.SetValue(Canvas.LeftProperty, left);
154:         }
155:     }
156: }

Beispiel 2. Implementierung der Ansicht: WPF Custom Control Library


Es fehlt noch das Hauptfenster der Anwendung. Hierzu folgen in Listing 3 und Listing 4 die entsprechenden XAML-Direktiven bzw. der C#-Logikanteil:

01: <Window
02:     x:Class="MergeSortSimulation.MainWindow"
03:     xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
04:     xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
05:     xmlns:local="clr-namespace:MergeSortView;assembly=MergeSortView"
06:     Title="MergeSort Simulator" Height="450" Width="525">
07:     
08:     <DockPanel LastChildFill="True">
09:         <!-- using ZIndex to give the Canvas control a lower ZIndex -->
10:         <Grid DockPanel.Dock="Top"
11:               DockPanel.ZIndex="2" Background="White" >
12:             <Grid.ColumnDefinitions>
13:                 <ColumnDefinition></ColumnDefinition>
14:                 <ColumnDefinition></ColumnDefinition>
15:                 <ColumnDefinition></ColumnDefinition>
16:                 <ColumnDefinition></ColumnDefinition>
17:             </Grid.ColumnDefinitions>
18:             <Grid.RowDefinitions>
19:                 <RowDefinition></RowDefinition>
20:                 <RowDefinition></RowDefinition>
21:             </Grid.RowDefinitions>
22: 
23:             <Button
24:                 Grid.Row="0" Grid.Column="0" Name="ButtonStart"
25:                 Grid.ColumnSpan="2" Click="Button_Click"
26:                 Margin="3,3,0,0" Content="Start"/>
27:             <Button
28:                 Grid.Row="0" Grid.Column="2" Name="ButtonRandom"
29:                 Click="Button_Click" Margin="3,3,0,0">Random</Button>
30:             <Button
31:                 Grid.Row="0" Grid.Column="3" Name="ButtonReverse"
32:                 Click="Button_Click" Margin="3,3,3,0">Reverse</Button>
33: 
34:             <Label Grid.Row="1" Grid.Column="0"
35:                    Margin="3,3,3,3" Content="Elements:" />
36:             <ComboBox
37:                 Grid.Row="1" Grid.Column="1"
38:                 Name="ComboBoxElements" Margin="3,3,3,3" 
39:                 SelectionChanged="ComboBox_SelectionChanged"/>
40:             <Label Grid.Row="1" Grid.Column="2"
41:                    Margin="3,3,3,3" Content="Interval:"/>
42:             <ComboBox
43:                 Grid.Row="1" Grid.Column="3"
44:                 Name="ComboBoxInterval" Margin="3,3,3,3" 
45:                 SelectionChanged="ComboBox_SelectionChanged"/>
46:         </Grid>
47: 
48:         <local:MergeSortViewControl
49:             x:Name="MergeSortView" DockPanel.ZIndex="1">
50:         </local:MergeSortViewControl>
51:         
52:     </DockPanel>
53: </Window>

Beispiel 3. Beschreibung des Hauptfensters: XAML.


001: using System.Threading.Tasks;
002: using MergeSortModel;
003: 
004: namespace MergeSortSimulation
005: {
006:     public partial class MainWindow : Window
007:     {
008:         private MergeSortModelImpl model;
009: 
010:         // threading utils
011:         private Task t;
012: 
013:         public MainWindow()
014:         {
015:             this.InitializeComponent();
016: 
017:             this.model = new MergeSortModelImpl();
018:             int[] numbers = new int[] { 9, 7, 5, 3, 1, 2, 4, 6, 8 };
019:             this.model.Numbers = numbers.ToList<int>();
020:             this.MergeSortView.Numbers = this.model.Numbers;
021: 
022:             this.model.ListChanged +=
023:                 new ListChangedHandler(
024:                     this.Model_ListChanged);
025:             this.model.SortRangeChanged +=
026:                 new SortRangeChangedHandler(
027:                     this.Model_MergeRangeChanged);
028:             this.model.ValueChanged +=
029:                 new ValueChangedHandler(
030:                     this.Model_ValueChanged);
031: 
032:             // adjust controller
033:             this.ComboBoxElements.Items.Add(5);
034:             this.ComboBoxElements.Items.Add(10);
035:             this.ComboBoxElements.Items.Add(20);
036:             this.ComboBoxElements.Items.Add(30);
037:             this.ComboBoxElements.Items.Add(40);
038:             this.ComboBoxElements.Items.Add(50);
039:             this.ComboBoxElements.SelectedIndex = 1;
040:             this.ComboBoxElements.SelectionChanged +=
041:                 new SelectionChangedEventHandler (
042:                     this.ComboBox_SelectionChanged);
043: 
044:             this.ComboBoxInterval.Items.Add(0);
045:             this.ComboBoxInterval.Items.Add(50);
046:             this.ComboBoxInterval.Items.Add(100);
047:             this.ComboBoxInterval.Items.Add(200);
048:             this.ComboBoxInterval.Items.Add(500);
049:             this.ComboBoxInterval.Items.Add(1000);
050:             this.ComboBoxInterval.SelectedIndex = 1;
051:             this.ComboBoxInterval.SelectionChanged +=
052:                 new SelectionChangedEventHandler (
053:                     this.ComboBox_SelectionChanged);
054:         }
055: 
056:         private void Model_ValueChanged(int index, int value)
057:         {
058:             this.MergeSortView.ChangeValue(index, value);
059:         }
060: 
061:         private void Model_MergeRangeChanged(
062:             int start, int count, MergeSortPhase phase)
063:         {
064:             Color color = (phase == MergeSortPhase.Divide) ?
065:                 Colors.Black : Colors.Red;
066:             this.MergeSortView.SelectRange(start, count, color);
067:         }
068: 
069:         private void Model_ListChanged(List<int> numbers)
070:         {
071:             this.MergeSortView.Numbers = numbers;
072:         }
073: 
074:         private void ComboBox_SelectionChanged(
075:             Object sender, SelectionChangedEventArgs e)
076:         {
077:             if (sender == this.ComboBoxElements)
078:             {
079:                 int count =
080:                     (int) this.ComboBoxElements.SelectedValue;
081:                 int[] numbers = new int[count];
082:                 for (int i = 0; i < numbers.Length; i++)
083:                     numbers[i] = i + 1;
084: 
085:                 this.model.Numbers = numbers.ToList<int>();
086:             }
087:             else if (sender == this.ComboBoxInterval)
088:             {
089:                 this.model.Delay =
090:                     (int)this.ComboBoxInterval.SelectedValue;
091:             }
092:         }
093: 
094:         private void Button_Click(Object sender, RoutedEventArgs e)
095:         {
096:             if (sender == this.ButtonStart)
097:             {
098:                  // any animation active
099:                  if (this.t != null)
100:                      return;
101:  
102:                  this.t = Task.Factory.StartNew(() => {
103:                      this.model.Start();
104:                      this.t = null;
105:                  });
106:             }
107:             else if (sender == this.ButtonRandom)
108:             {
109:                 this.model.Random();
110:             }
111:             else if (sender == this.ButtonReverse)
112:             {
113:                 this.model.Reverse();
114:             }
115:         }
116:     }
117: }

Beispiel 4. Realisierung der Hauptfenster-Logik: Code-Behind.