Selectionsort - Versionsgeschichte

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Selection-sort nach Selectionsort

2026-04-28T08:51:59Z

Flbkwikiadmin verschob die Seite Selection-sort nach Selectionsort

← Nächstältere Version		Version vom 28. April 2026, 10:51 Uhr
(kein Unterschied)

Flbkwikiadmin am 28. April 2026 um 08:49 Uhr

2026-04-28T08:49:46Z

← Nächstältere Version		Version vom 28. April 2026, 10:49 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== Einführung ==
	Ein einfacher [[Sortieren\|Sortieralgorithmus]] ist der Selection Sort. Dieser Algorithmus sucht zunächst das kleinste Element in der Liste, merkt es sich und tauscht es mit dem Element am Anfang aus, sodass sich das kleinste Element an ~~erster~~ Stelle befindet. Anschließend wird das zweitkleinste Element gesucht und mit dem Element an ~~zweiter~~ Stelle vertauscht ~~usw~~. Auf diese Weise erhalten die Elemente auf der linken Seite der aktuellen Position schrittweise ihren festen Platz und werden nicht mehr verändert.		Ein einfacher [[Sortieren\|Sortieralgorithmus]] ist der Selection Sort (Sortieren durch Auswählen). Dieser Algorithmus sucht zunächst das kleinste Element in der Liste, merkt es sich und tauscht es mit dem Element am Anfang aus, sodass sich das kleinste Element an der ersten Stelle befindet.

			Anschließend wird das zweitkleinste Element im verbleibenden, noch unsortierten Teil der Liste gesucht und mit dem Element an der zweiten Stelle vertauscht, und so weiter. Auf diese Weise erhalten die Elemente auf der linken Seite der aktuellen Position schrittweise ihren festen Platz und werden nicht mehr verändert.

	== Beispiel ==		== Beispiel ==
	[[Datei:Array Selectionsort.gif\|mini]]		[[Datei:Array Selectionsort.gif\|mini]]
	Es soll eine Liste mit dem Inhalt [4\|3\|1\|5\|2] sortiert werden.		Es soll eine Liste mit dem Inhalt <code>[4, 3, 1, 5, 2]</code> sortiert werden.

	Im ersten Durchlauf wird die komplette Liste durchsucht, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel ist das der Wert 1. Der ursprüngliche Wert der Startposition (hier 4) wird mit dem Wert an der Position des kleinsten Elements (hier 1 an Index 2) vertauscht.		Im ersten Durchlauf wird die komplette Liste durchsucht, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel ist das der Wert 1. Der ursprüngliche Wert der Startposition (hier die 4) wird mit dem Wert an der Position des kleinsten Elements (hier die 1 am Index 2) vertauscht.

	[[Datei:Animation Selectionsort.gif\|mini]]		[[Datei:Animation Selectionsort.gif\|mini]]
	Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun bei Index 1. An Index 0 befindet sich bereits das kleinste Element, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht~~. Das kleinste Element befindet sich hier am Ende der Liste~~. Es wird die 2 als kleinstes Element ausgewählt und mit der neuen Startposition vertauscht.		Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun bei Index 1. An Index 0 befindet sich bereits das kleinste Element der gesamten Liste, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht. Es wird die 2 als kleinstes Element ausgewählt und mit der neuen Startposition vertauscht.

	Die Suche wiederholt sich nach diesem Prinzip, bis alle Elemente sortiert sind. Der Suchbereich verkleinert sich Schritt für Schritt. Die folgende Animation visualisiert den Algorithmus.		Die Suche wiederholt sich nach diesem Prinzip, bis alle Elemente sortiert sind. Der Suchbereich verkleinert sich dabei Schritt für Schritt um ein Element. Die folgende Animation visualisiert den Algorithmus.

	== Pseudocode ==		== Pseudocode ==
	Der Algorithmus sieht im Pseudocode so aus:		Der [[Algorithmus]] sieht im Pseudocode so aus:

	<syntaxhighlight lang="text">		<syntaxhighlight lang="text">
Zeile 63:		Zeile 65:

	== Komplexität ==		== Komplexität ==
	Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des [[~~Algorithmus~~]] ~~SelectionSort~~.		Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des Algorithmus Selection Sort.

			Ein besonderes Merkmal dieses Algorithmus ist, dass seine Laufzeit unabhängig von der anfänglichen Sortierung der Elemente ist. Um eine Datenstruktur (z. B. ein [[Array]]) mit <math>n</math> Einträgen zu sortieren, muss <math>n - 1</math> Mal das Minimum durch Vergleichen bestimmt werden.

			Bei der ersten Bestimmung des Minimums sind <math>n - 1</math> Vergleiche notwendig, bei der zweiten <math>n - 2</math> Vergleiche, und so weiter bis zum letzten Durchlauf mit exakt 1 Vergleich. Mit der [[Arithmetische-reihe\|gaußschen Summenformel]] erhält man die Gesamtanzahl der immer notwendigen Vergleiche:

			<math>(n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n</math>

	~~Um eine Datenstruktur (z~~. B. ein ~~[[Array]]~~) ~~mit~~ n ~~Einträgen mittels SelectionSort zu sortieren, muss n−1~~-~~mal das Minimum durch Vergleichen bestimmt werden~~. ~~Bei der ersten Bestimmung des Minimums sind n−1~~ Vergleiche ~~notwendig~~, bei ~~der zweiten n−2 Vergleiche usw~~. ~~Mit der [[Arithmetische-reihe\|gaußschen Summenformel]] erhält man die Gesamtanzahl der notwendigen Vergleiche:~~		=== Best Case ===
			Das Best-Case-Szenario tritt ein, wenn das Array bereits vollständig aufsteigend sortiert ist.
			Auch wenn alle Elemente bereits am richtigen Platz stehen, "weiß" der Selection Sort dies nicht. Er muss trotzdem in jedem Durchlauf den kompletten unsortierten Rest der Liste überprüfen, um sicherzustellen, dass nicht doch ein noch kleineres Element existiert. Es finden zwar keine Vertauschungen (Swaps) statt, die Anzahl der Vergleiche bleibt jedoch bei <math>\frac{n(n - 1)}{2}</math>. Da die Vergleiche asymptotisch dominieren, liegt die Zeitkomplexität im Best Case bei <math>\mathcal{O}(n^2)</math>.

	(n − 1~~) +~~ (n − 2) ~~+ … + 1 = n(n − 1)~~ / 2		=== Average Case ===
			Im durchschnittlichen Fall (Average Case) liegt eine zufällig durchmischte Liste vor.
			Genau wie im Best Case muss der Selection Sort die gesamte arithmetische Reihe an Vergleichen durchführen, um das Minimum in jedem Schritt zu finden. Die Anzahl der durchgeführten Vertauschungen liegt im Schnitt zwischen 0 und <math>n - 1</math>. Auch hier ändert dies nichts an der dominanten quadratischen Anzahl der Vergleiche. Die Zeitkomplexität im Average Case ist somit ebenfalls <math>\mathcal{O}(n^2)</math>.

	~~SelectionSort~~ liegt ~~somit~~ in der Komplexitätsklasse <math>O(n^2)</math>.		=== Worst Case ===
			Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist.
			Der Algorithmus führt wieder exakt <math>\frac{n(n - 1)}{2}</math> Vergleiche aus. In diesem Fall muss bei fast jedem Durchlauf (maximal <math>n - 1</math> Mal) das kleinste Element mit dem aktuellen Start-Element vertauscht werden. Da die maximale Anzahl der Vertauschungen linear (<math>\mathcal{O}(n)</math>) wächst, die Anzahl der Vergleiche jedoch quadratisch, bestimmt der quadratische Term das Laufzeitverhalten. Die Komplexitätsklasse im Worst Case liegt demnach bei <math>\mathcal{O}(n^2)</math>.

	[[Kategorie:Programmierung]]		[[Kategorie:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_TP2]]		[[Kategorie:FI_I_TP2]]

Flbkwikiadmin am 2. März 2026 um 11:28 Uhr

2026-03-02T11:28:47Z

← Nächstältere Version		Version vom 2. März 2026, 13:28 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== Einführung ==
	Ein ~~simpler~~ [[Sortieren\|~~Sortier~~]]~~algorithmus~~ ist der Selection Sort. Dieser Algorithmus sucht ~~sich als erstes~~ das kleinste Element in der Liste, merkt es sich und tauscht es ~~gegen das~~ Element am Anfang aus, sodass sich ~~dann~~ das kleinste Element ~~ganz am Anfang~~ befindet. ~~Als Nächstes~~ wird das zweitkleinste Element ~~in der Liste~~ gesucht und ~~wird gegen das~~ an zweiter Stelle ~~platzierte Element der Liste ausgetauscht~~ usw. Auf diese Weise ~~haben immer~~ die Elemente auf der linken Seite der aktuellen Position ~~einen~~ festen Platz und werden nicht mehr ~~geändert~~.		Ein einfacher [[Sortieren\|Sortieralgorithmus]] ist der Selection Sort. Dieser Algorithmus sucht zunächst das kleinste Element in der Liste, merkt es sich und tauscht es mit dem Element am Anfang aus, sodass sich das kleinste Element an erster Stelle befindet. Anschließend wird das zweitkleinste Element gesucht und mit dem Element an zweiter Stelle vertauscht usw. Auf diese Weise erhalten die Elemente auf der linken Seite der aktuellen Position schrittweise ihren festen Platz und werden nicht mehr verändert.

	== Beispiel ==		== Beispiel ==
	[[Datei:Array Selectionsort.gif\|mini]]		[[Datei:Array Selectionsort.gif\|mini]]
	Es soll eine Liste mit dem Inhalt [4\|3\|1\|5\|2] sortiert werden.		Es soll eine Liste mit dem Inhalt [4\|3\|1\|5\|2] sortiert werden.
	Im ersten Durchlauf wird die komplette Liste ~~durchlaufen~~, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel der Wert 1. Der ursprüngliche Wert der Startposition (hier 4) wird mit dem Wert der ~~Stelle~~ des kleinsten ~~Wertes~~ (hier ~~Wert~~ 1 im Index 2) ~~getauscht~~.
			Im ersten Durchlauf wird die komplette Liste durchsucht, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel ist das der Wert 1. Der ursprüngliche Wert der Startposition (hier 4) wird mit dem Wert an der Position des kleinsten Elements (hier 1 an Index 2) vertauscht.

	[[Datei:Animation Selectionsort.gif\|mini]]		[[Datei:Animation Selectionsort.gif\|mini]]
	Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun im Index 1. Im Index 0 befindet sich bereits das kleinste Element, daher ist ~~eine~~ Suche ~~an der ersten Stelle nicht~~ mehr erforderlich. Der ~~Rest~~ der Liste wird ~~durchlaufen~~. Das kleinste Element befindet sich hier ~~zufällig~~ am Ende der Liste. Es wird die 2 als kleinstes Element ausgewählt und ~~die Werte werden~~ mit der neuen Startposition ~~getauscht~~.		Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun bei Index 1. An Index 0 befindet sich bereits das kleinste Element, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht. Das kleinste Element befindet sich hier am Ende der Liste. Es wird die 2 als kleinstes Element ausgewählt und mit der neuen Startposition vertauscht.

	Die Suche wiederholt sich nach ~~dieser Logik~~ bis alle Elemente sortiert ~~wurden~~. Der Suchbereich ~~sinkt~~ Schritt für Schritt. ~~Folgende~~ Animation visualisiert den Algorithmus.		Die Suche wiederholt sich nach diesem Prinzip, bis alle Elemente sortiert sind. Der Suchbereich verkleinert sich Schritt für Schritt. Die folgende Animation visualisiert den Algorithmus.

	== ~~Pseudo Code~~ ==		== Pseudocode ==
	Der Algorithmus sieht im Pseudocode so aus:		Der Algorithmus sieht im Pseudocode so aus:
	<syntaxhighlight>
	prozedur ~~SelectionSort~~( A : Liste sortierbarer Elemente)		<syntaxhighlight lang="text">
	~~hoechsterIndex~~ = ~~Elementanzahl(~~ A ~~) - 1~~		prozedur selectionSort(A ist Liste sortierbarer Elemente)
	einfuegeIndex = 0		n = Länge von A
	wiederhole		für einfuegeIndex von 0 bis n - 2 wiederhole
	minPosition = einfuegeIndex		minPosition = einfuegeIndex
	für ~~jeden~~ idx von (einfuegeIndex + 1) bis ~~hoechsterIndex~~ wiederhole		für idx von einfuegeIndex + 1 bis n - 1 wiederhole
	falls A[ idx ] < A[ minPosition ] dann		falls A[idx] < A[minPosition] dann
	minPosition = idx		minPosition = idx
	ende falls		ende falls
			ende für
			falls minPosition ≠ einfuegeIndex dann
			vertausche A[minPosition] und A[einfuegeIndex]
			ende falls
	ende für		ende für
	~~vertausche A[ minPosition ] und A[ einfuegeIndex ]~~		ende prozedur
	~~einfuegeIndex~~ = ~~einfuegeIndex + 1~~		</syntaxhighlight>
	~~solange einfuegeIndex~~ < ~~hoechsterIndex~~
	~~prozedur ende~~		== Java-Implementierung ==
	<~~/syntaxhighlight~~>		<syntaxhighlight lang="java">
			public ArrayList<Mitarbeiter> sortierenNachNachnamen() {
			ArrayList<Mitarbeiter> sortierteListe = new ArrayList<>(mitarbeiterListe);
			int stelle = 0;

	~~== Java Implementierung ==~~		while (stelle < sortierteListe.size() - 1) {
	~~<syntaxhighlight lang="java">~~		int kleinstesElement = stelle;
	~~public ArrayList<Mitarbeiter> sortierenNachNachnamen(){~~
	~~ArrayList<Mitarbeiter> sortierteListe = mitarbeiterListe;~~
	~~int stelle = 0;~~
	while(stelle < sortierteListe.size()){
	int kleinstesElement = stelle;
	~~for(int index = stelle+1; index < sortierteListe.size(); index++){~~

	if(sortierteListe.get(index).getNachname().compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0){		for (int index = stelle + 1; index < sortierteListe.size(); index++) {
	kleinstesElement = index;		if (sortierteListe.get(index).getNachname()
	}		.compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0) {
			kleinstesElement = index;
	}		}
			}

			if (kleinstesElement != stelle) {
	Mitarbeiter puffer = sortierteListe.get(kleinstesElement);		Mitarbeiter puffer = sortierteListe.get(kleinstesElement);
	sortierteListe.set(kleinstesElement,sortierteListe.get(stelle)) ;		sortierteListe.set(kleinstesElement, sortierteListe.get(stelle));
	sortierteListe.set(stelle,puffer);		sortierteListe.set(stelle, puffer);
	~~stelle++~~;
	}		}
	return sortierteListe;
			stelle++;
			}

			return sortierteListe;
	}		}
	</syntaxhighlight>		</syntaxhighlight>

	== Komplexität ==		== Komplexität ==
	Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des [[Algorithmus]] SelectionSort.		Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des [[Algorithmus]] SelectionSort.

	Um eine Datenstruktur (z.B. ~~eine~~ [[Array]]) mit Einträgen mittels SelectionSort zu sortieren, muss n-1 mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind ~~n-1~~ Vergleiche notwendig, bei der zweiten ~~n-2~~ Vergleiche usw. Mit der [[Arithmetische-reihe\|gaußschen Summenformel]] erhält man die ~~Anzahl~~ der notwendigen Vergleiche. SelectionSort liegt somit in der Komplexitätsklasse <math>O(n^2) </math>.		Um eine Datenstruktur (z. B. ein [[Array]]) mit n Einträgen mittels SelectionSort zu sortieren, muss n−1-mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind n−1 Vergleiche notwendig, bei der zweiten n−2 Vergleiche usw. Mit der [[Arithmetische-reihe\|gaußschen Summenformel]] erhält man die Gesamtanzahl der notwendigen Vergleiche:

			(n − 1) + (n − 2) + … + 1 = n(n − 1) / 2

			SelectionSort liegt somit in der Komplexitätsklasse <math>O(n^2)</math>.

	[[Kategorie:Programmierung]]		[[Kategorie:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_TP2]]		[[Kategorie:FI_I_TP2]]

Thomas: /* Komplexität */

2026-02-20T11:00:05Z

Komplexität

← Nächstältere Version		Version vom 20. Februar 2026, 13:00 Uhr
Zeile 56:		Zeile 56:

	Um eine Datenstruktur (z.B. eine [[Array]]) mit Einträgen mittels SelectionSort zu sortieren, muss n-1 mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind n-1 Vergleiche notwendig, bei der zweiten n-2 Vergleiche usw. Mit der [[Arithmetische-reihe\|gaußschen Summenformel]] erhält man die Anzahl der notwendigen Vergleiche. SelectionSort liegt somit in der Komplexitätsklasse <math>O(n^2) </math>.		Um eine Datenstruktur (z.B. eine [[Array]]) mit Einträgen mittels SelectionSort zu sortieren, muss n-1 mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind n-1 Vergleiche notwendig, bei der zweiten n-2 Vergleiche usw. Mit der [[Arithmetische-reihe\|gaußschen Summenformel]] erhält man die Anzahl der notwendigen Vergleiche. SelectionSort liegt somit in der Komplexitätsklasse <math>O(n^2) </math>.
			[[Kategorie:Programmierung]]
			[[Kategorie:AHR_I_Informatik_LK]]
			[[Kategorie:FI_I_TP2]]

Thomas: /* Einführung */

2026-02-20T10:55:55Z

Einführung

← Nächstältere Version		Version vom 20. Februar 2026, 12:55 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== Einführung ==
	Ein simpler ~~Sortieralgorithmus~~ ist der Selection Sort. Dieser Algorithmus sucht sich als erstes das kleinste Element in der Liste, merkt es sich und tauscht es gegen das Element am Anfang aus, sodass sich dann das kleinste Element ganz am Anfang befindet. Als Nächstes wird das zweitkleinste Element in der Liste gesucht und wird gegen das an zweiter Stelle platzierte Element der Liste ausgetauscht usw. Auf diese Weise haben immer die Elemente auf der linken Seite der aktuellen Position einen festen Platz und werden nicht mehr geändert.		Ein simpler [[Sortieren\|Sortier]]algorithmus ist der Selection Sort. Dieser Algorithmus sucht sich als erstes das kleinste Element in der Liste, merkt es sich und tauscht es gegen das Element am Anfang aus, sodass sich dann das kleinste Element ganz am Anfang befindet. Als Nächstes wird das zweitkleinste Element in der Liste gesucht und wird gegen das an zweiter Stelle platzierte Element der Liste ausgetauscht usw. Auf diese Weise haben immer die Elemente auf der linken Seite der aktuellen Position einen festen Platz und werden nicht mehr geändert.

	== Beispiel ==		== Beispiel ==

Thomas: Die Seite wurde neu angelegt: „== Einführung == Ein simpler Sortieralgorithmus ist der Selection Sort. Dieser Algorithmus sucht sich als erstes das kleinste Element in der Liste, merkt es sich und tauscht es gegen das Element am Anfang aus, sodass sich dann das kleinste Element ganz am Anfang befindet. Als Nächstes wird das zweitkleinste Element in der Liste gesucht und wird gegen das an zweiter Stelle platzierte Element der Liste ausgetauscht usw. Auf diese Weise haben immer die Ele…“

2026-02-20T10:55:29Z

Die Seite wurde neu angelegt: „== Einführung == Ein simpler Sortieralgorithmus ist der Selection Sort. Dieser Algorithmus sucht sich als erstes das kleinste Element in der Liste, merkt es sich und tauscht es gegen das Element am Anfang aus, sodass sich dann das kleinste Element ganz am Anfang befindet. Als Nächstes wird das zweitkleinste Element in der Liste gesucht und wird gegen das an zweiter Stelle platzierte Element der Liste ausgetauscht usw. Auf diese Weise haben immer die Ele…“

Neue Seite

== Einführung ==
Ein simpler Sortieralgorithmus ist der Selection Sort. Dieser Algorithmus sucht sich als erstes das kleinste Element in der Liste, merkt es sich und tauscht es gegen das Element am Anfang aus, sodass sich dann das kleinste Element ganz am Anfang befindet. Als Nächstes wird das zweitkleinste Element in der Liste gesucht und wird gegen das an zweiter Stelle platzierte Element der Liste ausgetauscht usw. Auf diese Weise haben immer die Elemente auf der linken Seite der aktuellen Position einen festen Platz und werden nicht mehr geändert.

== Beispiel ==
[[Datei:Array Selectionsort.gif|mini]]
Es soll eine Liste mit dem Inhalt [4|3|1|5|2] sortiert werden.
Im ersten Durchlauf wird die komplette Liste durchlaufen, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel der Wert 1. Der ursprüngliche Wert der Startposition (hier 4) wird mit dem Wert der Stelle des kleinsten Wertes (hier Wert 1 im Index 2) getauscht.

[[Datei:Animation Selectionsort.gif|mini]]
Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun im Index 1. Im Index 0 befindet sich bereits das kleinste Element, daher ist eine Suche an der ersten Stelle nicht mehr erforderlich. Der Rest der Liste wird durchlaufen. Das kleinste Element befindet sich hier zufällig am Ende der Liste. Es wird die 2 als kleinstes Element ausgewählt und die Werte werden mit der neuen Startposition getauscht.

Die Suche wiederholt sich nach dieser Logik bis alle Elemente sortiert wurden. Der Suchbereich sinkt Schritt für Schritt. Folgende Animation visualisiert den Algorithmus.

== Pseudo Code ==
Der Algorithmus sieht im Pseudocode so aus:
<syntaxhighlight>
prozedur SelectionSort( A : Liste sortierbarer Elemente)
hoechsterIndex = Elementanzahl( A ) - 1
einfuegeIndex = 0
wiederhole
minPosition = einfuegeIndex
für jeden idx von (einfuegeIndex + 1) bis hoechsterIndex wiederhole
falls A[ idx ] < A[ minPosition ] dann
minPosition = idx
ende falls
ende für
vertausche A[ minPosition ] und A[ einfuegeIndex ]
einfuegeIndex = einfuegeIndex + 1
solange einfuegeIndex < hoechsterIndex
prozedur ende
</syntaxhighlight>

== Java Implementierung ==
<syntaxhighlight lang="java">
public ArrayList<Mitarbeiter> sortierenNachNachnamen(){
ArrayList<Mitarbeiter> sortierteListe = mitarbeiterListe;
int stelle = 0;
while(stelle < sortierteListe.size()){
int kleinstesElement = stelle;
for(int index = stelle+1; index < sortierteListe.size(); index++){

if(sortierteListe.get(index).getNachname().compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0){
kleinstesElement = index;
}
}
Mitarbeiter puffer = sortierteListe.get(kleinstesElement);
sortierteListe.set(kleinstesElement,sortierteListe.get(stelle)) ;
sortierteListe.set(stelle,puffer);
stelle++;
}
return sortierteListe;
}
</syntaxhighlight>
== Komplexität ==
Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des [[Algorithmus]] SelectionSort.

Um eine Datenstruktur (z.B. eine [[Array]]) mit Einträgen mittels SelectionSort zu sortieren, muss n-1 mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind n-1 Vergleiche notwendig, bei der zweiten n-2 Vergleiche usw. Mit der [[Arithmetische-reihe|gaußschen Summenformel]] erhält man die Anzahl der notwendigen Vergleiche. SelectionSort liegt somit in der Komplexitätsklasse <math>O(n^2) </math>.