Lotto mit Bubblesort

Gefällt Ihnen Ihr Programm aus der letzten Lektion? Zugegeben, es wäre noch schöner, wenn die Zahlen sortiert ausgegeben würde, so wie das auch am Ende bei der Ziehung Lottozahlen im Fernsehen passiert. Genau das soll im nun folgenden Beispiel geschehen, es ist also eine Erweiterung der Anwendung aus der letzten Lektion. Obwohl ein NSMutableArray mit nur wenigen Anweisung sortiert werden kann, wollen im ersten Schritt darauf verzichten und die Liste manuell sortieren. Wie Sie ein Array mit den Mitteln des Cocoa-Framework sortieren, ist Thema einer späteren Lektion.


Um Auflistungen, wie in diesem Fall ein NSMutableArray, zu sortieren, verwendet man in der Informatik gelegentlich ein als Bubble Sort bekanntes Verfahren. Es gibt unzählige andere, aber Bubble Sort ist eines der Bekanntesten und wahrscheinlich auch das Einfachste. Jeder Programmierer sollte in der Lage sein, einen Bubble Sort ohne viel Mühe zu programmieren.
Bei diesem Algorithmus werden schrittweise immer zwei Objekte einer Auflistung verglichen und anschließend vertauscht, wenn sie im Wert nicht der beabsichtigten Sortierreihenfolge entsprechen. Das klingt einfach und ist es auch.
Schreiben Sie den folgenden Programmcode zwischen den Schleifen zum Erzeugen der Zufallszahlen und dem Senden der Werte an die NSTextField.
Zu allererst benötigt man zwei NSNumber Bezeichner, die jeweils ein Element des NSMutableArray aufnehmen können. Hierbei genügt es, nur die Variablen zu deklarieren, es muss nicht mit alloc Speicher reserviert werden. Da bestehende Objekte aus einem Array verglichen werden sollen, genügt es, einen Zeiger auf diese Objekte zu haben. Speicherplatz haben diese Objekte bereits.

NSNumber *aZahl; NSNumber *bZahl;

Will man nun jeweils ein Objekt mit seinem Nachbarobjekt vergleichen, kommt eine for-Schleife zum Einsatz. Der Endwert der Schleife ist die Länge des Array minus Eins, denn das letzte Objekt hat kein nachfolgendes Objekt mehr, mit dem es verglichen werden könnte.

for (int i = 0; i < [zufallsArray count] - 1 ; i++) {     aZahl = [zufallsArray objectAtIndex:i];     bZahl = [zufallsArray objectAtIndex:i+1]; }

Anschließend wird die compare-Methode von NSNumber benutzt, um zu prüfen, ob die zwei Werte schon in der richtigen Reihenfolge angeordnet sind. Ist dies nicht der Fall, müssen sie getauscht werden. Die aZahl nimmt den Platz von bZahl an und umgekehrt.

if ([aZahl compare:bZahl] == NSOrderedDescending) {     [zufallsArray replaceObjectAtIndex:i+1 withObject:aZahl];     [zufallsArray replaceObjectAtIndex:i withObject:bZahl]; }

Diese Anweisungen sehen zwar auf den ersten Blick richtig aus, aber es fehlt eine ganz entscheidende Funktion, ohne die Ihr Programm garantiert abstürzt. Die Problematik liegt in der Speicherverwaltung von Objekten.
Sobald aZahl den Platz i+1 im Array annimmt, geht der ursprüngliche Wert an dieser Position verloren, da sein retain-Zähler 0 erreicht. Dummerweise ist der Zeiger von bZahl aber auf genau dieses Objekt gerichtet. Es fehlt also die Anweisung dieses Objekt im Speicher zu belassen, eine Aufgabe die retain übernimmt. Ist der Austausch gemacht, kann man mit release das Objekt wieder freigeben, da es jetzt wieder vom Array gehalten wird. Fehlerfrei sähe das Vertauschen der Objekte so aus:

if ([aZahl compare:bZahl] == NSOrderedDescending) {     [bZahl retain];     [zufallsArray replaceObjectAtIndex:i+1 withObject:aZahl];     [zufallsArray replaceObjectAtIndex:i withObject:bZahl];     [bZahl release]; }

Beim Bubble Sort kann ein Objekt maximal eine Position pro Durchlauf wandern. Der ungünstigste Fall wäre also, dass ein Objekt vom Ende der Auflistung zum Anfang verschoben werden muss. Dafür gibt es eine zweite for-Schleife, die so viele Durchläufe macht, wie Objekte in der Auflistung sind. Der gesamte Sortieralgorithmus sieht im Zusammenhang dann so aus:

// Sortieren mit Bubble Sort NSNumber *aZahl; NSNumber *bZahl; for (int j = 0; j < [zufallsArray count] -1; j++) {     for (int i = 0; i < [zufallsArray count] - 1 ; i++)     {         aZahl = [zufallsArray objectAtIndex:i];         bZahl = [zufallsArray objectAtIndex:i+1];         if ([aZahl compare:bZahl] == NSOrderedDescending)         {             [bZahl retain];             [zufallsArray replaceObjectAtIndex:i+1 withObject:aZahl];             [zufallsArray replaceObjectAtIndex:i withObject:bZahl];             [bZahl release];         }     } }

Obwohl diese Anwendung in seiner jetzigen Form fehlerfrei arbeitet, bieten sich noch einige Möglichkeiten, den Programmcode zu optimieren. So ist es zum Beispiel möglich, Objekte im Array mit nur einem einzigen Befehl zu vertauschen.

[zufallsArray exchangeObjectAtIndex:i withObjectAtIndex:i+1];

Ebenfalls unnötig ist es, Objekte aus dem NSMutableArray wieder in NSNumber umzuwandeln. Will man zwei Objekte im Array vergleichen, geht das auch direkt.

if ([[zufallsArray objectAtIndex:i] compare: [zufallsArray objectAtIndex:i+1]] ==      NSOrderedDescending) {     [zufallsArray exchangeObjectAtIndex:i withObjectAtIndex:i+1]; }

Der vollständige, auf das Wesentliche reduzierte Programmcode ist dann:

for (int j = 0; j < [zufallsArray count] -1; j++) {     for (int i = 0; i < [zufallsArray count] - 1 ; i++)     {         if ([[zufallsArray objectAtIndex:i] compare: [zufallsArray objectAtIndex:i+1]]              == NSOrderedDescending)         {             [zufallsArray exchangeObjectAtIndex:i withObjectAtIndex:i+1];         }     } }

nächste Seite