Teil 2 – Die Basics: Variablen, Datentypen, Ablaufstrukturen & Algorithmen

Einführung in die Programmierung: Variablen, Datentypen & Co
Kommentare

Die Basics sind das A und O der Programmierung. Dazu gehören die Definition von Variablen und die Auswahl der Datentypen. Die meisten Konzepte der Programmierung sind weitgehend sprachneutral. Es gilt, die richtigen Ablaufstrukturen umzusetzen und die Algorithmen zu verstehen, eigenständig zu entwerfen und zu implementieren. Der zweite Teil unseres Einführungskurses behandelt diese Themen am Beispiel von C#.

Programmierung basiert im Wesentlichen darauf, den richtigen Aufbau des Programms zu wählen (Architektur) und innerhalb dieser Struktur die Lösungen für die Problemstellung richtig, effizient, wartungsfreundlich und gemäß den neusten Erkenntnissen der Informatik umzusetzen. Um Programme zu erstellen, die diesen Anforderungen genügen, ist es zunächst die Aufgabe des (angehenden) Programmierers, sich mit den Basics der gewählten Programmiersprache vertraut zu machen. In einem bestimmten Umfang kann dieses Grundlagenwissen durch das Studium von Fachliteratur und die Teilnahme an Seminaren erarbeitet werden; der Großteil ist jedoch Erfahrungswissen, das sich bei der Lösung konkreter Problemstellungen ergibt.

Deshalb möchten wir den Leser fortlaufend motivieren, hier dargestelltes Wissen an eigenständigen Beispielen nachzuvollziehen, es zu erweitern und auch bewusst andere Lösungsansätze auszuprobieren. In diesem Teil der Serie (Kasten: „Artikelserie“) werden die Grundlagen der Programmiersprache C# – Variablen, Datentypen, Ablaufstrukturen und Algorithmen – in kompakter Form vorgestellt. Vieles davon lässt sich auch auf andere Programmiersprachen und Systemumgebungen außerhalb von .NET übertragen.

Artikelserie
Teil 1: Einführung: Programmentwicklung, Sprachen, Entwicklungsumgebung
Teil 2: Basics: Variablen, Datentypen, Ablaufstrukturen, Algorithmen
Teil 3: Objektorientierung: Klassen, Eigenschaften, Methoden, Ereignisse, Vererbung
Teil 4: User Interface: Design aus technischer Perspektive
Teil 5: Architektur: Anwendungsschichten und Kopplung, Model-View-Controller-Muster
Teil 6: Daten: Datenmodellierung, Datenbanken (Dateisystem, Server, Cloud)

Basics

Wie in anderen Programmiersprachen auch, besteht ein Programm in C# aus einzelnen Befehlen bzw. Anweisungen, die nach bestimmten Regeln im Quelltext notiert werden. Die Gesamtheit dieser Regeln wird als Syntax bezeichnet. Dabei ist zu beachten, dass jede Anweisung – im Regelfall sollte pro Quelltextzeile nur eine Anweisung notiert werden – mit einem Semikolon abgeschlossen wird. Zeilenumbrüche, Leerzeichen und Tabulatoren haben für den Compiler in C# keine Bedeutung, was in anderen Sprachen wie zum Beispiel F# anders ist. Dennoch können solche Elemente für die Formatierung des Quelltexts mit dem Ziel einer verbesserten Lesbarkeit eingesetzt werden. Um die Formatierung des Quellcodes muss man sich im Regelfall keine Gedanken machen; das erledigt Visual Studio automatisiert. Sobald eine Anweisung als syntaktisch fehlerfrei erkannt wurde, erfolgt die Formatierung. C# ist eine blockorientierte Programmiersprache, d. h. zusammenhängende Anweisungen (z. B. innerhalb einer Schleife) werden in geschweiften Klammern eingeschlossen (Listing 1).

Listing 1: Zusammenhängende Anweisungen in geschweiften Klammern
for (int i = 1; i<=100; i++)
{
  // Schleifenanweisungen
}
Ende

Eine besondere Bedeutung haben die sogenannten Schlüsselwörter (Tabelle 1). Dabei handelt es sich um vordefinierte, reservierte Bezeichner. Sie bilden den Kern der Sprache und stehen für eine andere Verwendung (zum Beispiel für Variablen) nicht zur Verfügung.

Krypczyk_tab1

Grundsätzlich sollte der Quelltext alleine gut verständlich sein, trotzdem ist es häufig angeraten, Erläuterungen zu ergänzen. Das geschieht in Form von Kommentaren direkt im Quelltext, die vom Compiler bei der Übersetzung des Programms ignoriert werden und nur einem leichteren Verständnis dienen. Man unterscheidet ein- und mehrzeilige Kommentare (Listing 2).

Listing 2: Kommentare in C#
private float nettoBetrag; // Betrag nach der Kalkulation 

/* Der folgend Quelltext dient
der Berechnung der Zwischensumme
*/

Datentypen und Variablen

Variablen dienen dazu, die Werte von Berechnungen und Auswertungen innerhalb eines Programms zu speichern; sie müssen dabei einem bestimmten Datentyp entsprechen. C# bietet ein Set von einfachen Datentypen an, die sich jeweils auf die Typen im .NET Framework beziehen (Tabelle 2). Dass die Definition der Datentypen im .NET Framework erfolgt, hat den Vorteil, dass die Datentypen auch in den anderen Programmiersprachen zur Verfügung stehen, die das .NET Framework verwenden, z. B. VB.NET. Damit ist es grundsätzlich möglich, dass Teilmodule komplexer Software in unterschiedlichen Sprachen erstellt werden und der Datenaustausch bzw. die gemeinsame Verwendung dieser Module in einer Projektmappe erfolgt.

Krypczyk_tab2

Variablen müssen bezüglich des gewählten Namens eindeutig sein. Grundsätzlich gelten die folgenden Konventionen:

  • Als Zeichen sind Groß- und Kleinbuchstaben, der Unterstrich und die Ziffern 0 bis 9 zulässig
  • Jeder Bezeichner muss mit einem Buchstaben oder einem Unterstrich beginnen
  • C# unterscheidet zwischen Groß- und Kleinschreibung (case-sensitive Programmiersprache)
  • Die Bezeichner der Variablen sollten mit einem Kleinbuchstaben beginnen
  • Unterstriche sind zu vermeiden
  • Falls man Bezeichner aus mehreren Wörtern zusammensetzt, sollte man ab dem zweiten Wort alle Wörter mit einem Großbuchstaben starten (z. B.: float kalkulationsUntergrenze)

Die Variablen müssen vor der ersten Verwendung deklariert werden. Das kann man mit der Initialisierung zusammenfassen. In Listing 3 sind einige Beispiele dargestellt.

Listing 3
// Variablen mit unterschiedlichen Datentypen
int Anzahl;
double Hoehe;
string nachName;

// Deklaration mehrerer Variablen gleichen Typs
int i, j, k;

// Deklaration mit Initialisierung
int anzahl = 99;
string nachName="Maier";
Ende

Eine besondere Rolle bei der Speicherung von zusammenhängenden Daten spielen so genannte Arrays. Sie gehören seit eh und je zum Handwerkszeug eines Programmierers, darum ist deren sichere Beherrschung Pflicht! Das Prinzip ist eigentlich ganz einfach: Es handelt sich um die strukturierte Ablage von Daten eines Typs im Speicher, wobei der Zugriff auf die einzelnen Elemente über einen Index erfolgt. Damit kann beispielsweise innerhalb einer Schleife auf die einzelnen Datenfelder zugegriffen werden.

Je nach Verwendung kommen ein- oder mehrdimensionale Arrays zum Einsatz. Grafisch kann man sich ein eindimensionales Array als Liste (Vektor) und ein zweidimensionales Array als Matrix vorstellen (Abb. 1). Ab mehr als drei Dimensionen kann keine grafische Darstellung mehr erfolgen; im Speicher des Computers können aber natürlich derartige Datenstrukturen aufgebaut werden. Ein einfaches Beispiel zeigt den Einsatz: Es soll eine Speicherform für die jährlichen Ausgaben und Einnahmen einer fiktiven Firma erzeugt werden. Die Datenstruktur kann in Form einer Tabelle angelegt werden. Spalte 1 enthält die Werte für die Einnahmen und Spalte 2 die Werte für die Ausgaben; den Zeilen sind die Werte für die Jahre (2005 bis 2015) zugeordnet. Will man beispielsweise den Wert für die Ausgaben des Jahres 2007 ermitteln, so muss man auf das dritte Element in der zweiten Spalte zugreifen.

Abb. 1: Datenspeicherung innerhalb eines Arrays (ein- bzw. zweidimensional)

Abb. 1: Datenspeicherung innerhalb eines Arrays (ein- bzw. zweidimensional)

In C# sind Arrays Objekte. Das bedeutet, dass es sich nicht nur um primitive Datentypen handelt. Als Objekte verfügen Arrays über Eigenschaften und Methoden, die zugehörige Klasse lautet System.Array. Zu Klassen und deren Bestandteilen erfahren Sie übrigens im nächsten Teil der Artikelserie mehr. Bevor man ein Array verwendet, muss man sich über dessen Größe (Dimension) Gedanken machen. Arrays sind in C# grundsätzlich statisch, d. h. ihre Größe ist fix. Zur Beachtung: Das .NET Framework kennt ähnliche, auf Listen basierte Speicherformen, deren Größe während der Nutzung dynamisch angepasst werden kann. Ein eindimensionales Array, das den Datentyp int (für ganzzahlige Werte) für seine Elemente verwendet, wird wie folgt definiert:

int [ ] TestArray;

Bevor ein Zugriff auf die einzelnen Elemente möglich ist, müssen sie mithilfe des new-Operators erzeugt werden. Ein Beispiel:

TestArray = new int [5];

Mittels dieser beiden Anweisungen wurde ein eindimensionales Array zur Verwaltung von fünf ganzzahligen Werten erstellt. Beide Befehle können auch platzsparend zu einer Zeile zusammengefasst werden:

int[ ] TestArray= new int [5];

Die Trennung ist dann sinnvoll, wenn zum Zeitpunkt der Definition die Anzahl der Elemente noch nicht feststeht. Der Datentyp int ist nur beispielhaft. Arrays können von beliebigen, auch selbst definierten, Datentypen und Klassen erzeugt werden. Die allgemeine Syntax lautet:

Datentyp [ ] Bezeichner = new Datentyp [Anzahl der Elemente];

Die Definition eines Arrays kann um die Initialisierung mit (Start-)Werten erweitert werden. Für ein ganzzahliges Array ergibt sich in diesem Fall die folgende Befehlszeile:

int[ ] TestArray = {0, 1, 2, 3};

Es wird ein eindimensionales Array mit der Zahlenfolge 0, 1, 2 und 3 erzeugt. Für zweidimensionale Arrays sehen die Schritte der Definition, Objekterzeugung und Initialisierung ähnlich aus. Aus dem folgendem Beispiel kann auf die Vorgehensweise bei höheren Dimensionen geschlossen werden:

int[,] TestArray;

Bzw. mit gleichzeitiger Erstellung der Objekte (am Beispiel einer 3×5-Matrix):

int[,] TestArray = new int [3,5];

Und die Erweiterung um die Initialisierung:

int[,] TestArray = 
{ 
  {0;1;2;3;4}
  {5;6;7;8;9}
};

Der Zugriff auf die einzelnen Elemente eines Arrays gestaltet sich denkbar einfach. Das gewünschte Element wird unter Angabe des Index (eindimensionales Array) oder der Indizes (mehrdimensionales Array) angesprochen. Beispielsweise wird mittels:

int a = TestArray[3];

das vierte Element aus dem Array mit der Bezeichnung TestArray ausgelesen und der lokalen Variablen a zugewiesen. Im Fall eines mehrdimensionalen Arrays sind die einzelnen Indexwerte durch Kommata zu trennen:

int a = TestArray[3, 4]

Zwingend zu beachten ist, dass der Array-Speicher nullbasiert ist. Das bedeutet, das erste Element ist mittels des Indexwerts 0 und das letzte Element über den Indexwert (n-1) zu erreichen. Dabei wurde angenommen, dass n die Größe des Array-Speichers – also die Anzahl der Elemente – darstellt. Wie bereits erwähnt, kennt .NET weitere modernere Datenstrukturen, um Elemente strukturiert zu speichern und über einen Index abzurufen. Insbesondere wurden diese Speicherkonzepte um alltägliche Aufgaben aus der Programmierpraxis wie zum Beispiel das Sortieren der Elemente, vereinfachtes Einfügen und Löschen oder ein Suchen nach bestimmten Kriterien erweitert. Steht man also während der Programmentwicklung vor der Aufgabe, Daten gleichen Typs in Listen- oder Matrixform zu speichern und zu verarbeiten, ist es empfehlenswert, die Dokumentation nach passenden Lösungsansätzen zu durchsuchen. Stichwörter für ein schnelles Auffinden sind in diesem Zusammenhang List und List<T> bzw. die Typen, die unter dem System.Collections.Generic-Namespace im .NET Framework abgelegt sind. Für unsere nächsten Aufgaben sollten die dargestellten Zusammenhänge jedoch zunächst genügen.

Operatoren

Operatoren verknüpfen Variablen miteinander und führen Berechnungen aus. Es ist zwischen arithmetischen Operatoren, Zuweisungsoperatoren, logischen Operatoren und Vergleichsoperatoren zu unterscheiden. Eine kompakte Zusammenstellung der wichtigsten Operatoren für die Sprache C# ist in Tabelle 3 zu sehen.

Krypczyk_tab3

Sieht eine Anweisung mehrere Operatoren vor, stellt sich die Frage nach der Reihenfolge (Priorität). Beispielsweise gilt – wie aus der Mathematik bekannt – ein Vorgang der Multiplikation und Division (Punktrechnung) vor der Addition und Subtraktion (Strichrechnung). Mittels Klammern kann die Reihenfolge der Bearbeitung den eigenen Anforderungen angepasst werden. Damit ergibt sich folgende Rangfolge der Operatoren:

  1. Klammern: ()
  2. Logisches NOT: !
  3. Multiplikation, Division, Modulo: *, /, %
  4. Addition und Subtraktion: +, –
  5. Kleiner als, kleiner gleich als, größer als und größer gleich als: <, <=, >, >=
  6. gleich, ungleich: ==, !=

Kontrollstrukturen

Grundsätzlich werden die Anweisungen in einem Computerprogramm von oben nach unten (Zeile für Zeile) und innerhalb einer Zeile von links nach rechts abgearbeitet. Diesen Ablauf bezeichnet man als linear. Mittels Verzweigungen und Schleifenanweisungen kann diese Vorgabe angepasst werden. Schleifenanweisungen wiederholen dabei eine bestimmte Menge von Anweisungen. Die Anzahl der Wiederholungen kann im Vorfeld bereits feststehen, sich aus einer Berechnung ergeben, oder die Schleife wird so lange durchlaufen, bis eine bestimmte Bedingung eintritt. Auswahlanweisungen dienen grundsätzlich der Fallunterscheidung. Je nach Vorliegen einer bestimmten Bedingung werden ausgewählte Codeabschnitte (Blöcke) ausgeführt oder ignoriert. Wichtige Kontrollstrukturen sind in Tabelle 4 zusammengestellt.

Krypczyk_tab4

Algorithmen

Rein formal ist ein Algorithmus ein präzise festgelegtes Verfahren zur Lösung von Problemen bzw. einer Klasse von Problemen, das aus endlich vielen, effektiv ausführbaren, elementaren Lösungsschritten besteht. Ein Algorithmus muss folgenden Bedingungen genügen: Spezifikation, Durchführbarkeit und Korrektheit (Tabelle 5).

Tabelle 5: Anforderungen an Algorithmen

Tabelle 5: Anforderungen an Algorithmen

Das Vorgehen bei der Entwicklung eines Algorithmus lässt sich verallgemeinern. Folgende Schritte sind zu durchlaufen:

  1. Konkretisierung der Problemstellung: Die Problemstellung ist fachlich aufzuarbeiten, d.h. sie ist vollständig vom Programmierer zu verstehen. Er muss beispielsweise wissen, welche Berechnungen in welcher Reihenfolge auszuführen sind.
  2. Ausarbeitung eines maschinenausführbaren Algorithmus: Er muss durch den Rechner ausgeführt werden können. Im Gegensatz zum Menschen können Computerprogramme nur streng nach einem bestimmten Ablaufschema vorgehen. Ein intuitives Gestalten des Lösungswegs ist nicht möglich.
  3. Beachtung des möglichen Fehlerverhaltens: Folgendes Beispiel: Für viele Berechnungen werden Funktionen wie Sinus benötigt. Bekanntermaßen beträgt der exakte Wert der Sinusfunktion für die Zahl π (Winkel von 180°) Null, also Sin(π) = 0. Diese Klarheit kann bei einer Berechnung mit dem Computer zu Problemen führen. Wird statt π eine (vermeintlich hinreichende) Näherung von zum Beispiel 3,14159 eingesetzt und aus dieser Zahl der Sinuswert errechnet, so ergibt sich eine Abweichung. Soll auf der Basis dieses Ergebnisses eine Prüfung durchgeführt werden (if Ergebnis == 0), so wird der betreffende Programmabschnitt nicht ausgeführt, weil die Prüfung dieser Bedingung kein positives Ergebnis liefert.
  4. Analyse des Laufzeitverhaltens: Komplexe Algorithmen (z. B. das Sortieren von Daten) können einen hohen Bedarf an Rechenzeit benötigen.
  5. Implementierung: In der jeweiligen Programmiersprache.
  6. Test: Zum einen ist auf logische Konsistenz zu überprüfen, d. h. werden alle Verzweigungen des Codes erreicht? In einem zweiten Schritt sollte eine Überprüfung mit Testdaten stattfinden. Referenzergebnisse können beispielsweise manuell ermittelt werden.

Algorithmen weisen oft einen komplizierten Ablauf auf, dessen Verständnis durch eine visuelle Darstellung deutlich verbessert werden kann. Dazu können beispielsweise Fluss- oder Struktogramme dienen.

Beispiel

Bisher war die Darstellung recht theoretisch. Sie haben viele Informationen über Variablen, Datentypen, Arrays, Operatoren und Algorithmen erhalten. In einem zusammenhängenden Beispiel werden wir all diese Elemente miteinander kombinieren und deren Anwendung demonstrieren. Hierzu greifen wir auf ein bekanntes, spielerisches Problem, das so genannte Acht-Damen-Problem, zurück. Informationen zur Aufgabenstellung finden Sie im Textkasten („Beispiel: Das Acht-Damen-Problem“)

Das Acht-Damen-Problem ist ein klassisches Schachproblem, das zuerst von M. Bezzel 1845 in einer Schachzeitung veröffentlicht wurde, aber weithin unbeachtet blieb. Es geht darum, acht Spielfiguren vom Typ der Dame so auf dem Schachfeld (8 x 8 Felder) zu platzieren, dass sie sich nicht gegenseitig bedrohen. Erst als die Aufgabe am 1.6.1850 von Dr. Nauk erneut zur Diskussion gestellt wurde, fand sie ein großes Echo. Als der blinde Dr. Nauk am 21.09.1850 sämtliche 92 Lösungen publizierte, hatte Gauß 72 Lösungen gefunden. Die Gesamtzahl aller möglichen Damenstellungen ist hier immerhin 88 = 224 = 16 777 216 [2]. Auch für die Leser, die keine Schachspieler sind, ist das Problem schnell erklärt. Eine auf dem Schachfeld platzierte Dame blockiert das von ihr eingenommene Feld und bedroht alle Felder in horizontaler, vertikaler und diagonaler Richtung (Abb. 2). Mittels eines Computerprogramms sollen alle möglichen Lösungen (insgesamt gibt es 92 bei einem 8×8-Feld, Abb. 3) ermittelt werden. Mit etwas systematischem Probieren kann man manuell eine erste Lösung finden (Abb. 4).

Abb. 2: Eine Dame bedroht Felder in horizontaler, vertikaler und diagonaler Richtung

Abb. 2: Eine Dame bedroht Felder in horizontaler, vertikaler und diagonaler Richtung

Abb. 3: Bei einem 8x8-Feld gibt es 92 Lösungen für das Acht-Damen-Problem [2]

Abb. 3: Bei einem 8×8-Feld gibt es 92 Lösungen für das Acht-Damen-Problem [2]

Abb. 4: Eine von 92 möglichen Lösungen für das Acht-Damen-Problem [2]

Abb. 4: Eine von 92 möglichen Lösungen für das Acht-Damen-Problem [2]

Für die Lösung dieser Aufgabe, d. h. das Platzieren der Damen auf dem Spielfeld ohne gegenseitige Bedrohung, existiert kein einfaches Lösungsverfahren. Die Zahl der möglichen Kombinationen ist zu groß; man sagt auch, das Problem ist NP-schwer. Derartige Probleme löst man mit dem Computer so, wie man es manuell auch machen würde – durch systematisches Probieren. Mit etwas Überlegung kommt man schnell zu dem Ergebnis, dass in jeder Zeile und in jeder Spalte nur eine Dame platziert werden kann. Damit steht für jede Dame beispielsweise die Zeile fest, und es wird lediglich die Spaltenposition gesucht. Dame Nummer 1 steht damit in Zeile 1, Dame Nummer 2 in Zeile 2 usw. Um gültige Lösungen zu ermitteln, geht man wie folgt vor:

  1. In der Größe des Spielfelds (8 x 8 Felder) wird ein zweidimensionales Array definiert, das den Zustand eines jeden Felds beschreibt. Der Datentyp des Arrays ist boolean, und dabei bedeuten die Werte false, dass dieses Feld aktuell nicht bedroht, und der Wert true, dass dieses Feld bedroht wird.
  2. Es wird ein weiteres eindimensionales Array (Größe 8) angelegt, das die Damen repräsentiert. Genauer: Hier wird die ermittelte Spaltenposition abgelegt. Der Spaltenindex läuft von 0 bis 7. Ein Wert von -1 bedeutet, dass die Dame noch nicht platziert ist.
  3. In einer äußeren Schleife wird das Array aller Damen durchlaufen; dabei wird versucht, eine Dame nach der anderen zu platzieren.
  4. Es muss eine Methode geschrieben werden, die diejenigen Felder als besetzt markiert, die durch eine Dame bedroht werden. Diese Methode ruft man immer dann auf, wenn man eine Dame platziert hat, und aktualisiert auf diese Weise den Status des Spielfelds fortlaufend.
  5. Bevor eine Dame platziert wird, ist zu prüfen, ob das betreffende Feld bedroht ist. Ist das nicht der Fall, kann die Dame dort positioniert werden. Ist das Feld bedroht, wird versucht, die Dame eine Spalte weiter rechts zu platzieren. Ist man am Ende der Spalten (Spaltenindex = 7) angekommen, wird ein Schritt zurückgegangen und eine neue Position der vorherigen Dame gesucht.
  6. Eine gültige Lösung ist erreicht, wenn alle acht Damen platziert sind. Danach wird die zuletzt platziert Dame wieder entfernt und für sie eine neue Position gesucht.

Anders zusammengefasst: Man probiert systematisch alle möglichen Kombinationen für die Stellung der acht Damen auf dem Schachfeld durch. Diese Vorgehensweise ist einem menschlichen Spieler aufgrund des Aufwands nur in sehr begrenzten Umfang möglich. Der Computer kann hier bereits deutlich größere Problemstellungen lösen. Ist jedoch die Anzahl der Möglichkeiten zu groß, so stoßen auch noch heutige Rechner an ihre Grenzen. In diesen Fällen benötigt es intelligentere Algorithmen, die gezielter nach möglichen Lösungen suchen und beispielsweise gleich zu Beginn unzulässige Kombinationen von der weiteren Untersuchung ausschließen. Dieser hier verbal beschriebene Algorithmus wurde in C# implementiert. Der Quellcode ist über die Webseite des Verlags verfügbar, wo die Lösungen sehr einfach in einer Liste ausgebeben werden. Vollziehen Sie die Abläufe damit nach und entwickeln Sie Ideen, wie das Vorgehen noch weiter vereinfacht werden kann. Die Laufzeit von Algorithmen kann sehr schnell sehr zeitintensiv werden, sodass sich Optimierungen durchaus lohnen.

Fazit, Hausaufgabe und Ausblick

In diesem Teil haben Sie ganz essenzielle und wichtige Grundlagen der Programmierung kennen gelernt. Sie sind die Basics der Programmierung und damit das Herzstück eines jeden Computerprogramms. Mittels Software sollen Probleme der realen Welt gelöst werden, dazu ist es notwendig, die Problemstellung zu verstehen, sie in vereinfachter Form abzubilden und einen Algorithmus zur Lösung der Problemstellung zu erarbeiten. Diese Vorgehensweise ist unabhängig von der Art des Computerprogramms. Es gilt gleichermaßen für ein Buchhaltungsprogramm wie für die Entwicklung eines Spiels. In der kommenden Ausgabe des Entwickler Magazins beschäftigen wir uns mit dem heutigen Standard der Programmentwicklung – der objektorientierten Programmierung. Bis dahin gibt es wieder eine Übungsaufgabe (Kasten: „Hausaufgabe: Von aufsteigenden Blasen lernen“), um mit dem bisher Gelesenen besser vertraut zu werden. Die Lösung finden Sie online.

Es geht um das Sortieren einer belieben Zahlenfolge. Sortierverfahren sind so alt wie die Computertechnologie und spielen weiterhin in fast jedem Programm eine Rolle. Es existieren unterschiedliche Algorithmen zum Sortieren. Die Ansätze unterscheiden sich u. a. in ihrem Implementierungsaufwand und im Ergebnis darin, wie viele Schritte notwendig sind, um eine Menge an Daten zu sortieren. Dabei können nicht nur Zahlen sortiert werden, sondern zum Beispiel auch Zeichenfolgen nach dem Alphabet oder beliebige andere Objekte. Voraussetzung ist lediglich, dass man die Reihenfolge zwischen zwei Objekten eindeutig festlegen kann.

Wir beschäftigen uns als Übung mit dem Sortieren einer Zahlenfolge. Dabei soll der so genannte Bubble-Sort-Algorithmus zum Einsatz kommen. Das Prinzip: Es wird ein Array mit den zu sortierenden Objekten durchlaufen, benachbarte Elemente werden miteinander verglichen und wenn nötig vertauscht. Schrittweise wird auf diese Weise die Lösung erzeugt. Der Algorithmus trägt diesen Namen, da das Maximum wie eine Luftblase aufsteigt (bzw. hier von links nach rechts wandert). Der Bubble-Sort-Algorithmus gehört zur Klasse der so genannten In-place-Verfahren, d. h. für die Sortierung wird kein weiterer Speicher (z. B. ein zweites Array) benötigt. Lediglich ein temporärer Datenspeicher für das Vertauschen von benachbarten Elementen ist vonnöten. Die Arbeitsweise der ersten beiden Durchläufe für die Zahlenfolge 54, 26, 93, 17, 77, 31, 44, 55, 20 ist in Abbildung 5 zu sehen.

Ihre Aufgabe: Initialisieren Sie ein Array mit diesen Werten und sortieren Sie es in aufsteigender Reihenfolge mithilfe des Bubble-Sort-Algorithmus.

Abb. 5: Die ersten beiden Schritte beim Sortieren einer Zahlenfolge mittels Bubble Sort

Abb. 5: Die ersten beiden Schritte beim Sortieren einer Zahlenfolge mittels Bubble Sort

Links & Literatur:

[1] Gewinnus, T.; Doberenz, W.: Der Visual C#-Programmierer, Carl Hanser Verlag, München, 2009
[2] Herrmann, D.: Algorithmen Arbeitsbuch, Addison-Wesley, 1995

Entwickler Magazin

Entwickler Magazin abonnierenDieser Artikel ist im Entwickler Magazin erschienen.

Natürlich können Sie das Entwickler Magazin über den entwickler.kiosk auch digital im Browser oder auf Ihren Android- und iOS-Devices lesen. In unserem Shop ist das Entwickler Magazin ferner im Abonnement oder als Einzelheft erhältlich.

Aufmacherbild: Rows of butterfly cocoons and newly hatched butterfly via Shutterstock / Urheberrecht: Ksenia Ragozina

Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -