Sortieralgorithmus Selection 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 selectionSort ü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];

selectionSort(array1);
selectionSort(array2);
selectionSort(array3);

function selectionSort(array) {

}

Abb. 1: Ausgangssituation

Folie 2

Das Array soll mit dem kleinsten Wert beginnen.

Zunächst möchten wir erreichen, dass der kleinste Wert des zu sortierenden Arrays im Element mit Index 0 steht.

Dazu nehmen wir zunächst an, dass das Element mit Index 0 bereits den kleinsten Wert des zu sortierenden Arrays enthält. Anschließend vergleichen wir die Werte der folgenden Elemente und prüfen, ob deren Wert kleiner ist. Ist dies der Fall, dann merken wir uns den Index des Elements.

Sind alle Elemente geprüft – wir beschränken uns zunächst auf die ersten fünf Elemente –, stellen wir fest, ob das Element mit Index 0 bereits den kleinsten Wert des Arrays enthält. Falls ein anderes Element einen kleineren Wert enthält, dann werden deren Werte getauscht.

// 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];

selectionSort(array1);
selectionSort(array2);
selectionSort(array3);

function selectionSort(array) {
	var indexMinValue;
	var temp;
	
	indexMinValue = 0;
	
	if(array[1] < array[indexMinValue]) {
		indexMinValue = 1;
	}
	
	if(array[2] < array[indexMinValue]) {
		indexMinValue = 2; 
	}
	
	if(array[3] < array[indexMinValue]) {
		indexMinValue = 3; 
	}
	
	if(array[4] < array[indexMinValue]) {
		indexMinValue = 4;
	}
		
	if(0!=indexMinValue) {
		temp = array[0];
		array[0] = array[indexMinValue];
		array[indexMinValue] = temp;
	}
}

Abb. 2: Der kleinster Wert eines Arrays (Länge 5) steht im ersten Element.

Folie 3

Das Array beliebiger Länge soll mit dem kleinsten Wert beginnen.

Nun sollen nicht mehr nur die ersten fünf Werte des Arrays geprüft werden, sondern alle Werte.

Geprüft werden nacheinander das Element mit Index 1, dann das mit Index 2, ... und zum Schluss das letzte Element des zu sortierenden Arrays. Dazu nutzen wir eine Zählerschleife, deren Zählervariable als Startwert den Index des zweiten Elements erhält, und die ein letztes ausgeführt wird, wenn der Wert der Zählervariablen dem Index des letzten Elements entspricht.

Nachdem die Zählerschleife beendet ist, kennen wir den Index des Elements mit dem kleinsten Wert und verfahren damit wie bisher.

// 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];

selectionSort(array1);
selectionSort(array2);
selectionSort(array3);

function selectionSort(array) {
	var indexMinValue;
	var temp;
	
	/* Wir nehmen zunächst an, dass das Element mit Index 0 den kleinsten der noch
	   zu sortierenden Werte enthält. Sobald ein Element mit einem kleineren Wert
	   gefunden wird, merken wir uns dann stattdessen dessen Index. */
	indexMinValue = 0;
	
	for(let i=1; i<array.length; i++) {
		// Ist der Wert im Element mit Index i kleiner als der bisher kleinste Wert? 
		if(array[i] < array[indexMinValue]) {
			indexMinValue = i; // Ja! -> Index merken!
		}
	}
		
	/* Das Element mit Index 0 soll den kleinsten Wert des Arrays enthalten.
	   Wenn ein anderes Element einen kleineren Wert enthält, dann werden 
	   die Werte getauscht. */
	if(0!=indexMinValue) {
		temp = array[0];
		array[0] = array[indexMinValue];
		array[indexMinValue] = temp;
	}
}

Abb. 3: Der kleinster Wert eines Arrays beliebiger Länge steht im ersten Element.

Folie 4

Das Array ist aufsteigend sortiert.

Nachdem das Element mit Index 0 den kleinsten Wert des zu sortierenden Arrays enthält, muss nun dafür gesorgt werden, dass das Element mit Index 1 den kleinsten Wert der Elemente enthält, deren Werte bisher noch nicht nicht sortiert sind. Anschließend kommt das Element mit Index 2 an die Reihe usw. Die Wiederholungen enden, wenn das vorletzte Element den kleinsten Wert der Elemente enthält, deren Werte bisher noch nicht nicht sortiert sind. Dies ist in diesem Fall nur noch das letzte Element, das damit automatisch den größten Wert des Arrays enthält.

Dazu setzen wir erneut eine Zählerschleife ein. Als Startwert der Zählervariable legen wir den den Index des ersten Elements fest. Die Zählerschleife wird ein letztes ausgeführt, wenn der Wert der Zählervariablen dem Index des vorletzten Elements entspricht.

Zu Beginn einer Wiederholung nehmen wir zunächst an, dass das Element mit Index j – alle vorhergenden Elemente sind bereits sortiert – den kleinsten der noch zu sortierenden Werte enthält. Sobald ein Element mit einem kleineren Wert gefunden wird, merken wir uns dann stattdessen dessen Index.

Nachdem die äußere Zählerschleife beendet ist, ist das Array aufsteigend sortiert.

// 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];

selectionSort(array1);
selectionSort(array2);
selectionSort(array3);

function selectionSort(array) {
	var indexMinValue;
	var temp;
	
	for(let j=0; j<array.length-1; j++) {
		/* Zu Beginn einer Wiederholung nehmen wir zunächst an, dass das Element mit
		   Index j den kleinsten der noch zu sortierenden Werte enthält. Sobald ein
		   Element mit einem kleineren Wert gefunden wird, merken wir uns dann 
		   stattdessen dessen Index. */
		indexMinValue = j;
		
		/* Geprüft werden nacheinander das Element mit Index 1, dann das mit Index 2, ...
		   und zum Schluss das letzte Element des zu sortierenden Arrays. */ 
		for(let i=1+j; i<array.length; i++) {
			/* Ist der Wert im Element mit Index i kleiner als 
			   der bisher kleinste Wert? */ 
			if(array[i] < array[indexMinValue]) {
				indexMinValue = i; // Ja! -> Index merken!
			}
		}
			
		/* Das Element mit Index 0 soll den kleinsten Wert des Arrays enthalten.
		   Wenn ein anderes Element einen kleineren Wert enthält, dann werden 
		   die Werte getauscht. */
		if(0!=indexMinValue) {
			temp = array[0];
			array[0] = array[indexMinValue];
			array[indexMinValue] = temp;
		}
	}
}

Abb. 4: Nachdem die äußere Zählerschleife beendet ist, ist das Array aufsteigend sortiert.

Folie 5

Performancevergleich

Ein Klick auf die folgende Schaltfläche startet einen Performancevergleich des Selection-Sort-Algorithmus mit vier Varianten des Bubble-Sort-Algorithmus. 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 selectionSort(array) {
	var indexMinValue;
	var temp;
	
	for(let j=0; j<array.length-1; j++) {
		indexMinValue = j;
		
		for(let i=1+j; i<array.length; i++) {
			/* Ist der Wert im Element mit Index i kleiner als 
			   der bisher kleinste Wert? */ 
			if(array[i] < array[indexMinValue]) {
				indexMinValue = i; // Ja! -> Index merken!
			}
		}

		if(0!=indexMinValue) {
			temp = array[0];
			array[0] = array[indexMinValue];
			array[indexMinValue] = temp;
		}
	}
}

Abb. 5: Selection-Sort-Algorithmus

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. 6: 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. 7: 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. 8: 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. 9: Bubble-Sort-Algorithmus mit äußerer while-Schleife und Abbruch nach spätestens n-1 Durchläufen