Selectionsort

Selectionsort (Sortieren durch Auswahl), auch MinSort bzw. MaxSort genannt, ist ein Sortieralgorithmus, der eine Reihe einer Linearen Liste nach der Größe sortiert. In seiner Grundform wird er als ein sehr instabiler Sortieralgorithmus bezeichnet, aber lässt sich dafür sehr leicht und schnell implementieren. Wegen seiner Komplexität wird davon abgeraten, diesen Algorithmus bei sehr großen Feldern bzw. Linearen Listen einzusetzen. Seine Laufzeit hängt quadratisch von der Anzahl der sortierenden Elemente ab, sprich der Größenordnung O(n²).

Prinzip

Dieser Selection-Algorithmus basiert auf zwei Vorgehensweisen. Die Grundidee ist hier die Minimum bzw. Maximumsuche. Die Vorgehensweise, wie man das Minimum bzw. Maximum einer Linearen Liste findet kann auf dem Ko-System von Wettkämpfen übertragen. Zwei Gegner treten gegeneinander an, hier wären es zwei Zahlen. Wenn wir das Minimum betrachten, dann gewinnt die Zahl die kleiner ist. Beim Maximum ist es selbstverständlich anders herum. Der Gewinner tritt jetzt gegen den nächsten Gegner an, bis am Ende einer übrigbleibt und diesen Wettkampf gewinnt. Der Computer setzt dieses Prinzip in der Praxis wie folgt um: Er setzt die Bedingung voraus, dass die erste Zahl in der Linearen Liste die kleinste bzw. größte ist, weil er noch keine Zahl verglichen hat. Jetzt vergleicht er die 1 Zahl mit der 2 Zahlen und speichert die kleinere bzw. größere Zahl. Danach nimmt er die nächste Zahl und vergleicht Sie mit der davor gespeicherten Zahl. Wenn er das Minimum bzw. Maximum gefunden hat, dann vertauscht er die Zahl mit der ersten Zahl im Feld. Jetzt sucht er das nächste Minimum bzw. Maximum und setzt es auf der zweiten Stelle im Feld. Diese Vergleiche werden solange fortgesetzt bis man auch die letzte Zahl verglichen hat und somit die Zahlenreihe sortiert wurde.

Implementierung in C++

#include <iostream>
#include <ctime>
using namespace std; 

void selectionsort (int *pFeld, int size) {
	int min;
	for (int i = 0; i < size; i++) {
		min = i;
		for (int j = i + 1; j < size; j++) {
			if (pFeld[j] < pFeld[min]) {
				min = j;
			}
		}
		int temp = pFeld[i];
		pFeld[i] = pFeld[min];
		pFeld[min] = temp;
}
}
	
int main () {
	srand (time(NULL));
	int count; 
	cout <<"\n Wie viel Elemente wollen Sie in der Liste zufällig generieren?";
	cin >> count; 
	int *array = new int[count];
	for (int i = 0; i < count; i++) {
		array[i] = 1 + rand()% 15;
	}
	cout <<"\n Elemente in der Liste vor dem Sortieren:";
	for (int i = 0; i < count; i++) {
		cout << array[i] << " ";
	}
	cout <<"\n Elemente in der Liste nach dem Sortiren:"; 
	selectionsort (array, count);
	for (int i = 0; i < count; i++) {
		cout << array[i] << " ";
	}
}

Der eigentliche Hauptteil dieses Programmes liegt in der Funktion selectionsort(). Dieser Funktion werden zwei Parameter übergegeben. Einmal ein Pointer auf das zu sortierende Feld und die Anzahl der Elemente im Feld. Die Funktion arbeitet mit zwei for-Schleifen. Die äußere for-Schleife durchläuft alle zu sortierenden Elemente im Feld. Der Hilfsvariable min wird der Wert der Index Variable i zugewiesen. In der inneren for-Schleife wird das Minimum der Zahlenreihe gesucht. Die Schleife fängt beim 2 Element des Feldes an und vergleicht die einzelnen Zahlen miteinander. Wenn das Feld pFeld[j] kleiner ist als das momentane Minimum, dann wird der Variable min das Feld pFeld[i] zugewiesen. Wenn das Minimum durch die innere for-Schleife gefunden wurde, dann werden die Werte der Felder pFeld[i] und pFeld[min] vertauscht. In der main() Funktion wird der Benutzer aufgefordert, die Anzahl der Elemente zu bestimmen, was anschließend in der count Variable gespeichert wird und mit dem new Befehl dynamisch erstellt wird. In der for-Schleife wird jedem Element eine zufällig generierte Zahl zwischen 1 und 15 zugewiesen und anschließend durch die darauffolgende for-Schleife ausgegeben. Jetzt wird die vorher geschrieben selectionsort() Funktion eingesetzt und aufgerufen. Zum Schluss werden die sortierten Elemente wieder ausgegeben.

Ausgabe des Programmes:

Wie viel Elemente wollen Sie in der Liste zufällig generieren?

6

Elemente in der Liste vor dem Sortieren:7 4 3 4 1 10

Elemente in der Liste nach dem Sortiren:1 3 4 4 7 10

Achtung: Die Zahlen in der Liste können sich unterscheiden, weil das zufällig erzeugte Zahlen sind!!