Sortieralgorithmus Bubble Sort

Präsentationsmodus

Folie 1

Ausgangssituation

Gegeben sind die Arrays array1, array2 und array3. Sie haben eine unterschiedliche Länge und enthalten verschiedene ganzzahlige Werte. Zu Testzwecken wird jedes dieser Arrays an die Funktion bubbleSort übergeben werden, die die Werte des übergebenen Arrays jeweils aufsteigend sortieren soll.

// Testarrays:
var array1 = [5, 4, 9, 1, 0];
var array2 = [11, 18, -4, -15, 3, 1, 17];
var array3 = [6, 1, 2, 3, 4, 5];

bubbleSort(array1);
bubbleSort(array2);
bubbleSort(array3);

function bubbleSort(array) {

}

Abb. 1: Ausgangssituation

Folie 2

Vergleich

Ist der Wert des 1. Elements größer als der Wert seines Nachfolgers? Dann sollen die beiden Werte getauscht werden!

// Testarrays:
var array1 = [5, 4, 9, 1, 0];
var array2 = [11, 18, -4, -15, 3, 1, 17];
var array3 = [6, 1, 2, 3, 4, 5];

bubbleSort(array1);
bubbleSort(array2);
bubbleSort(array3);

function bubbleSort(array) {
	// Ist der Wert des 1. Elements größer als der seines Nachfolgers?
	if(array[0] > array[1]) {
		// Ja! -> Werte tauschen!
	}
}

Abb. 2: Vergleich

Folie 3

Tausch

Der Wert des 2. Elements wird in der Variable temp zwischengespeichert. Anschließend wird dem 2. Element der Wert des 1. Elements zugewiesen. Abschließend wird der in der Variable temp zwischengespeicherte Wert dem 1. Element zugewiesen.

// Testarrays:
var array1 = [5, 4, 9, 1, 0];
var array2 = [11, 18, -4, -15, 3, 1, 17];
var array3 = [6, 1, 2, 3, 4, 5];

bubbleSort(array1);
bubbleSort(array2);
bubbleSort(array3);

function bubbleSort(array) {
	let temp;
	
	// Ist der Wert des 1. Elements größer als der seines Nachfolgers?
	if(array[0] > array[1]) {
		// Ja! -> Werte tauschen!
		temp = array[1];
		array[1] = array[0];
		array[0] = temp;
	}
}

Abb. 3: Tausch

Folie 4

Vergleich aller Elementwerte mit ihrem Nachfolger

Zur Entwicklungszeit ist nicht bekannt, wie viele Elemente das übergebene Array besitzt. Durch den Quellcode in Abb. 4 werden die ersten vier Elementwerte mit ihrem Nachfolger verglichen. Hat das Array weniger als fünf Elemente, führt dies zu einem Fehler. Hat es mehr Elemente, werden deren Werte nicht geprüft!

// Testarrays:
var array1 = [5, 4, 9, 1, 0];
var array2 = [11, 18, -4, -15, 3, 1, 17];
var array3 = [6, 1, 2, 3, 4, 5];

bubbleSort(array1);
bubbleSort(array2);
bubbleSort(array3);

function bubbleSort(array) {
	let temp;
	
	// Ist der Wert des 1. Elements größer als der seines Nachfolgers?
	if(array[0] > array[1]) {
		// Ja! -> Werte tauschen!
		temp = array[1];
		array[1] = array[0];
		array[0] = temp;
	}
	
	// Ist der Wert des 2. Elements größer als der seines Nachfolgers?
	if(array[1] > array[2]) {
		// Ja! -> Werte tauschen!
		temp = array[2];
		array[2] = array[1];
		array[1] = temp;
	}
	
	// Ist der Wert des 3. Elements größer als der seines Nachfolgers?
	if(array[2] > array[3]) {
		// Ja! -> Werte tauschen!
		temp = array[3];
		array[3] = array[2];
		array[2] = temp;
	}
	
	// Ist der Wert des 4. Elements größer als der seines Nachfolgers?
	if(array[3] > array[4]) {
		// Ja! -> Werte tauschen!
		temp = array[4];
		array[4] = array[3];
		array[3] = temp;
	}
}

Abb. 4: Problem: Wie viele Elemente hat das zu sortierende Array?

Folie 5

Vergleich aller Elementwerte mit ihrem Nachfolger

Die Anzahl der Vergleiche, die notwendig sind, um jeden Elementwert des übergebenen Arrays mit seinem Nachfolgewert zu vergleichen, lässt sich aus der Länge des Arrays berechnen. Der Wert eines jeden Elements wird einmal mit dem seines Nachfolgers verglichen. Bei einem Array der Länge n sind das n-1 Vergleiche. Mit Hilfe einer Zählerschleife lassen sich die erforderlichen Vergleiche dann durchführen. Da das 1. Element den Index 0 besitzt, wählen wir 0 als Startwert der Zählervariable. Die Zählerschleife soll ein letztes Mal ausgeführt werden, wenn die Zählervariable dem Index des vorletzten Elements entspricht. Daraus ergibt sich für die Zählerschleife die Ausführungsbedingung (Zählervariable < Arraylänge - 1).

// Testarrays:
var array1 = [5, 4, 9, 1, 0];
var array2 = [11, 18, -4, -15, 3, 1, 17];
var array3 = [6, 1, 2, 3, 4, 5];

bubbleSort(array1);
bubbleSort(array2);
bubbleSort(array3);

function bubbleSort(array) {
	let temp;
	
	/* Der Wert eines jeden Elements wird einmal mit dem seines
	   Nachfolgers verglichen. Ist er größer wird getauscht. */
	for(let i=0; i<array.length-1; i++) {
		// Ist der Wert des Elements mit Index i größer als der seines Nachfolgers?
		if(array[i] > array[i+1]) {
			// Ja! -> Werte tauschen!
			temp = array[i+1];
			array[i+1] = array[i];
			array[i] = temp;
		}
	}
}

Abb. 5: Eine Zählerschleife ermöglicht es, die Anzahl der Vergleiche variabel zu steuern.

Folie 6

Ausgabe der Elementwerte

Nachdem der Wert eines jeden Elements einmal mit dem seines Nachfolgers verglichen und ggf. getauscht wurde, enthält das letzte Element des Arrays den größten Wert. Zur Kontrolle geben wir die Elementwerte des Arrays vor und nach dem Durchlauf der Zählerschleife auf der Konsole aus.

// Testarrays:
var array1 = [5, 4, 9, 1, 0];
var array2 = [11, 18, -4, -15, 3, 1, 17];
var array3 = [6, 1, 2, 3, 4, 5];

bubbleSort(array1);
bubbleSort(array2);
bubbleSort(array3);

function bubbleSort(array) {
	let temp;
	
	// Ausgabe der Arraywerte vor der Sortierung.
	console.log(array.toString());
	
	/* Der Wert eines jeden Elements wird einmal mit dem seines
	   Nachfolgers verglichen. Ist er größer wird getauscht. */
	for(let i=0; i<array.length-1; i++) {
		// Ist der Wert des Elements mit Index i größer als der seines Nachfolgers?
		if(array[i] > array[i+1]) {
			// Ja! -> Werte tauschen!
			temp = array[i+1];
			array[i+1] = array[i];
			array[i] = temp;
		}
	}
	
	/* Ausgabe der Arraywerte nachdem der Wert eines jeden
	   Elements einmal mit dem seines Nachfolgers verglichen
	   und ggf. getauscht wurde. Im letzten Element steht nun
	   der größte Wert des Arrays. */
	console.log(array.toString());
}

Abb. 6: Ausgabe der Elementwerte

Folie 7

Array aufsteigend sortieren

Nachdem die innere Zählerschleife einmal durchlaufen wurde, steht im letzten geprüften Element der größte Wert des Arrays. Der zweite Durchlauf kann daher enden, nachdem der drittletzte mit dem zweitletzten Elementwert verglichen wurde. Denn im letzten Element steht bereits der größte Wert des Arrays. Im zweiten Durchlauf wird also ein Vergleich weniger durchgeführt als im ersten. Außerdem steht, nachdem er beendet ist, im vorletzten Element des Arrays der größte Wert der in diesem Durchlauf geprüften Elementwerte. Auch in jedem weiteren Durchlauf muss der Wert des jeweils letzten geprüften Elements im darauffolgenden Durchlauf nicht mehr geprüft werden. Die Zahl der Vergleiche sinkt also mit jedem Durchlauf um 1. Ein Array der Länge n ist somit spätestens nach n-1 Durchläufen aufsteigend sortiert. Denn in diesem Durchlauf findet nur noch ein Vergleich statt, nämlich der, ob der 1. Elementwert größer ist als der zweite.
Die äußere Schleife könnte also mit einem Zählerwert von 1 beginnen und bei einem einem Zählerwert von n-1 ein letztes Mal ausgeführt werden. Oder Sie beginnt mit einem Zählerwert von 0 und endet, wenn die Zählervariable den Wert n-1 erreicht. Dies hat den Vorteil, dass der Zählerwert der äußeren Schleife stets die Anzahl der bereits sortierten Werte angibt. Diese müssen von der inneren Schleife nicht mehr geprüft werden.

// Testarrays:
var array1 = [5, 4, 9, 1, 0];
var array2 = [11, 18, -4, -15, 3, 1, 17];
var array3 = [6, 1, 2, 3, 4, 5];

bubbleSort(array1);
bubbleSort(array2);
bubbleSort(array3);

function bubbleSort(array) {
	let temp;
	
	// Ausgabe der Arraywerte vor der Sortierung.
	console.log(array.toString()); 
	
	/* Nach jedem Durchlauf muss der Wert des jeweils letzten geprüften 
	   Elements im darauffolgenden Durchlauf nicht mehr geprüft werden.
	   Die Zahl der Wiederholungen sinkt also mit jedem Durchlauf um 1.
	   Ein Array der Länge n ist nach n-1 Durchläufen in jedem Fall
	   aufsteigend sortiert. */
	for(let j=0; j<array.length-1; j++) {
		/* Nach einem Durchlauf, in dem der Reihe nach der Wert der
		   Elemente mit dem ihres Nachfolgers verglichen und, falls
		   er größer ist, getauscht wird, steht im letzten geprüften
		   Element der größte Wert der verglichenen Elemente.
		   Die j hintersten Werte sind bereits aufsteigend sortiert.
		   In den vorderen Elementen gibt es keine größeren Werte mehr.
	       Sie müssen daher nicht mehr geprüft werden. */
		for(let i=0; i<array.length-1-j; i++) {
			/* Ist der Wert des Elements mit Index i größer als der
			   seines Nachfolgers? */
			if(array[i] > array[i+1]) {
				// Ja! -> Werte tauschen!
				temp = array[i+1];
				array[i+1] = array[i];
				array[i] = temp;
			}
		}
	}
	
	/* Ausgabe der Arraywerte nach dem Sortieren. */
	console.log(array.toString()); 
}

Abb. 7: Bubble-Sort-Algorithmus

Folie 8

Abbruch sobald das Array sortiert ist

In der vorhergehenden Version des Bubble-Sort-Algorithmus führt die äußere Zählerschleife immer n-1 Durchläufe aus. Danach ist das übergebene Array in jedem Fall sortiert. In manchen Fällen kann das übergebene Array jedoch schon früher sortiert sein. Zum Beispiel ist array3 bereits nach einem Durchlauf der äußeren Zählerschleife aufsteigend sortiert. Wurde in einem kompletten Durchlauf der äußeren Schleife kein einziger Tausch durchgeführt, ist das Array sortiert und die Schleife kann abgebrochen werden.

Die Prüfung, ob ein Tauschvorgang durchgeführt wurde, erfordert zusätzliche Anweisungen, deren Ausführung zusätzliche Zeit kostet. Eine Zeitersparnis gegenüber der vorhergehenden Version des Bubble-Sort-Algorithmus ohne Prüfung ist damit nur gegeben, wenn das Array bereits nach deutlich weniger als n-1 Durchläufen sortiert ist.

// Testarrays:
var array1 = [5, 4, 9, 1, 0];
var array2 = [11, 18, -4, -15, 3, 1, 17];
var array3 = [6, 1, 2, 3, 4, 5];

bubbleSort(array1);
bubbleSort(array2);
bubbleSort(array3);

function bubbleSort(array) {
	let temp;
	let werte_getauscht = false;
	
	// Ausgabe der Arraywerte vor der Sortierung.
	console.log(array.toString()); 
	
	/* Nach jedem Durchlauf muss der Wert des jeweils letzten geprüften 
	   Elements im darauffolgenden Durchlauf nicht mehr geprüft werden.
	   Die Zahl der Wiederholungen sinkt also mit jedem Durchlauf um 1.
	   Ein Array der Länge n ist nach n-1 Durchläufen in jedem Fall
	   aufsteigend sortiert. */
	for(let j=0; j<array.length-1; j++) {
		werte_getauscht = false;
		
		/* Nach einem Durchlauf, in dem der Reihe nach der Wert der
		   Elemente mit dem ihres Nachfolgers verglichen und, falls
		   er größer ist, getauscht wird, steht im letzten geprüften
		   Element der größte Wert der verglichenen Elemente.
		   Die j hintersten Werte sind bereits aufsteigend sortiert.
		   In den vorderen Elementen gibt es keine größeren Werte mehr.
	       Sie müssen daher nicht mehr geprüft werden. */
		for(let i=0; i<array.length-1-j; i++) {
			/* Ist der Wert des Elements mit Index i größer als der
			   seines Nachfolgers? */
			if(array[i] > array[i+1]) {
				// Ja! -> Werte tauschen!
				temp = array[i+1];
				array[i+1] = array[i];
				array[i] = temp;
				werte_getauscht = true;
			}
		}
		
		/* Wurde in einem kompletten Durchlauf der äußeren Schleife
		kein einziger Tausch durchgeführt, ist das Array sortiert und die
		Schleife kann abgebrochen werden. */
		if(!werte_getauscht) {
			break;
		}
	}
	
	/* Ausgabe der Arraywerte nach dem Sortieren. */
	console.log(array.toString()); 
}

Abb. 8: Abbruch sobald das Array sortiert ist.

Folie 9

Performancevergleich

Ein Klick auf die folgende Schaltfläche startet einen Performancevergleich der folgenden vier Bubble-Sort-Algorithmen. Nacheinander werden 100 Arrays der Länge 1000 generiert und mit ganzzahligen Zufallszahlen aus dem Intervall [-1000; 1000] gefüllt. Jedes Array wird für jeden Algorithmus einmal geklont und anschließend durch diesen aufsteigend sortiert. Abschließend wird die durchschnittliche Zeitdauer, die jeder der vier Algorithmen im Schnitt zur Sortierung eines Arrays benötigte, ausgegeben. Außerdem wird die Abweichung zur durchschnittlichen Dauer aller vier Algorithmen angezeigt.

function bubbleSort1(array) {
	let temp;
	
	for(let j=0; j<array.length-1; j++) {
		for(let i=0; i<array.length-1-j; i++) {
			if(array[i] > array[i+1]) {
				temp = array[i+1];
				array[i+1] = array[i];
				array[i] = temp;
			}
		}
	}
}

Abb. 9: Bubble-Sort-Algorithmus mit äußerer Zählerschleife

function bubbleSort2(array) {
	let temp;
	let werte_getauscht = false;
	
	for(let j=0; j<array.length-1; j++) {
		werte_getauscht = false;
		
		for(let i=0; i<array.length-1-j; i++) {
			if(array[i] > array[i+1]) {
				temp = array[i+1];
				array[i+1] = array[i];
				array[i] = temp;
				werte_getauscht = true;
			}
		}
	
		if(!werte_getauscht) {
			break;
		}
	}
}

Abb. 10: Bubble-Sort-Algorithmus mit äußerer Zählerschleife und Abbruch, falls keine Werte getauscht wurden

function bubbleSort3(array) {
	var getauscht = true;
	var anzahlDurchlauefe = 0;
					
	while(getauscht) {		
		getauscht = false;
		
		for(let i=0; i<array.length-1-anzahlDurchlauefe; i=i+1) {
			if(array[i] > array[i+1]) {
				let temp = array[i+1];
				array[i+1] = array[i];
				array[i] = temp;
				getauscht = true;
			}
		}
		
		anzahlDurchlauefe++;
	}
}

Abb. 11: Bubble-Sort-Algorithmus mit äußerer while-Schleife

function bubbleSort4(array) {
	var getauscht = true;
	var anzahlDurchlauefe = 0;
					
	while(getauscht && anzahlDurchlauefe < array.length-1) {		
		getauscht = false;
		
		for(let i=0; i<array.length-1-anzahlDurchlauefe; i=i+1) {
			if(array[i] > array[i+1]) {
				let temp = array[i+1];
				array[i+1] = array[i];
				array[i] = temp;
				getauscht = true;
			}
		}
		
		anzahlDurchlauefe++;
	}
}

Abb. 12: Bubble-Sort-Algorithmus mit äußerer while-Schleife und Abbruch nach spätestens n-1 Durchläufen