Selectionsort in Java

Funktionsweise von Selectionsort samt Beispielcode

Navigation:

Selectionsort ist ein Sortieralgorithmus den man natürlich auch in Java implementieren kann. Der Selectionsort-Algorithmus ist auch unter den Bezeichnungen MinSort (von Minimum) bzw. MaxSort (von Maximum), Selectsort oder ExchangeSort (AustauschSort) bekannt. Was hinter dem Selectionsort-Algorithmus sich versteckt, wie er funktioniert, wo man ihn einsetzt und was es sonst noch zu Wissen gibt, erfährt man nun nachfolgend. Am Ende findet man eine Java-Implementierung, also den Java-Quellcode von Selectionsort.

Funktionsweise von Selectionsort

Die Funktionsweise von Selectionsort stellt sich so dar: Man hat ein Array in dem sich die zu sortierenden Daten befinden. Nun teilt man das Array im Geiste in zwei Teile. Der erste Teil soll den sortierten Teil darstellen, der zweite Teil den unsortierten. Da am Anfang noch nichts sortiert ist, stellt dementsprechend das gesamte Array den unsortierten Teil dar.

Nun sucht man das kleinste Element im Array und vertauscht es mit dem ersten Element. Nun befindet sich also das erste Element im sortierten Bereich und die restlichen Elemente im unsortierten. Nun wird wieder im unsortierten Teil nach dem kleinsten Element gesucht und dieses nun hinter dem ersten Element im sortierten Bereich eingefügt. Dies geht so lange, bis alle Elemente im sortierten Bereich und keins mehr im unsortierten Bereich sich befindet. Wer nach der Größe sortieren will, angefangen mit dem größten Element, sucht statt dem kleinsten, immer nach dem größten Element.

Selectionsort Beispiel Quellcode

Hier eine Beispiel-Implementierung des Selectionsort-Algorithmus ausgelagert in einer Funktion, samt einer Testausgabe.

public static void main(String[] args) {

		int[] unsortiert = { 4, 1, 8, -3, 5, 7 };
		int[] sortiert = selectionsort(unsortiert);

		for (int i = 0; i < sortiert.length; i++) {
			System.out.print(sortiert[i] + ", ");
		}

	}

	public static int[] selectionsort(int[] sortieren) {
		for (int i = 0; i < sortieren.length - 1; i++) {
			for (int j = i + 1; j < sortieren.length; j++) {
				if (sortieren[i] > sortieren[j]) {
					int temp = sortieren[i];
					sortieren[i] = sortieren[j];
					sortieren[j] = temp;
				}
			}
		}

		return sortieren;
	}

Eine Optimierung des Selectionsort-Algorithmus stellt die gleichzeitige Suche nach dem größten und dem kleinsten Element in einem Durchlauf dar. In diesem Fall wird das kleinste Element am Anfang des Arrays verschoben, während das größte auf den letzten Platz getauscht wird. So erhält man in der Regel eine Beschleunigung um den Faktor 2.