IT-Academy Logo
Sign Up Login Help
Home - Programmieren - Der BubbleSort-Algorithmus



Der BubbleSort-Algorithmus

Der BubbleSort-Algorithmus wird in seiner Funktionalität erklärt, weiter wird er dann in eine Funktion umgesetzt.


Autor: Patrick Bucher (paedubucher)
Datum: 01-11-2004, 12:52:51
Referenzen: keine
Schwierigkeit: Fortgeschrittene
Ansichten: 31916x
Rating: 8 (1x bewertet)

Hinweis:

Für den hier dargestellte Inhalt ist nicht der Betreiber der Plattform, sondern der jeweilige Autor verantwortlich.
Falls Sie Missbrauch vermuten, bitten wir Sie, uns unter missbrauch@it-academy.cc zu kontaktieren.

[Druckansicht] [Als E-Mail senden] [Kommentar verfassen]



Einleitung

Oftmals ist es nötig, ein Array (Datenfeld) auf- oder absteigend zu sortieren. Dazu gibt es einige Algorithmen. Der BubbleSort-Algorithmus ist nicht der schnellste, dafür ist er sehr einfach und somit besonders für Einsteiger geeignet. BubbleSort hat den Namen daher, dass die größeren Elemente wie Seifenblasen aufsteigen, die größte Seifenblase ist am Schluss ganz oben, die kleinste ganz unten.

Funktion

Beim BubbleSort-Algorithmus werden immer zwei benachbarte Elemente miteinander verglichen. Ist das eine größer als das andere, werden die beiden Werte vertauscht. Ein kleines Beispiel dazu.
Ausgangslage:
19	5	32	8

Erster Durchlauf
19	5	32	8	>>	5	19	32	8
5	19	32	8	>>	5	19	32	8
5	19	32	8	>>	5	19	8	32

Zweiter Durchlauf
5	19	8	32	>>	5	19	8	32
5	19	8	32	>>	5	8	19	32
5	8	19	32	>>	5	8	19	32
Bei jedem Durchlauf wird auch jedes einzelne Arrayelement mit dem nächsten verglichen. Pro Arrayelement läuft eine äußere und einer innere Schleife durch. In diesem Fall gäbe es hier vier äußere Schleifendurchläufe - in diesem Beispiel ist das Array nach zwei Durchläufen allerdings bereits korrekt sortiert. Man könnte mit entsprechenden Prüfungen nun das Sortieren abbrechen, für die "Grundversion" ist das aber erstmals unnötig.

Programmablauf

Die Funktionalität des BubbleSort-Algorithmus sollte man am besten in einem Nassi/Shneidermann-Diagramm darstellen, danach kann die Codierung in (fast) jeglicher beliebigen Sprache erfolgen. Mein Lösungsvorschlag:

BubbleSort-Algorithmus

Vor der Prüfung, ob ein Element größer als das darauf folgende ist, ist eine weitere Prüfung vorhanden. Y muss kleiner als der oberste Arrayindex sein, da in der zweiten Abfrage der Arrayindex y+1 benutzt wird. Angenommen, y ist bereits das höchste Element, so liegt y+1 in einem Speicherbereich nach dem Array - dieser hat jedoch keinen gültigen Wert. Einige Compiler würden sich hier ohne diese Abfrage bereits beschweren (was auch sehr hilfreich und erwünscht ist).

In der inneren if-Abfrage wird nun geprüft, ob das aktuelle Element größer ist, als das darauf folgende. Wenn dies der Fall ist, werden die beiden Werte vertauscht.

In diesem Beispiel wird in einer aufsteigenden Reihenfolge sortiert. Wenn man in absteigender Reihenfolge sortieren will, muss der Vergleich nur von "grösser als" in "kleiner als" geändert werden.

Programmcode

Die Funktion im Nassi/Shneidermann-Diagramm kann nun in jede beliebige Hochsprache umgeschrieben werden. Ich habe dafür C verwendet. Der Funktion muss das erste Arrayelement (als Zeiger) übergeben werden, dieser kann aber nachher in der Funktion wie üblich mit Eckklammern dereferenziert werden. Weiter wird der oberste Arrayindex benötigt.


void BubbleSort(int *Array, int Obergrenze)
{
	int x, y;
	int temp;
	for(x=0;x<=Obergrenze;x++)
	{
		for(y=0;y<=Obergrenze;y++)
		{
			if(y < Obergrenze)
			{
				if(Array[y] > Array[y+1])
				{
					temp = Array[y];
					Array[y] = Array[y+1];
					Array[y+1] = temp;
				}
			}
		}
	}
}


[back to top]



Userdaten
User nicht eingeloggt

Gesamtranking
Werbung
Datenbankstand
Autoren:04510
Artikel:00815
Glossar:04116
News:13565
Userbeiträge:16552
Queueeinträge:06247
News Umfrage
Ihre Anforderungen an ein Online-Zeiterfassungs-Produkt?
Mobile Nutzung möglich (Ipone, Android)
Externe API Schnittstelle/Plugins dritter
Zeiterfassung meiner Mitarbeiter
Exportieren in CSV/XLS
Siehe Kommentar



[Results] | [Archiv] Votes: 1158
Comments: 0