FLBK-Wiki - Benutzerbeiträge [de]

Blackboxtest

2026-02-20T11:35:27Z

Thomas: /* Einführung */

== Einführung ==
[[Datei:Übersicht Testverfahren.jpg|mini]]
Blackboxtests gehören zur Kategorie der dynamischen Testverfahren. Das Ziel des Blackboxtests ist es, die Übereinstimmung eines Softwaresystems mit seinen in der Analysephase eines Softwareentwicklungsprozesses spezifizierten Anforderungen zu überprüfen. Ausgehend von formalen oder informalen Spezifikationen werden Testfälle erarbeitet, die sicherstellen, dass der geforderte Funktionsumfang eingehalten wird. Vor diesem Hintergrund wird die Notwendigkeit, Anforderungen sorgfältig und formal zu beschreiben, besonders deutlich.

Dieser Test wird ohne die Kenntnisse über die innere Funktionsweise des zu testenden Systems durchgeführt. Das Innenleben des zu testenden System bleibt im Dunkeln wie in einer schwarzen Kiste. Der Fokus liegt auf dem funktionsorientierten Testen, d. h. für die Ermittlung der Testfälle werden nur die Anforderungen, aber nicht die Implementierung des Testobjekts herangezogen. Nur nach außen sichtbares Verhalten wird im Balckboxtest berücksichtigt. Die Blackbox-Testverfahren gehen davon aus, daß die Implementierung einer Funktionalität unbedeutend ist. Statt dessen wird überprüft, ob die in der Spezifikation verlangte Funktionalität erfüllt ist. Es handelt sich also um ein Testen auf höherer Ebene, von einzelnen [[Klasse|Klassen]] (Komponententest) über das Zusammenspiel von Klassen (Integrationstest) bis zum Testen des Gesamt-Systems.

Dieser Ansatz ist sehr gut vereinbar mit der [[Objektorientierung|objektorientierten]] Programmierung wie z.B. [[Java]], da auch hier das Bilden von logischen Modulen, [[Klasse|Klassen]] und [[Objekt|Objekten]], im Vordergrund steht. Die innere Realisierung der Funktionalität ist dabei für den Anwender des Systems oder sogar für den Entwickler, welcher diese Klassen weiter verwendet, unbekannt. Blackboxtests eignen sich sehr gut für automatisiertes Testen.

Wurde das Fehlverhalten einer Komponente ermittelt, kann es mit [[Whiteboxtest|Whiteboxtests]] oder statischen Testverfahren, wie z.B. [[Schreibtischtest|Schreibtischtests]], tiefer analysiert werden.

Whiteboxtest

2026-02-20T11:32:27Z

Thomas: /* Einführung */

== Einführung ==
[[Datei:Übersicht Testverfahren.jpg|mini]]
White-Box-Test bezeichnet eine dynamische Methode des Software-Tests, bei der die Tests mit Einblick in die innere Funktionsweise des zu testenden Systems entwickelt werden. Im Gegensatz zum [[Blackboxtest|Black-Box-Test]] ist für diesen Test also ein Blick in den [[Quelltext|Quellcode]] gestattet, d. h. es wird am Code geprüft.

White-Box-Tests werden eingesetzt, um Fehler in den Teilkomponenten aufzudecken und zu lokalisieren, sind aber kein geeignetes Mittel, Fehler gegenüber der [[Softwareentwicklungsprozess|Anforderungsspezifikation]] aufzudecken. Für letzteres benötigt man [[Blackboxtest|Black-Box-Tests]]. Zu bedenken ist auch, dass zwei Komponenten, die für sich genommen korrekt gemäß ihrer jeweiligen Teilspezifikation arbeiten, zusammen nicht zwangsläufig eine korrekte Einheit gemäß der Gesamtspezifikation bilden. Dies kann durch Black-Box-Tests leichter festgestellt werden als durch White-Box-Tests.

Whiteboxtest

2026-02-20T11:31:57Z

Thomas: /* Einführung */

== Einführung ==
[[Datei:Übersicht Testverfahren.jpg|mini]]
White-Box-Test bezeichnet eine dynamische Methode des Software-Tests, bei der die Tests mit Einblick in die innere Funktionsweise des zu testenden Systems entwickelt werden. Im Gegensatz zum [[Blackboxtest|Black-Box-Test]] ist für diesen Test also ein Blick in den [[Quelltext|Quellcode]] gestattet, d. h. es wird am Code geprüft.

White-Box-Tests werden eingesetzt, um Fehler in den Teilkomponenten aufzudecken und zu lokalisieren, sind aber kein geeignetes Mittel, Fehler gegenüber der Anforderungsspezifikation aufzudecken. Für letzteres benötigt man [[Blackboxtest|Black-Box-Tests]]. Zu bedenken ist auch, dass zwei Komponenten, die für sich genommen korrekt gemäß ihrer jeweiligen Teilspezifikation arbeiten, zusammen nicht zwangsläufig eine korrekte Einheit gemäß der Gesamtspezifikation bilden. Dies kann durch Black-Box-Tests leichter festgestellt werden als durch White-Box-Tests.

Whiteboxtest

2026-02-20T11:31:37Z

Thomas: Die Seite wurde neu angelegt: „== Einführung == White-Box-Test bezeichnet eine dynamische Methode des Software-Tests, bei der die Tests mit Einblick in die innere Funktionsweise des zu testenden Systems entwickelt werden. Im Gegensatz zum Black-Box-Test ist für diesen Test also ein Blick in den Quellcode gestattet, d. h. es wird am Code geprüft. White-Box-Tests werden eingesetzt, um Fehler in den Teilkomponenten aufzudecken und zu lokalisieren, sind a…“

== Einführung ==
White-Box-Test bezeichnet eine dynamische Methode des Software-Tests, bei der die Tests mit Einblick in die innere Funktionsweise des zu testenden Systems entwickelt werden. Im Gegensatz zum [[Blackboxtest|Black-Box-Test]] ist für diesen Test also ein Blick in den [[Quelltext|Quellcode]] gestattet, d. h. es wird am Code geprüft.

White-Box-Tests werden eingesetzt, um Fehler in den Teilkomponenten aufzudecken und zu lokalisieren, sind aber kein geeignetes Mittel, Fehler gegenüber der Anforderungsspezifikation aufzudecken. Für letzteres benötigt man [[Blackboxtest|Black-Box-Tests]]. Zu bedenken ist auch, dass zwei Komponenten, die für sich genommen korrekt gemäß ihrer jeweiligen Teilspezifikation arbeiten, zusammen nicht zwangsläufig eine korrekte Einheit gemäß der Gesamtspezifikation bilden. Dies kann durch Black-Box-Tests leichter festgestellt werden als durch White-Box-Tests.

Unit-test

2026-02-20T11:29:20Z

Thomas: /* Einführung */

== Einführung ==
Unit-Tests sind eine Art von Software-Tests, bei denen einzelne, isolierte Teile eines Programms (Units) auf ihre korrekte Funktionalität überprüft werden. Diese Units sind in der Regel kleine, wiederverwendbare Code-Abschnitte wie Methoden oder Funktionen.

Obwohl der Entwickler den Code kennt, schreibt man idealerweise Unit-Tests nach dem [[Blackboxtest|Blackbox]]-Prinzip. Man definiert Eingabewerte und erwartet ein bestimmtes Ergebnis, ohne sich darauf zu verlassen, wie die Logik intern implementiert ist.

=== Ziel von Unit-Tests: ===

* Fehler frühzeitig erkennen: Durch das Testen einzelner Komponenten können Fehler bereits in der Entwicklungsphase identifiziert und behoben werden.
* Codequalität verbessern: Unit-Tests fördern sauberen, gut strukturierten und wartbaren Code.
* Regressionen verhindern: Wenn neue Funktionen hinzugefügt oder bestehender Code geändert wird, können Unit-Tests sicherstellen, dass bereits vorhandene Funktionalität nicht beeinträchtigt wird.
* Dokumentation: Gut geschriebene Unit-Tests dienen als lebendige Dokumentation des Codes und machen sein Verhalten verständlicher.

=== Werkzeuge für Unit-Tests ===
* JUnit: Das am weitesten verbreitete Java-Framework für Unit-Tests.
* NUnit: Für .NET-Anwendungen.
* pytest: Für Python.
* Jest: Für JavaScript.

== Beispiel (Java mit JUnit) ==
<syntaxhighlight lang="java">
// Klasse zu testende Klasse
public class Calculator {
public int add(int a, int b) {
return a + b;
}
}
// JUnit Test
import static org.junit.jupiter.api.Assertions.assertEquals;
import org.junit.jupiter.api.Test;
public class CalculatorTest {
@Test
public void testAdd() {
Calculator calculator = new Calculator();
int result = calculator.add(2, 3);
assertEquals(5, result);
}
}
</syntaxhighlight>
In diesem Beispiel wird die add-[[Methode]] der Calculator-[[Klasse]] getestet. Der Test erwartet, dass die Summe von 2 und 3 gleich 5 ist.

Blackboxtest

2026-02-20T11:29:08Z

Thomas: Die Seite wurde neu angelegt: „== Einführung == mini Blackboxtests gehören zur Kategorie der dynamischen Testverfahren. Das Ziel des Blackboxtests ist es, die Übereinstimmung eines Softwaresystems mit seinen in der Analysephase eines Softwareentwicklungsprozesses spezifizierten Anforderungen zu überprüfen. Ausgehend von formalen oder informalen Spezifikationen werden Testfälle erarbeitet, die sicherstellen, dass der geforderte Funktionsumfan…“

== Einführung ==
[[Datei:Übersicht Testverfahren.jpg|mini]]
Blackboxtests gehören zur Kategorie der dynamischen Testverfahren. Das Ziel des Blackboxtests ist es, die Übereinstimmung eines Softwaresystems mit seinen in der Analysephase eines Softwareentwicklungsprozesses spezifizierten Anforderungen zu überprüfen. Ausgehend von formalen oder informalen Spezifikationen werden Testfälle erarbeitet, die sicherstellen, dass der geforderte Funktionsumfang eingehalten wird. Vor diesem Hintergrund wird die Notwendigkeit, Anforderungen sorgfältig und formal zu beschreiben, besonders deutlich.

Dieser Test wird ohne die Kenntnisse über die innere Funktionsweise des zu testenden Systems durchgeführt. Das Innenleben des zu testenden System bleibt im Dunkeln wie in einer schwarzen Kiste. Der Fokus liegt auf dem funktionsorientierten Testen, d. h. für die Ermittlung der Testfälle werden nur die Anforderungen, aber nicht die Implementierung des Testobjekts herangezogen. Nur nach außen sichtbares Verhalten wird im Balckboxtest berücksichtigt. Die Blackbox-Testverfahren gehen davon aus, daß die Implementierung einer Funktionalität unbedeutend ist. Statt dessen wird überprüft, ob die in der Spezifikation verlangte Funktionalität erfüllt ist. Es handelt sich also um ein Testen auf höherer Ebene, von einzelnen [[Klasse|Klassen]] (Komponententest) über das Zusammenspiel von Klassen (Integrationstest) bis zum Testen des Gesamt-Systems.

Dieser Ansatz ist sehr gut vereinbar mit der [[Objektorientierung|objektorientierten]] Programmierung wie z.B. [[Java]], da auch hier das Bilden von logischen Modulen, [[Klasse|Klassen]] und [[Objekt|Objekten]], im Vordergrund steht. Die innere Realisierung der Funktionalität ist dabei für den Anwender des Systems oder sogar für den Entwickler, welcher diese Klassen weiter verwendet, unbekannt. Blackboxtests eignen sich sehr gut für automatisiertes Testen.

Wurde das Fehlverhalten einer Komponente ermittelt, kann es mit Whiteboxtests oder statischen Testverfahren, wie z.B. [[Schreibtischtest|Schreibtischtests]], tiefer analysiert werden.

Unit-test

2026-02-20T11:09:04Z

Thomas: Die Seite wurde neu angelegt: „== Einführung == Unit-Tests sind eine Art von Software-Tests, bei denen einzelne, isolierte Teile eines Programms (Units) auf ihre korrekte Funktionalität überprüft werden. Diese Units sind in der Regel kleine, wiederverwendbare Code-Abschnitte wie Methoden oder Funktionen. === Ziel von Unit-Tests: === * Fehler frühzeitig erkennen: Durch das Testen einzelner Komponenten können Fehler bereits in der Entwicklungsphase identifiziert und behoben werde…“

== Einführung ==
Unit-Tests sind eine Art von Software-Tests, bei denen einzelne, isolierte Teile eines Programms (Units) auf ihre korrekte Funktionalität überprüft werden. Diese Units sind in der Regel kleine, wiederverwendbare Code-Abschnitte wie Methoden oder Funktionen.

=== Ziel von Unit-Tests: ===

* Fehler frühzeitig erkennen: Durch das Testen einzelner Komponenten können Fehler bereits in der Entwicklungsphase identifiziert und behoben werden.
* Codequalität verbessern: Unit-Tests fördern sauberen, gut strukturierten und wartbaren Code.
* Regressionen verhindern: Wenn neue Funktionen hinzugefügt oder bestehender Code geändert wird, können Unit-Tests sicherstellen, dass bereits vorhandene Funktionalität nicht beeinträchtigt wird.
* Dokumentation: Gut geschriebene Unit-Tests dienen als lebendige Dokumentation des Codes und machen sein Verhalten verständlicher.

=== Werkzeuge für Unit-Tests ===
* JUnit: Das am weitesten verbreitete Java-Framework für Unit-Tests.
* NUnit: Für .NET-Anwendungen.
* pytest: Für Python.
* Jest: Für JavaScript.

== Beispiel (Java mit JUnit) ==
<syntaxhighlight lang="java">
// Klasse zu testende Klasse
public class Calculator {
public int add(int a, int b) {
return a + b;
}
}
// JUnit Test
import static org.junit.jupiter.api.Assertions.assertEquals;
import org.junit.jupiter.api.Test;
public class CalculatorTest {
@Test
public void testAdd() {
Calculator calculator = new Calculator();
int result = calculator.add(2, 3);
assertEquals(5, result);
}
}
</syntaxhighlight>
In diesem Beispiel wird die add-[[Methode]] der Calculator-[[Klasse]] getestet. Der Test erwartet, dass die Summe von 2 und 3 gleich 5 ist.

Schreibtischtest

2026-02-20T11:05:10Z

Thomas: /* Einführung */

== Einführung ==
[[Datei:Beispiel Schreibtisschtest.png|mini]]
Der Schreibtischtest ist ein Verfahren, das im Bereich der Softwareentwicklung verwendet wird, um [[Algorithmus|Algorithmen]] oder Routinen auf Richtigkeit zu prüfen. Der Schreibtischtest wird nicht mit Hilfe eines Rechners durchgeführt, sondern vielmehr im Kopf des Entwicklers. Dazu werden für einen deterministischen und terminierenden Programmablauf eine Eingabe- und eine mögliche Ausgabemenge festgelegt. Anschließend wird mit jedem Element der Eingabemenge durch schrittweises Durchrechnen die Korrektheit des Programmablaufs überprüft. Der gewählte Programmablauf verhält sich für das gewählte Eingabeelement genau dann korrekt, wenn das ausgegebene Element, also das Ergebnis, Teil der Ausgabemenge ist. Man könnte es auch als analoges [[Debugger|debugging]] bezeichnen.

Die Tatsache, dass die Eingabemenge für einen Algorithmus beliebig groß sein kann, z. B. eine Untermenge der natürlichen Zahlen, erfordert vom Entwickler zur Überprüfung der Korrektheit des zu testenden Programms die schrittweise Durchrechnung mit allen Elementen der Eingabemenge. Gibt es für die Eingabemenge keine obere oder untere Schranke, dann kann der Schreibtischtest höchstens mit einigen plausiblen Eingaben ein Indiz dafür liefern, dass der Algorithmus richtig implementiert wurde.

Voraussetzungen für den Schreibtischtest sind also ein deterministischer und terminierender Programmablauf, die Kenntnis über plausible und sinnvolle Eingabeelemente, und die Kenntnis der zu den Eingabeelementen passenden Ausgabeelemente, um aus der jeweiligen Ausgabe auf die Richtigkeit schließen zu können. Das Ergebnis für die jeweilige Eingabe muss also bekannt sein.

Selectionsort

2026-02-20T11:00:05Z

Thomas: /* Komplexität */

== 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.

== 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>.
[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Quicksort

2026-02-20T10:59:49Z

Thomas: /* Best Case */

== Einführung ==
[[Datei:Rekursive Baumstruktur.jpg|mini]]
Ein oft eingesetzter [[Sortieren|Sortier]]-Algorithmus ist der Quicksort. Der Quicksort funktioniert nach dem Prinzip »teile und herrsche«, was mit Hilfe der [[Rekursion]] realisiert wird. Die zu sortierenden [[Daten]] werden immer in zwei Teile zerlegt ("Teile") und wieder sortiert ("Herrsche")). Diese zwei Teile werden wiederum jeweils in zwei Teile zerlegt und sortiert usw., bis die Daten sortiert sind. Die [[Rekursion]] beendet sich, wenn das Teilstück aus nur noch einem Element besteht (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm#mj035bded10a26be556df779f234784e89).

Die Zerlegung in zwei Teile erfolgt anhand eines sogenannten Pivot-Elementes. Ein Element der Liste wird als Pivot Element ausgewählt und dann werden alle weiteren Elemente der zu sortierenden Liste mit diesem Element verglichen. Die zu sortierende Liste wird in zwei Bereiche unterteilt. Alle Elemente die kleiner sind als das Pivot-Element werden links von dem Pivot-Element einsortiert. Alle Elemente die größer sind, werden rechts von Pivot-Element abgelegt.

Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich dem Pivot-Element und somit auch kleiner oder gleich den Elementen der rechten Liste. Die Elemente der linken und rechten Liste sind je Liste noch unsortiert.

Anschließend muss man noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort.

Die Teillisten sind immer Abschnitte auf der ursprünglichen Liste, so dass kein zusätzlicher Speicher benötigt wird.

== Beispiel ==
Als Beispiel betrachten wir eine Liste mit Zahlen. Wir wählen immer das erste Element als Pivot-Element. Zu Beginn ist die Zahl 7 zufällig das Pivot-Element.

7 10 8 6 11 4 9 3 1 5 2 12

Die Zahlen, die kleiner als das Pivot-Element 7 sind, wurden blau markiert. Die Zahlen größer 7 haben sind rot markiert. Als ersten Schritt ändert QuickSort die Liste folgendermaßen:

3 2 5 6 1 4 7 9 11 8 10 12

Nun sind alle Zahlen, welche kleiner sind als 7, links von ihr. Alle Zahlen welche größer sind als die 7, stehen rechts. Die Reihenfolge der Zahlen in den Teillisten ist hier willkürlich und hängt ab von der jeweiligen Implementierung. Entscheidend ist, dass alle Zahlen die kleiner sind als 7 links stehen und alle Zahlen die größer sind als 7 rechts.

Als nächstes wird der Teil links von der 7 wieder per QuickSort sortiert. Als Pivot wird die Zahl 3 gewählt. Die Zahlen die kleiner sind als 3 werden wieder blau markiert. Alle Zahlen größer 3 sind rot. Die Zahl 7 und die größeren Zahlen betrachten wir im Moment nicht, deshalb sind sie gelb hinterlegt:

3 2 5 6 1 4 7 9 11 8 10 12

Der Algorithmus bringt die blauen und die roten Zahlen wieder in die richtige Ordnung. Man erhält dann das Folgende:

1 2 3 6 5 4 7 9 11 8 10 12

Das wird fortgesetzt bis der linke Teil des Arrays sortiert ist. Das sieht dann wie folgt aus:

'''''1 2 3 4 5 6''''' 7 9 11 8 10 12

Nun wird rechts von der 7 sortiert. Wieder wird ein Pivot gewählt, hier die 9, und die kleineren und größeren Zahlen auf die jeweils richtige Seite gebracht.

Der grundsätzlichen Algorithmus lässt mit PseudoCode wie folgt beschreiben:

== Pseudocode ==
Der folgende Pseudocode illustriert die Arbeitsweise des [[Algorithmus]]. Bei jedem Aufruf von quicksort(...) gibt links den Index des ersten Elements in der Teilliste an und rechts den des letzten. Beim ersten Aufruf (oberste Rekursionsebene) ist links = 0 und rechts = n-1. Die übergebene Liste wird dabei [[Rekursion|rekursiv]] immer weiter geteilt, bis sie nur noch einen Wert enthält.
<syntaxhighlight>
funktion quicksort(links, rechts)
falls links < rechts dann
teiler := teile(links, rechts)
quicksort(links, teiler - 1)
quicksort(teiler + 1, rechts)
ende
ende
</syntaxhighlight>
== Wahl des Pivot-Elements ==
Die Wahl des Pivotelements ist wichtig. Die schlechteste Wahl des Pivots ist das Element, welches ganz am linken oder ganz am rechten Rand des zu sortierenden Intervalls endet. Mit linkem oder rechten Element ist nicht das Element gemeint, welches sich in der unsortierten Liste ganz Links (im Beispiel die 7) oder rechts befindet, sondern das kleinste (im Beispiel die 1) bzw. das größte Element (im Beispiel die 12). Der QuickSort ist dann am Effizientesten, wenn man ein Pivot-Element wählt, welches am Schluss genau in der Mitte zu liegen kommt (im Beispiel die 6 oder die 7). Leider ist dieses Element nicht ganz einfach zu finden.

Man sollte deshalb nicht immer wie im Beispiel das erste Element als Pivot wählen. Dies ist zwar leicht zu implementieren, allerdings führt dies zu einem langsamen "QuickSort", falls das Array bereits sortiert ist, oder nahezu sortiert ist.

Als Kompromiss wird oft ein zufälliges Element als Pivot-Element genommen. Noch besser kann es sein, von drei zufällig gewählten Elementen jeweils das mittlere zu nehmen.

== Java Implementierung ==
Bisher wurde die allgemeine Funktionsweise des Quicksorts beschrieben. Am Besten lassen sich komplexe [[Algorithmus|Algorithmen]] nachvollziehen, wenn Sie anhand einer Implementierung mit Hilfe eines [[Debugger|Debuggers]] analysiert werden. Mit Hilfe des Quicksorts können beliebige Datenstrukturen sortiert werden. In der folgenden [[Java]] Implementierung wird ein [[Array]] bestehend aus Integern (kurz int) sortiert.
<syntaxhighlight lang="java">
public void quickSort(int array[], int links, int rechts) {
if (links < rechts) {
int i = teile(array,links,rechts);
quickSort(array,links,i-1);
quickSort(array,i+1,rechts);
}
}

public int teile(int array[], int links, int rechts) {
int pivot, i, j, help;
pivot = array[rechts];
i = links;
j = rechts-1;
while(i<=j) {
if (array[i] > pivot) {
// tausche x[i] und x[j]
help = array[i];
array[i] = array[j];
array[j] = help;

j--;
} else i++;
}

// tausche x[i] und x[rechts]
help = array[i];
array[i] = array[rechts];
array[rechts] = help;
return i;
}
</syntaxhighlight>
== Laufzeitanalyse ==
=== Worst-Case ===
[[Datei:Baum N-Ebenen.png|mini]]
Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.

In diesem Szenario benötigt [[Rekursion|rekursive]] Aufruf von n-1 Elementen c* (n - 1) für eine Konstante c. Dies Konstante c repräsentiert die Benötigte Zeit für eine Operation wie einen Aufruf oder einen Vergleich. Für n-2 Elemente werden die Zeit c*(n-2) benötigt und so weiter (siehe Abbildung).

Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe|gauschen Summenformel]]:
<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>
Im Rahmend er [[Laufzeitanalyse]] ignorieren wir Terme niedriger Ordnung und konstante Koeffizienten. In der Big-Θ-Notation folgt hieraus die Worst-Case-Laufzeit von QuickSort <math> O(n^2)</math>.

== Best Case ==
[[Datei:Verzweigungsbaum Quicksort symetrisch.png|mini]]
Der beste Fall von Quicksort liegt vor, wenn die Partitionen so gleichmäßig wie möglich aufgeteilt werden: Ihre Größen sind entweder gleich oder weichen nur um ein Element voneinander ab.

[[Datei:SubArrays symetrisch Quicksort.png|mini]]
Der erstere Fall tritt auf, wenn das Subarray eine ungerade Anzahl von Elementen hat und der Drehpunkt nach der Partitionierung genau in der Mitte liegt und jede Partition <math>(n-1) / 2 </math> hat. Der letztere Fall tritt auf, wenn das Subarray eine gerade Anzahl n von Elementen hat und eine Partition n / 2 hat, während die andere n-1 / 2 hat. In beiden Fällen hat jede Partition höchstens n / 2 Elemente.

Wird die Anzahl der zu sortierenden Elemente n verdoppelt, muss nur eine neue Ebene mit Teilarrays erzeugt werden. Dieses Wachstum lässt sich mit <math>log(n) </math> beschreiben.
{| class="wikitable" style="text-align:center"
|-
! Zu sortierende Elemente n
| style="color:green" | 4
| style="color:green" | 8
| style="color:green" | 16
| style="color:green" | 32
|-
! Zu sortierende Elemente n
| <math>\color{green}{2^2}</math>
| <math>\color{green}{2^3}</math>
| <math>\color{green}{2^4}</math>
| <math>\color{green}{2^5}</math>
|-
! Anzahl Ebene log(n)
| style="color:red" | 2
| style="color:red" | 3
| style="color:red" | 4
| style="color:red" | 5
|}

In jeder Ebene müssen n Elemente sortiert werden. Hieraus ergibt sich eine Laufzeit von <math> O(n * log(n))</math>.
[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Insertionsort

2026-02-20T10:59:10Z

Thomas: /* Komplexität */

Einführung
Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relative simpel. Das Prinzip von Insertion Sort ist: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links weitergereicht – und das so lange, bis das bewegte Element größer oder gleich dem Element ist, das an der im Augenblick abgefragten Position liegt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).

Der Platz für das Element, das verschoben wird, ist frei. Diese Lücke wird mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

== Beispiel ==
[[Datei:Animation Insertio-Sort.gif|mini]]
Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite grün dargestellt befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links gewandert ist. Das aktuell eingefügte Element ist fett markiert. (http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertion.htm).
{| class="wikitable" style="text-align:center; font-family:monospace;"
|-
| ''5'' || 7 || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''5''' || '''7''' || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''''0''''' || 5 || 7 || 3 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || '''''3''''' || 5 || 7 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || 3 || '''''4''''' || 5 || 7 || 2 || 6 || 1 || (2)
|-
| 0 || '''''2''''' || 3 || 4 || 5 || 7 || 6 || 1 || (4)
|-
| 0 || 2 || 3 || 4 || 5 || '''''6''''' || 7 || 1 || (1)
|-
| 0 || '''''1''''' || 2 || 3 || 4 || 5 || 6 || 7 || (6)
|}
== Pseudo Code ==
Der [[Algorithmus]] sieht im Pseudocode so aus:
<syntaxhighlight line>
prozedur INSERTIONSORT(A ist Liste sortierbarer Elemente)
wiederhole bis zur Länge von A und beginne beim 2. Element
einzusortierender_wert = A an der Stelle i
j = i
wiederhole solange j > 1 und A an der Stelle j-1 > einzusortierender_wert
A an der Stelle j = A an der Stelle j-1
j = j − 1
ende wiederhole
A an der Stelle j = einzusortierender_wert
ende wiederhole
ende prozedur
</syntaxhighlight >

== Komplexität ==
=== Worst Case ===
Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

<math>[11,7,5,3,2,0]</math>

Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n.

Beim ersten äußeren Schleifendurchlauf ist c = 1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe oben) der Datenstruktur. Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche , c = 2. Beim dritte Mal, c = 3 bis zum letzten Mal, wenn c = n-1. Es gilt also:

<math>c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))</math>

Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für [[Arithmetische-reihe|arithmetische Reihen]], erhalten wir:

<math>c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2</math>

Für sehr große n können wir den niederwertigen Term <math>cn/2 </math> und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Der InsertionSort liegt hier in der Komplexitätsklasse <math>O(n2)</math>

=== Best Case ===
Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. <math>O(n)</math>). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.

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

Bubblesort

2026-02-20T10:58:34Z

Thomas: /* Pseudo Code */

== Einführung ==
Der Bubble Sort ist ein relativ einfacher [[Sortieren|Sortieralgorithmus]]. In der Bubble-Phase wird die Eingabe-Liste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie getauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.

Die Bubble-Phase wird solange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Liste. Auch werden immer zwei Zahlen miteinander in „Bubbles“ vertauscht.

== Beispiel ==
[[Datei:Animation Bubble Sort.gif|mini]]
Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts. Der zweite Durchlauf braucht somit die letzte und vorletzte Position nicht mehr zu vergleichen. → Dritter Durchlauf: kein Vergleich letzte/vorletzte/vorvorletzte....

'''''55 07''''' 78 12 42 1. Durchlauf

07 '''''55 78''''' 12 42

07 55 '''''78 12''''' 42

07 55 12 '''''78 42''''' Letzter Vergleich

'''''07 55''''' 12 42 78 2. Durchlauf

07 '''''55 12''''' 42 78

07 12 '''''55 42''''' 78 Letzter Vergleich

'''''07 12''''' 42 55 78 3. Durchlauf

07 '''''12 42''''' 55 78 Letzter Vergleich

'''''07 12''''' 42 55 78 4. Durchlauf + Letzter Vergleich

07 12 42 55 78 Fertig sortiert.

== Pseudo Code ==
Der [[Algorithmus]] sieht im Pseudocode so aus:
<syntaxhighlight>
prozedur bubbleSort(A ist Liste sortierbarer Elemente)
n = Länge von A
wiederhole solange n>1
n=n-1
i=0
wiederhole solange i<n-1
i=i+1
falls A an der Stelle i > A an der Stelle i+1 dann
A tausche i und i+1
ende falls
ende wiederhole
ende wiederhole
ende prozedur
</syntaxhighlight>
[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Sortieren

2026-02-20T10:58:14Z

Thomas: /* Übersicht */

== Einführung ==
Ein übliches Problem in der Informatik ist es, Daten zu sortieren. Wer das Sortieren verstanden hat, dem wird es nicht schwerfallen, andere Algorithmen zu verstehen. Das Sortieren könnte man sozusagen auch als »Basics für Algorithmen« bezeichnen.
[[Datei:Sortiertes kartenspiel.png|mini]]

Primär geht es darum, die einzelnen Sortierverfahren näherzubringen, speziell deren Funktionen. Die Implementierung ist zumeist problemabhängig und richtet sich nach der Art der Daten, die es zu sortieren gilt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).Es gibt unterschiedliche Algorithmen für ein gegebenes Problem und so gibt es verschiedene Sortierverfahren. Jeder Algorithmus arbeitet unterschiedlich effizient, um ein Problem zu lösen. Die Zeitkomplexität eines Sortieralgorithmus gibt an, wie viele Operationen nötig sind, um einen Sortiervorgang abzuschließen. Bei gegebenen Hardwareausstattung lässt sich also messen, wie lange ein Sortiervorgang dauert.

== Platzkomplexität – In-place ==
Zusätzlich wird die Platzkomplexität eines Sortierverfahrens betrachtet. Hier wird analysiert, ob und wie viel zusätzlicher Speicher für den Sortiervorgang an sich benötigt wird. Bei in-Place wird nur eine konstante Menge an zusätzlichem Speicher benötigt z.B. Hilfsvariablen für den Dreieckstausch. Bei out-of-place wird eine dynamische Anzahl von zusätzlichem Speicher benötigt die abhängig von der Eingabegröße ist.

== Vergleichsbasierte Verfahren ==
Sortierverfahren können sich allgemein durch die Basis der Arbeitsweise unterscheiden. Zum einen können Sortieralgorithmen vergleichsbasiert arbeiten oder eben nicht. Das heißt, dass ein Teil der Sortieralgorithmen Vergleiche von Elementen der Liste verwendet, um die Elemente entsprechend in die richtige Reihenfolge zu tauschen. Beim nicht vergleichsbasierten Verfahren liegt der Fokus auf der konditionierten Eingabe. Im Folgenden werden die vergleichsbasierten sortierverfahren behandelt.

== Stabilität ==

Zusätzliche kann zwischen stabilem und instabilem Verfahren unterschieden werden. Bei stabile Verfahren bleibt die Reihenfolge der Datensätze gleich, deren Sortierschlüssel auch gleich sind. Angenommen man möchte in einem Verein die bereits alphabetisch geordnete Mitglieder nach dem Geburtsdatum sortieren. Stabile Verfahren sorgen dafür, dass die Mitglieder mit gleichem Geburtsdatum weiterhin noch nach der alphabetischen Reihenfolge sortiert bleiben. Das Verfahren sortiert in erster Priorität nach dem Geburtsdatum und in zweiter Priorität nach alphabetische Reihenfolge.
== Übersicht ==
{| class="wikitable sortable" style="text-align:center;"
! rowspan="2" | Name
! colspan="3" | [[Laufzeitanalyse|Laufzeit]]
! colspan="3" | Platzkomplexität
! rowspan="2" | Stabil
! rowspan="2" | In-Place
! rowspan="2" | Vergleichs-orientiert
|-
! Best-Case !! Average-Case !! Worst-Case !! Best-Case !! Average-Case !! Worst-Case
|-
| [[Bubble-sort|Bubble Sort]]
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| [[Insertion-sort|Insertion Sort]]
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| [[Quicksort]]
| O(n log n) || O(n log n) || O(n²)
| O(log n) || O(log n) || O(n)
| nein || ja/nein || ja
|-
| [[Selection-sort|Selection Sort]]
| O(n²) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| nein || ja || ja
|}
[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Sortieren

2026-02-20T10:56:58Z

Thomas:

Sortieren

2026-02-20T10:56:34Z

Thomas: /* Übersicht */

Einführung
Ein übliches Problem in der Informatik ist es, Daten zu sortieren. Wer das Sortieren verstanden hat, dem wird es nicht schwerfallen, andere Algorithmen zu verstehen. Das Sortieren könnte man sozusagen auch als »Basics für Algorithmen« bezeichnen.
[[Datei:Sortiertes kartenspiel.png|mini]]

Primär geht es darum, die einzelnen Sortierverfahren näherzubringen, speziell deren Funktionen. Die Implementierung ist zumeist problemabhängig und richtet sich nach der Art der Daten, die es zu sortieren gilt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).Es gibt unterschiedliche Algorithmen für ein gegebenes Problem und so gibt es verschiedene Sortierverfahren. Jeder Algorithmus arbeitet unterschiedlich effizient, um ein Problem zu lösen. Die Zeitkomplexität eines Sortieralgorithmus gibt an, wie viele Operationen nötig sind, um einen Sortiervorgang abzuschließen. Bei gegebenen Hardwareausstattung lässt sich also messen, wie lange ein Sortiervorgang dauert.

== Platzkomplexität – In-place ==
Zusätzlich wird die Platzkomplexität eines Sortierverfahrens betrachtet. Hier wird analysiert, ob und wie viel zusätzlicher Speicher für den Sortiervorgang an sich benötigt wird. Bei in-Place wird nur eine konstante Menge an zusätzlichem Speicher benötigt z.B. Hilfsvariablen für den Dreieckstausch. Bei out-of-place wird eine dynamische Anzahl von zusätzlichem Speicher benötigt die abhängig von der Eingabegröße ist.

== Vergleichsbasierte Verfahren ==
Sortierverfahren können sich allgemein durch die Basis der Arbeitsweise unterscheiden. Zum einen können Sortieralgorithmen vergleichsbasiert arbeiten oder eben nicht. Das heißt, dass ein Teil der Sortieralgorithmen Vergleiche von Elementen der Liste verwendet, um die Elemente entsprechend in die richtige Reihenfolge zu tauschen. Beim nicht vergleichsbasierten Verfahren liegt der Fokus auf der konditionierten Eingabe. Im Folgenden werden die vergleichsbasierten sortierverfahren behandelt.

== Stabilität ==

Zusätzliche kann zwischen stabilem und instabilem Verfahren unterschieden werden. Bei stabile Verfahren bleibt die Reihenfolge der Datensätze gleich, deren Sortierschlüssel auch gleich sind. Angenommen man möchte in einem Verein die bereits alphabetisch geordnete Mitglieder nach dem Geburtsdatum sortieren. Stabile Verfahren sorgen dafür, dass die Mitglieder mit gleichem Geburtsdatum weiterhin noch nach der alphabetischen Reihenfolge sortiert bleiben. Das Verfahren sortiert in erster Priorität nach dem Geburtsdatum und in zweiter Priorität nach alphabetische Reihenfolge.
== Übersicht ==
{| class="wikitable sortable" style="text-align:center;"
! rowspan="2" | Name
! colspan="3" | [[Laufzeitanalyse|Laufzeit]]
! colspan="3" | Platzkomplexität
! rowspan="2" | Stabil
! rowspan="2" | In-Place
! rowspan="2" | Vergleichs-orientiert
|-
! Best-Case !! Average-Case !! Worst-Case !! Best-Case !! Average-Case !! Worst-Case
|-
| [[Bubble-sort|Bubble Sort]]
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| [[Insertion-sort|Insertion Sort]]
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| [[Quicksort]]
| O(n log n) || O(n log n) || O(n²)
| O(log n) || O(log n) || O(n)
| nein || ja/nein || ja
|-
| [[Selection-sort|Selection Sort]]
| O(n²) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| nein || ja || ja
|}

Sortieren

2026-02-20T10:56:14Z

Thomas: /* Übersicht */

Einführung
Ein übliches Problem in der Informatik ist es, Daten zu sortieren. Wer das Sortieren verstanden hat, dem wird es nicht schwerfallen, andere Algorithmen zu verstehen. Das Sortieren könnte man sozusagen auch als »Basics für Algorithmen« bezeichnen.
[[Datei:Sortiertes kartenspiel.png|mini]]

Primär geht es darum, die einzelnen Sortierverfahren näherzubringen, speziell deren Funktionen. Die Implementierung ist zumeist problemabhängig und richtet sich nach der Art der Daten, die es zu sortieren gilt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).Es gibt unterschiedliche Algorithmen für ein gegebenes Problem und so gibt es verschiedene Sortierverfahren. Jeder Algorithmus arbeitet unterschiedlich effizient, um ein Problem zu lösen. Die Zeitkomplexität eines Sortieralgorithmus gibt an, wie viele Operationen nötig sind, um einen Sortiervorgang abzuschließen. Bei gegebenen Hardwareausstattung lässt sich also messen, wie lange ein Sortiervorgang dauert.

== Platzkomplexität – In-place ==
Zusätzlich wird die Platzkomplexität eines Sortierverfahrens betrachtet. Hier wird analysiert, ob und wie viel zusätzlicher Speicher für den Sortiervorgang an sich benötigt wird. Bei in-Place wird nur eine konstante Menge an zusätzlichem Speicher benötigt z.B. Hilfsvariablen für den Dreieckstausch. Bei out-of-place wird eine dynamische Anzahl von zusätzlichem Speicher benötigt die abhängig von der Eingabegröße ist.

== Vergleichsbasierte Verfahren ==
Sortierverfahren können sich allgemein durch die Basis der Arbeitsweise unterscheiden. Zum einen können Sortieralgorithmen vergleichsbasiert arbeiten oder eben nicht. Das heißt, dass ein Teil der Sortieralgorithmen Vergleiche von Elementen der Liste verwendet, um die Elemente entsprechend in die richtige Reihenfolge zu tauschen. Beim nicht vergleichsbasierten Verfahren liegt der Fokus auf der konditionierten Eingabe. Im Folgenden werden die vergleichsbasierten sortierverfahren behandelt.

== Stabilität ==

Zusätzliche kann zwischen stabilem und instabilem Verfahren unterschieden werden. Bei stabile Verfahren bleibt die Reihenfolge der Datensätze gleich, deren Sortierschlüssel auch gleich sind. Angenommen man möchte in einem Verein die bereits alphabetisch geordnete Mitglieder nach dem Geburtsdatum sortieren. Stabile Verfahren sorgen dafür, dass die Mitglieder mit gleichem Geburtsdatum weiterhin noch nach der alphabetischen Reihenfolge sortiert bleiben. Das Verfahren sortiert in erster Priorität nach dem Geburtsdatum und in zweiter Priorität nach alphabetische Reihenfolge.
== Übersicht ==
{| class="wikitable sortable" style="text-align:center;"
! rowspan="2" | Name
! colspan="3" | Laufzeit
! colspan="3" | Platzkomplexität
! rowspan="2" | Stabil
! rowspan="2" | In-Place
! rowspan="2" | Vergleichs-orientiert
|-
! Best-Case !! Average-Case !! Worst-Case !! Best-Case !! Average-Case !! Worst-Case
|-
| [[Bubble-sort|Bubble Sort]]
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| [[Insertion-sort|Insertion Sort]]
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| [[Quicksort]]
| O(n log n) || O(n log n) || O(n²)
| O(log n) || O(log n) || O(n)
| nein || ja/nein || ja
|-
| [[Selection-sort|Selection Sort]]
| O(n²) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| nein || ja || ja
|}

Selectionsort

2026-02-20T10:55:55Z

Thomas: /* Einführung */

Selectionsort

2026-02-20T10:55:29Z

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…“

== 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>.

Datei:Animation Selectionsort.gif

2026-02-20T10:50:55Z

Thomas:

Animation Selectionsort

Datei:Array Selectionsort.gif

2026-02-20T10:49:55Z

Thomas:

Array Selectionsort

Sortieren

2026-02-20T10:47:40Z

Thomas: /* Übersicht */

Einführung
Ein übliches Problem in der Informatik ist es, Daten zu sortieren. Wer das Sortieren verstanden hat, dem wird es nicht schwerfallen, andere Algorithmen zu verstehen. Das Sortieren könnte man sozusagen auch als »Basics für Algorithmen« bezeichnen.
[[Datei:Sortiertes kartenspiel.png|mini]]

Primär geht es darum, die einzelnen Sortierverfahren näherzubringen, speziell deren Funktionen. Die Implementierung ist zumeist problemabhängig und richtet sich nach der Art der Daten, die es zu sortieren gilt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).Es gibt unterschiedliche Algorithmen für ein gegebenes Problem und so gibt es verschiedene Sortierverfahren. Jeder Algorithmus arbeitet unterschiedlich effizient, um ein Problem zu lösen. Die Zeitkomplexität eines Sortieralgorithmus gibt an, wie viele Operationen nötig sind, um einen Sortiervorgang abzuschließen. Bei gegebenen Hardwareausstattung lässt sich also messen, wie lange ein Sortiervorgang dauert.

== Platzkomplexität – In-place ==
Zusätzlich wird die Platzkomplexität eines Sortierverfahrens betrachtet. Hier wird analysiert, ob und wie viel zusätzlicher Speicher für den Sortiervorgang an sich benötigt wird. Bei in-Place wird nur eine konstante Menge an zusätzlichem Speicher benötigt z.B. Hilfsvariablen für den Dreieckstausch. Bei out-of-place wird eine dynamische Anzahl von zusätzlichem Speicher benötigt die abhängig von der Eingabegröße ist.

== Vergleichsbasierte Verfahren ==
Sortierverfahren können sich allgemein durch die Basis der Arbeitsweise unterscheiden. Zum einen können Sortieralgorithmen vergleichsbasiert arbeiten oder eben nicht. Das heißt, dass ein Teil der Sortieralgorithmen Vergleiche von Elementen der Liste verwendet, um die Elemente entsprechend in die richtige Reihenfolge zu tauschen. Beim nicht vergleichsbasierten Verfahren liegt der Fokus auf der konditionierten Eingabe. Im Folgenden werden die vergleichsbasierten sortierverfahren behandelt.

== Stabilität ==

Zusätzliche kann zwischen stabilem und instabilem Verfahren unterschieden werden. Bei stabile Verfahren bleibt die Reihenfolge der Datensätze gleich, deren Sortierschlüssel auch gleich sind. Angenommen man möchte in einem Verein die bereits alphabetisch geordnete Mitglieder nach dem Geburtsdatum sortieren. Stabile Verfahren sorgen dafür, dass die Mitglieder mit gleichem Geburtsdatum weiterhin noch nach der alphabetischen Reihenfolge sortiert bleiben. Das Verfahren sortiert in erster Priorität nach dem Geburtsdatum und in zweiter Priorität nach alphabetische Reihenfolge.
== Übersicht ==
{| class="wikitable sortable" style="text-align:center;"
! rowspan="2" | Name
! colspan="3" | Laufzeit
! colspan="3" | Platzkomplexität
! rowspan="2" | Stabil
! rowspan="2" | In-Place
! rowspan="2" | Vergleichs-orientiert
|-
! Best-Case !! Average-Case !! Worst-Case !! Best-Case !! Average-Case !! Worst-Case
|-
| [[Bubble-sort|Bubble Sort]]
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| [[Insertion-sort|Insertion Sort]]
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| [[Quicksort]]
| O(n log n) || O(n log n) || O(n²)
| O(log n) || O(log n) || O(n)
| nein || ja/nein || ja
|-
| Selection Sort
| O(n²) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| nein || ja || ja
|}

Algorithmus

2026-02-20T10:47:12Z

Thomas: /* Laufzeit */

Ein '''Algorithmus''' ist in der Informatik ein genau beschriebenes Verfahren zur Lösung eines gegebenen Problems. Ein '''Programm''' stellt die Übersetzung eines Algorithmus in eine vom Computer begreifbare und ausführbare Folge von Befehlen dar, an dessen Ende die Lösung eines Problems ausgegeben wird.

Problem --> Algorithmus --> Programm

Somit ist ein Algorithmus universeller als eine konkrete Implementierung.

== Einführung ==

Zwei oft zu bewältigende Probleme in der Informatik sind das [[Suchen]] und das [[Sortieren]] von [[Objekt|Objekten]]. Allerdings sind Algorithmen für Computer heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen Steuergerät für den Einsatz in KFZ über die Rechtschreib- und Satzbau-Kontrolle in einer Textverarbeitung bis hin zur Analyse von Aktienmärkten finden sich tausende von mehr oder minder tauglich arbeitenden Algorithmen.

Die Lösung komplexer Probleme sollte zuvor designed werden. Hierzu können Algorithmen vor der eigentlichen Programmierung in Ablaufplänen z.B. durch Modelle der [[UML]] oder [[Struktogramm|Struktogramme]] visualisiert werden. Algorithmen werden in der Programmierung durch [[Kontrollstruktur|Kontrollstrukturen]] oder [[Rekursion]] implementiert.
[[Datei:Übersicht Algorithmus.png|mini]]

== Eigenschaften ==

Ein Algorithmus in der Informatik ist die Beschreibung eines Verfahrens, um aus gewissen Eingabegrößen bestimmte Ausgabegrößen zu bestimmen. Hierfür müssen folgende Bedingungen erfüllt sein:

=== Spezifikation ===

Für Algorithmen werden Schnittstellenspezifikationen benötigt. Sie regeln die Ein- und Ausgabe des Algorithmus. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung werden Algorithmen mit [[Methode|Methoden]] realisiert. Die Schnittstelle der Methoden muss in der so genannten [[Methodensignatur|Signatur]] beschrieben werden.

==== Eingabespezifikation ====

Es muss genau spezifiziert sein, welche Eingabegrößen erforderlich sind und welche Anforderungen diesen Größen genügen müssen, damit das Verfahren funktioniert. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung wird die Eingabespezifikation durch so genannte Eingabeparameter definiert.

==== Ausgabespezifikation ====

Es muss genau spezifiziert sein, welche Ausgabegrößen (Resultate) mit welchen Eigenschaften bestimmt werden. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung wird die Ausgabespezifikation durch den so genannten Ausgabeparameter definiert.

=== Durchführbarkeit ===

==== Endliche Beschreibung ====

Das Verfahren muss mit einem endlichen Text beschrieben werden.

==== Effektivität ====

Jeder Schritt des Verfahrens muss tatsächlich durchführbar sein.

==== Determinismus und Determiniertheit ====

Wenn der Ablauf zu jedem Zeitpunkt fest vorgeschrieben ist, ist der Algorithmus deterministisch (Determinismus). Für zwei gleiche Eingabegrößen werden jedes Mal exakt die gleichen Rechenschritt in der identischen Reihenfolge durchlaufen. Jeder deterministische Algorithmus ist auch determiniert (Determiniertheit). Der Algorithmus ist determiniert, wenn dieser stets für die gleiche Eingabegröße die gleiche Ausgabegröße liefert! Aber ein determinierter Algorithmus, muss nicht deterministisch sein. Denn determinierte Algorithmen können für gleiche Eingabegrößen jedes Mal auf unterschiedlichen Wegen zum Ziel kommen; liefern aber jedes Mal das gleiche Ergebnis!

=== Korrektheit ===

==== Partielle Korrektheit ====

Jedes ermittelte Ergebnis genügt der Ausgabespezifikation, sofern die Eingaben der Eingabespezifikation genügen.

==== Terminierung ====

Der Algorithmus hält nach endlichen vielen Schritten an, sofern die Eingabe der Eingabespezifikation genügen.

=== Effizienz ===

Außerdem sollte der Algorithmus effizient arbeiten. D.h. er sollte nicht zu viel Rechenleistung des Prozessors binden, um die Ausführungszeit nicht unnötig zu verlängern. Dies wird vermieden indem zur Laufzeit eine möglichst minimale Anzahl an Befehlen abgearbeitet werden muss, um das gegebene Problem zu lösen.

==== Laufzeit ====

Die Anzahl der Schritte, die ein Algorithmus benötigt, wird als die [[Laufzeit]] des Algorithmus bezeichnet. Der Begriff Schritt bezieht sich auf das zugrunde gelegte Maschinenmodell. Die Maschine (der Computer) muss in der Lage sein, einen einzelnen Schritt in konstanter Zeit auszuführen. Die Laufzeit hängt im allgemeinen von der Eingabe ab, insbesondere von der Länge der Eingabe, die auch als Problemgröße bezeichnet wird.

Beispiel: Die [[Laufzeitanalyse|Laufzeit]] eines [[Sortieren|Sortieralgorithmus]] ist umso größer, je mehr Elemente zu sortieren sind. Soll eine Liste von fünf Zahlen sortiert werden, so ist die Problemgröße n=5.

Bei einer vorsortierten Eingabefolge benötigt der Algorithmus möglicherweise weniger Schritte als bei einer unsortierten Eingabefolge gleicher Länge. Eine vorsortierte Liste stellt das Best Case Szenario dar. Also den günstigsten Fall für das gegebene Problem (hier das Sortieren von Zahlen). Eine sortierte Liste in umgekehrter Reihenfolge stellt das Worst Case Szenario dar. Hier ist der Aufwand am größten die Liste umzusortieren.

Um den Algorithmus unabhängig von der konkreten Eingabe bewerten zu können, betrachtet man die Zeitkomplexität in der so genannten [[Laufzeitanalyse]].

== Beispiel ==

Das folgende Beispiel zeigt einen Algorithmus in der Programmiersprache [[Java]] der z.B. Bücher in einem Regal sortiert:

<syntaxhighlight lang="Java" line>
// Sortieren durch Vertauschen unmittelbarer Nachbarn

// beim ersten Durchgang "perlt" die größte Zahl nach hinten, so dass

// spätere Durtchgänge immer ein Element früher enden können und so

// der sortierte Teil von hinten nach vorne wächst
int durchgang, stelle;
for (durchgang=1; durchgang<reihung.length; durchgang++){

// Es werden alle zu durchsuchenden Elemente Schritt für Schritt durchlaufen
for (stelle=0; stelle<reihung.length-durchgang; stelle++){
// Durchgänge beginnen immer bei 0, enden aber immer früher
if (reihung[stelle] > reihung[stelle+1]){
// Nachbarn in falscher Reihenfolge werden vertauscht
tausche (stelle, stelle+1);
}
}
}
</syntaxhighlight>

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_SDM]]
[[Kategorie:FI_I_TP1]]

Algorithmus

2026-02-20T10:46:16Z

Thomas: /* Laufzeit */

Ein '''Algorithmus''' ist in der Informatik ein genau beschriebenes Verfahren zur Lösung eines gegebenen Problems. Ein '''Programm''' stellt die Übersetzung eines Algorithmus in eine vom Computer begreifbare und ausführbare Folge von Befehlen dar, an dessen Ende die Lösung eines Problems ausgegeben wird.

Problem --> Algorithmus --> Programm

Somit ist ein Algorithmus universeller als eine konkrete Implementierung.

== Einführung ==

Zwei oft zu bewältigende Probleme in der Informatik sind das [[Suchen]] und das [[Sortieren]] von [[Objekt|Objekten]]. Allerdings sind Algorithmen für Computer heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen Steuergerät für den Einsatz in KFZ über die Rechtschreib- und Satzbau-Kontrolle in einer Textverarbeitung bis hin zur Analyse von Aktienmärkten finden sich tausende von mehr oder minder tauglich arbeitenden Algorithmen.

Die Lösung komplexer Probleme sollte zuvor designed werden. Hierzu können Algorithmen vor der eigentlichen Programmierung in Ablaufplänen z.B. durch Modelle der [[UML]] oder [[Struktogramm|Struktogramme]] visualisiert werden. Algorithmen werden in der Programmierung durch [[Kontrollstruktur|Kontrollstrukturen]] oder [[Rekursion]] implementiert.
[[Datei:Übersicht Algorithmus.png|mini]]

== Eigenschaften ==

Ein Algorithmus in der Informatik ist die Beschreibung eines Verfahrens, um aus gewissen Eingabegrößen bestimmte Ausgabegrößen zu bestimmen. Hierfür müssen folgende Bedingungen erfüllt sein:

=== Spezifikation ===

Für Algorithmen werden Schnittstellenspezifikationen benötigt. Sie regeln die Ein- und Ausgabe des Algorithmus. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung werden Algorithmen mit [[Methode|Methoden]] realisiert. Die Schnittstelle der Methoden muss in der so genannten [[Methodensignatur|Signatur]] beschrieben werden.

==== Eingabespezifikation ====

Es muss genau spezifiziert sein, welche Eingabegrößen erforderlich sind und welche Anforderungen diesen Größen genügen müssen, damit das Verfahren funktioniert. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung wird die Eingabespezifikation durch so genannte Eingabeparameter definiert.

==== Ausgabespezifikation ====

Es muss genau spezifiziert sein, welche Ausgabegrößen (Resultate) mit welchen Eigenschaften bestimmt werden. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung wird die Ausgabespezifikation durch den so genannten Ausgabeparameter definiert.

=== Durchführbarkeit ===

==== Endliche Beschreibung ====

Das Verfahren muss mit einem endlichen Text beschrieben werden.

==== Effektivität ====

Jeder Schritt des Verfahrens muss tatsächlich durchführbar sein.

==== Determinismus und Determiniertheit ====

Wenn der Ablauf zu jedem Zeitpunkt fest vorgeschrieben ist, ist der Algorithmus deterministisch (Determinismus). Für zwei gleiche Eingabegrößen werden jedes Mal exakt die gleichen Rechenschritt in der identischen Reihenfolge durchlaufen. Jeder deterministische Algorithmus ist auch determiniert (Determiniertheit). Der Algorithmus ist determiniert, wenn dieser stets für die gleiche Eingabegröße die gleiche Ausgabegröße liefert! Aber ein determinierter Algorithmus, muss nicht deterministisch sein. Denn determinierte Algorithmen können für gleiche Eingabegrößen jedes Mal auf unterschiedlichen Wegen zum Ziel kommen; liefern aber jedes Mal das gleiche Ergebnis!

=== Korrektheit ===

==== Partielle Korrektheit ====

Jedes ermittelte Ergebnis genügt der Ausgabespezifikation, sofern die Eingaben der Eingabespezifikation genügen.

==== Terminierung ====

Der Algorithmus hält nach endlichen vielen Schritten an, sofern die Eingabe der Eingabespezifikation genügen.

=== Effizienz ===

Außerdem sollte der Algorithmus effizient arbeiten. D.h. er sollte nicht zu viel Rechenleistung des Prozessors binden, um die Ausführungszeit nicht unnötig zu verlängern. Dies wird vermieden indem zur Laufzeit eine möglichst minimale Anzahl an Befehlen abgearbeitet werden muss, um das gegebene Problem zu lösen.

==== Laufzeit ====

Die Anzahl der Schritte, die ein Algorithmus benötigt, wird als die [[Laufzeit]] des Algorithmus bezeichnet. Der Begriff Schritt bezieht sich auf das zugrunde gelegte Maschinenmodell. Die Maschine (der Computer) muss in der Lage sein, einen einzelnen Schritt in konstanter Zeit auszuführen. Die Laufzeit hängt im allgemeinen von der Eingabe ab, insbesondere von der Länge der Eingabe, die auch als Problemgröße bezeichnet wird.

Beispiel: Die [[Laufzeit]] eines [[Sortieralgorithmus]] ist umso größer, je mehr Elemente zu sortieren sind. Soll eine Liste von fünf Zahlen sortiert werden, so ist die Problemgröße n=5.

Bei einer vorsortierten Eingabefolge benötigt der Algorithmus möglicherweise weniger Schritte als bei einer unsortierten Eingabefolge gleicher Länge. Eine vorsortierte Liste stellt das Best Case Szenario dar. Also den günstigsten Fall für das gegebene Problem (hier das Sortieren von Zahlen). Eine sortierte Liste in umgekehrter Reihenfolge stellt das Worst Case Szenario dar. Hier ist der Aufwand am größten die Liste umzusortieren.

Um den Algorithmus unabhängig von der konkreten Eingabe bewerten zu können, betrachtet man die Zeitkomplexität in der so genannten [[Laufzeitanalyse]].

== Beispiel ==

Das folgende Beispiel zeigt einen Algorithmus in der Programmiersprache [[Java]] der z.B. Bücher in einem Regal sortiert:

<syntaxhighlight lang="Java" line>
// Sortieren durch Vertauschen unmittelbarer Nachbarn

// beim ersten Durchgang "perlt" die größte Zahl nach hinten, so dass

// spätere Durtchgänge immer ein Element früher enden können und so

// der sortierte Teil von hinten nach vorne wächst
int durchgang, stelle;
for (durchgang=1; durchgang<reihung.length; durchgang++){

// Es werden alle zu durchsuchenden Elemente Schritt für Schritt durchlaufen
for (stelle=0; stelle<reihung.length-durchgang; stelle++){
// Durchgänge beginnen immer bei 0, enden aber immer früher
if (reihung[stelle] > reihung[stelle+1]){
// Nachbarn in falscher Reihenfolge werden vertauscht
tausche (stelle, stelle+1);
}
}
}
</syntaxhighlight>

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_SDM]]
[[Kategorie:FI_I_TP1]]

Laufzeitanalyse

2026-02-20T10:45:37Z

Thomas: /* Beispiel */

== Einführung ==
[[Datei:Laufzeitanalyse asymptotisch.png|mini]]
Die Laufzeitanalyse betrachtet die Zeitkomplexität eines [[Algorithmus]]. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der [[Anweisung|Befehle]] analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe. Die Eingabe wird auch als Problemgröße bezeichnet.

Die Analyse für kleine Eingabemengen ist häufig nicht so bedeutsam, weil für diesen Fall auch schwach konzipierte [[Algorithmus|Algorithmen]] befriedigende Ergebnisse liefern. Wichtiger sind die Betrachtungen für sehr große Problemgrößen und einer ungünstigen Anordnung der Werte (worst-case). Dabei wird von der asymptotischen [[Programmausführung|Laufzeit]] gesprochen und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Soll z.B. eine Folge von Zahlen [[Sortieren|sortiert]] werden, dann betrachtet man eine theoretisch unendliche lange Folge von Zahlen.

Lässt sich ein Algorithmus mathematisch durch die Funktion beschreiben, so gilt: <math>f(x)=1/x+x</math>

Die rot dargestellte Funktion<math> \color{Red}{f(x) = 1/x + x} </math>nähert sich für große x der grün dargestellte Asymptote <math> \color{green}{g(x)} </math> an.

Die Laufzeit wird in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der Landau-Notation(Groß-O-Notation) abgeschätzt.

In der Praxis ist die Laufzeitanalyse interessant, weil hierdurch entschieden werden kann, ob ein Programm bei anwachsender Eingabemenge wirtschaftlich betrieben werden kann.
Abgrenzung
Abgrenzend kann gesagt werden, dass die Laufzeitanalyse folgendes nicht betrachtet:

Den Zeitaufwand eines implementierten Algorithmus auf einem bestimmten Computer für eine konkrete endliche Eingabemenge.

== Szenarien ==
Man unterscheidet die folgenden Varianten zur Laufzeitabschätzung:

* Das '''worst-case-szenario''' (engl. schlechtester Fall) beschreibt die Problemgröße, die zu einer maximal langen Durchlaufzeit eines Algorithmus führt und entspricht der oberen Schranke zur Lösung eines Problems.
* Das '''average-case-Szenario''' (engl. durchschnittlicher Fall) beschreibt die Problemgröße die zu einer mittleren Durchlaufzeit eines Algorithmus führt.
* Das '''best-case-Szenario''' (engl. bester Fall) beschreibt die Problemgröße die zu einer minimalen Durchlaufzeit eines Algorithmus führt. Dies entspricht der untere Schranke zur Lösung eines Problems.

== Beispiel ==
Im Folgenden wird die Laufzeitanalyse anhand des [[Insertion-sort|Insertionsorts]] praktisch durchgeführt. Wir betrachten den Insertionsort anhand einer möglichen Implementierung in der Programmiersprache [[Java]]. Der [[Algorithmus]] arbeitet mit einem [[Array]] als Datenstruktur und verwendet als [[Kontrollstruktur|Kontrollstrukturen]] [[Verzweigung|Verzweigungen]] und [[Schleife|Schleifen]].
<syntaxhighlight lang="java">
public void sortierenEinfuegen_MC() {
int v, i, j;
for (i = 1; i < zSortfeld.length; i++) {
c++; // Zähler für Vergleiche
if (zSortfeld[i] < zSortfeld[i - 1]) {
v = zSortfeld[i];
j = i;
do {
zSortfeld[j] = zSortfeld[j - 1];
j--;
} while ((j > 0) && (zSortfeld[j - 1] > v));
zSortfeld[j] = v;
}
printAnalyse(i);
}
}
</syntaxhighlight>

Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

[11,7,5,3,2,0]

Wir betrachten zunächst nur den Zeitverbrauch für die durchzuführenden Vergleichsoperationen. Diesen Zeitverbrauchen kennen wir nicht und geben ihn allgemein durch die Konstante c an. Die Anzahl der zu sortierenden Elemente entspricht der Variablen n.

Beim ersten äußeren [[Schleife]]ndurchlauf gilt für den Zeitaufwand c*1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe [[Insertion-sort|InsertionSort]]) der Datenstruktur. Beim zweiten Durchlauf der äußeren [[Schleife]] benötigen wir zwei Vergleiche, c * 2. Beim dritte Mal, c * 3 bis zum letzten Mal, wenn <math> c * n-1 </math>. Es gilt also:

<math>c⋅*(1+2+3+⋯+(n−1))</math>

[[Datei:Asymptote an quadratische Funktion2.png|mini]]
Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für arithmetische Reihen, erhalten wir:

<math>c⋅*(n−1+1)*((n−1)/2)=c*n2/2 − c*n/2</math>

Für sehr große n können wir den niederwertigen Term n/2 und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Für sehr große n verhält sich <math> C(n)</math> asymptotisch wie n2. Oder anders ausgedrückt <math> C(n)</math> liegt in der Klasse <math>O(n2)</math>.

Und wie beeinflussen die anderen Operationen wie Lesen und Schreiben, die zum Vertauschen der Werte benötigt werden die Zeitkomplexität? Für das Vertauschen der Werte würde nur ein konstanter Aufwand je Vergleich hinzukommen. Wir nennen ihn v und passen unsere Funktion entsprechend an:

<math>(v+c) * n2/2 − (v+c)* n/2</math>

Und wieder gilt, für sehr große n können wir den niederwertigen Term <math>(v+c)* n/2 </math>und die konstanten Faktoren v,c und 1/2 verwerfen, so dass immer noch gilt:

Für sehr große n verhält sich <math>C(n) </math>asymptotisch wie n2. Oder anders ausgedrückt <math>C(n) </math>liegt in der Klasse <math>O(n2)</math>.

Datei:Asymptote an quadratische Funktion2.png

2026-02-20T10:45:29Z

Thomas:

Asymptote an quadratische Funktion

Laufzeitanalyse

2026-02-20T10:44:10Z

Thomas: /* Beispiel */

== Einführung ==
[[Datei:Laufzeitanalyse asymptotisch.png|mini]]
Die Laufzeitanalyse betrachtet die Zeitkomplexität eines [[Algorithmus]]. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der [[Anweisung|Befehle]] analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe. Die Eingabe wird auch als Problemgröße bezeichnet.

Die Analyse für kleine Eingabemengen ist häufig nicht so bedeutsam, weil für diesen Fall auch schwach konzipierte [[Algorithmus|Algorithmen]] befriedigende Ergebnisse liefern. Wichtiger sind die Betrachtungen für sehr große Problemgrößen und einer ungünstigen Anordnung der Werte (worst-case). Dabei wird von der asymptotischen [[Programmausführung|Laufzeit]] gesprochen und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Soll z.B. eine Folge von Zahlen [[Sortieren|sortiert]] werden, dann betrachtet man eine theoretisch unendliche lange Folge von Zahlen.

Lässt sich ein Algorithmus mathematisch durch die Funktion beschreiben, so gilt: <math>f(x)=1/x+x</math>

Die rot dargestellte Funktion<math> \color{Red}{f(x) = 1/x + x} </math>nähert sich für große x der grün dargestellte Asymptote <math> \color{green}{g(x)} </math> an.

Die Laufzeit wird in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der Landau-Notation(Groß-O-Notation) abgeschätzt.

In der Praxis ist die Laufzeitanalyse interessant, weil hierdurch entschieden werden kann, ob ein Programm bei anwachsender Eingabemenge wirtschaftlich betrieben werden kann.
Abgrenzung
Abgrenzend kann gesagt werden, dass die Laufzeitanalyse folgendes nicht betrachtet:

Den Zeitaufwand eines implementierten Algorithmus auf einem bestimmten Computer für eine konkrete endliche Eingabemenge.

== Szenarien ==
Man unterscheidet die folgenden Varianten zur Laufzeitabschätzung:

* Das '''worst-case-szenario''' (engl. schlechtester Fall) beschreibt die Problemgröße, die zu einer maximal langen Durchlaufzeit eines Algorithmus führt und entspricht der oberen Schranke zur Lösung eines Problems.
* Das '''average-case-Szenario''' (engl. durchschnittlicher Fall) beschreibt die Problemgröße die zu einer mittleren Durchlaufzeit eines Algorithmus führt.
* Das '''best-case-Szenario''' (engl. bester Fall) beschreibt die Problemgröße die zu einer minimalen Durchlaufzeit eines Algorithmus führt. Dies entspricht der untere Schranke zur Lösung eines Problems.

== Beispiel ==
Im Folgenden wird die Laufzeitanalyse anhand des [[Insertion-sort|Insertionsorts]] praktisch durchgeführt. Wir betrachten den Insertionsort anhand einer möglichen Implementierung in der Programmiersprache [[Java]]. Der [[Algorithmus]] arbeitet mit einem [[Array]] als Datenstruktur und verwendet als [[Kontrollstruktur|Kontrollstrukturen]] [[Verzweigung|Verzweigungen]] und [[Schleife|Schleifen]].
<syntaxhighlight lang="java">
public void sortierenEinfuegen_MC() {
int v, i, j;
for (i = 1; i < zSortfeld.length; i++) {
c++; // Zähler für Vergleiche
if (zSortfeld[i] < zSortfeld[i - 1]) {
v = zSortfeld[i];
j = i;
do {
zSortfeld[j] = zSortfeld[j - 1];
j--;
} while ((j > 0) && (zSortfeld[j - 1] > v));
zSortfeld[j] = v;
}
printAnalyse(i);
}
}
</syntaxhighlight>

Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

[11,7,5,3,2,0]

Wir betrachten zunächst nur den Zeitverbrauch für die durchzuführenden Vergleichsoperationen. Diesen Zeitverbrauchen kennen wir nicht und geben ihn allgemein durch die Konstante c an. Die Anzahl der zu sortierenden Elemente entspricht der Variablen n.

Beim ersten äußeren [[Schleife]]ndurchlauf gilt für den Zeitaufwand c*1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe [[Insertion-sort|InsertionSort]]) der Datenstruktur. Beim zweiten Durchlauf der äußeren [[Schleife]] benötigen wir zwei Vergleiche, c * 2. Beim dritte Mal, c * 3 bis zum letzten Mal, wenn <math> c * n-1 </math>. Es gilt also:

<math>c⋅*(1+2+3+⋯+(n−1))</math>

[[Datei:Asymptote an quadratische Funktion.png|mini]]
Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für arithmetische Reihen, erhalten wir:

<math>c⋅*(n−1+1)*((n−1)/2)=c*n2/2 − c*n/2</math>

Für sehr große n können wir den niederwertigen Term n/2 und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Für sehr große n verhält sich <math> C(n)</math> asymptotisch wie n2. Oder anders ausgedrückt <math> C(n)</math> liegt in der Klasse <math>O(n2)</math>.

Und wie beeinflussen die anderen Operationen wie Lesen und Schreiben, die zum Vertauschen der Werte benötigt werden die Zeitkomplexität? Für das Vertauschen der Werte würde nur ein konstanter Aufwand je Vergleich hinzukommen. Wir nennen ihn v und passen unsere Funktion entsprechend an:

<math>(v+c) * n2/2 − (v+c)* n/2</math>

Und wieder gilt, für sehr große n können wir den niederwertigen Term <math>(v+c)* n/2 </math>und die konstanten Faktoren v,c und 1/2 verwerfen, so dass immer noch gilt:

Für sehr große n verhält sich <math>C(n) </math>asymptotisch wie n2. Oder anders ausgedrückt <math>C(n) </math>liegt in der Klasse <math>O(n2)</math>.

Datei:Asymptote an quadratische Funktion.png

2026-02-20T10:43:52Z

Thomas:

Asymptote an quadratische Funktion

Laufzeitanalyse

2026-02-20T10:42:48Z

Thomas: /* Beispiel */

== Einführung ==
[[Datei:Laufzeitanalyse asymptotisch.png|mini]]
Die Laufzeitanalyse betrachtet die Zeitkomplexität eines [[Algorithmus]]. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der [[Anweisung|Befehle]] analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe. Die Eingabe wird auch als Problemgröße bezeichnet.

Die Analyse für kleine Eingabemengen ist häufig nicht so bedeutsam, weil für diesen Fall auch schwach konzipierte [[Algorithmus|Algorithmen]] befriedigende Ergebnisse liefern. Wichtiger sind die Betrachtungen für sehr große Problemgrößen und einer ungünstigen Anordnung der Werte (worst-case). Dabei wird von der asymptotischen [[Programmausführung|Laufzeit]] gesprochen und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Soll z.B. eine Folge von Zahlen [[Sortieren|sortiert]] werden, dann betrachtet man eine theoretisch unendliche lange Folge von Zahlen.

Lässt sich ein Algorithmus mathematisch durch die Funktion beschreiben, so gilt: <math>f(x)=1/x+x</math>

Die rot dargestellte Funktion<math> \color{Red}{f(x) = 1/x + x} </math>nähert sich für große x der grün dargestellte Asymptote <math> \color{green}{g(x)} </math> an.

Die Laufzeit wird in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der Landau-Notation(Groß-O-Notation) abgeschätzt.

In der Praxis ist die Laufzeitanalyse interessant, weil hierdurch entschieden werden kann, ob ein Programm bei anwachsender Eingabemenge wirtschaftlich betrieben werden kann.
Abgrenzung
Abgrenzend kann gesagt werden, dass die Laufzeitanalyse folgendes nicht betrachtet:

Den Zeitaufwand eines implementierten Algorithmus auf einem bestimmten Computer für eine konkrete endliche Eingabemenge.

== Szenarien ==
Man unterscheidet die folgenden Varianten zur Laufzeitabschätzung:

* Das '''worst-case-szenario''' (engl. schlechtester Fall) beschreibt die Problemgröße, die zu einer maximal langen Durchlaufzeit eines Algorithmus führt und entspricht der oberen Schranke zur Lösung eines Problems.
* Das '''average-case-Szenario''' (engl. durchschnittlicher Fall) beschreibt die Problemgröße die zu einer mittleren Durchlaufzeit eines Algorithmus führt.
* Das '''best-case-Szenario''' (engl. bester Fall) beschreibt die Problemgröße die zu einer minimalen Durchlaufzeit eines Algorithmus führt. Dies entspricht der untere Schranke zur Lösung eines Problems.

== Beispiel ==
Im Folgenden wird die Laufzeitanalyse anhand des [[Insertion-sort|Insertionsorts]] praktisch durchgeführt. Wir betrachten den Insertionsort anhand einer möglichen Implementierung in der Programmiersprache [[Java]]. Der [[Algorithmus]] arbeitet mit einem [[Array]] als Datenstruktur und verwendet als [[Kontrollstruktur|Kontrollstrukturen]] [[Verzweigung|Verzweigungen]] und [[Schleife|Schleifen]].
<syntaxhighlight lang="java">
public void sortierenEinfuegen_MC() {
int v, i, j;
for (i = 1; i < zSortfeld.length; i++) {
c++; // Zähler für Vergleiche
if (zSortfeld[i] < zSortfeld[i - 1]) {
v = zSortfeld[i];
j = i;
do {
zSortfeld[j] = zSortfeld[j - 1];
j--;
} while ((j > 0) && (zSortfeld[j - 1] > v));
zSortfeld[j] = v;
}
printAnalyse(i);
}
}
</syntaxhighlight>

Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

[11,7,5,3,2,0]

Wir betrachten zunächst nur den Zeitverbrauch für die durchzuführenden Vergleichsoperationen. Diesen Zeitverbrauchen kennen wir nicht und geben ihn allgemein durch die Konstante c an. Die Anzahl der zu sortierenden Elemente entspricht der Variablen n.

Beim ersten äußeren [[Schleife]]ndurchlauf gilt für den Zeitaufwand c*1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe [[Insertion-sort|InsertionSort]]) der Datenstruktur. Beim zweiten Durchlauf der äußeren [[Schleife]] benötigen wir zwei Vergleiche, c * 2. Beim dritte Mal, c * 3 bis zum letzten Mal, wenn <math> c * n-1 </math>. Es gilt also:

<math>c⋅*(1+2+3+⋯+(n−1))</math>

Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für arithmetische Reihen, erhalten wir:

<math>c⋅*(n−1+1)*((n−1)/2)=c*n2/2 − c*n/2</math>

Für sehr große n können wir den niederwertigen Term n/2 und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Für sehr große n verhält sich <math> C(n)</math> asymptotisch wie n2. Oder anders ausgedrückt <math> C(n)</math> liegt in der Klasse <math>O(n2)</math>.

Und wie beeinflussen die anderen Operationen wie Lesen und Schreiben, die zum Vertauschen der Werte benötigt werden die Zeitkomplexität? Für das Vertauschen der Werte würde nur ein konstanter Aufwand je Vergleich hinzukommen. Wir nennen ihn v und passen unsere Funktion entsprechend an:

<math>(v+c) * n2/2 − (v+c)* n/2</math>

Und wieder gilt, für sehr große n können wir den niederwertigen Term <math>(v+c)* n/2 </math>und die konstanten Faktoren v,c und 1/2 verwerfen, so dass immer noch gilt:

Für sehr große n verhält sich <math>C(n) </math>asymptotisch wie n2. Oder anders ausgedrückt <math>C(n) </math>liegt in der Klasse <math>O(n2)</math>.

Laufzeitanalyse

2026-02-20T10:34:19Z

Thomas: /* Einführung */

Datei:Laufzeitanalyse asymptotisch.png

2026-02-20T09:48:01Z

Thomas:

Laufzeitanalyse asymptotisch

Quicksort

2026-02-20T09:46:42Z

Thomas: /* Worst-Case */

Quicksort

2026-02-20T09:46:23Z

Thomas: /* Laufzeitanalyse */

== Einführung ==
[[Datei:Rekursive Baumstruktur.jpg|mini]]
Ein oft eingesetzter [[Sortieren|Sortier]]-Algorithmus ist der Quicksort. Der Quicksort funktioniert nach dem Prinzip »teile und herrsche«, was mit Hilfe der [[Rekursion]] realisiert wird. Die zu sortierenden [[Daten]] werden immer in zwei Teile zerlegt ("Teile") und wieder sortiert ("Herrsche")). Diese zwei Teile werden wiederum jeweils in zwei Teile zerlegt und sortiert usw., bis die Daten sortiert sind. Die [[Rekursion]] beendet sich, wenn das Teilstück aus nur noch einem Element besteht (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm#mj035bded10a26be556df779f234784e89).

Die Zerlegung in zwei Teile erfolgt anhand eines sogenannten Pivot-Elementes. Ein Element der Liste wird als Pivot Element ausgewählt und dann werden alle weiteren Elemente der zu sortierenden Liste mit diesem Element verglichen. Die zu sortierende Liste wird in zwei Bereiche unterteilt. Alle Elemente die kleiner sind als das Pivot-Element werden links von dem Pivot-Element einsortiert. Alle Elemente die größer sind, werden rechts von Pivot-Element abgelegt.

Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich dem Pivot-Element und somit auch kleiner oder gleich den Elementen der rechten Liste. Die Elemente der linken und rechten Liste sind je Liste noch unsortiert.

Anschließend muss man noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort.

Die Teillisten sind immer Abschnitte auf der ursprünglichen Liste, so dass kein zusätzlicher Speicher benötigt wird.

== Beispiel ==
Als Beispiel betrachten wir eine Liste mit Zahlen. Wir wählen immer das erste Element als Pivot-Element. Zu Beginn ist die Zahl 7 zufällig das Pivot-Element.

7 10 8 6 11 4 9 3 1 5 2 12

Die Zahlen, die kleiner als das Pivot-Element 7 sind, wurden blau markiert. Die Zahlen größer 7 haben sind rot markiert. Als ersten Schritt ändert QuickSort die Liste folgendermaßen:

3 2 5 6 1 4 7 9 11 8 10 12

Nun sind alle Zahlen, welche kleiner sind als 7, links von ihr. Alle Zahlen welche größer sind als die 7, stehen rechts. Die Reihenfolge der Zahlen in den Teillisten ist hier willkürlich und hängt ab von der jeweiligen Implementierung. Entscheidend ist, dass alle Zahlen die kleiner sind als 7 links stehen und alle Zahlen die größer sind als 7 rechts.

Als nächstes wird der Teil links von der 7 wieder per QuickSort sortiert. Als Pivot wird die Zahl 3 gewählt. Die Zahlen die kleiner sind als 3 werden wieder blau markiert. Alle Zahlen größer 3 sind rot. Die Zahl 7 und die größeren Zahlen betrachten wir im Moment nicht, deshalb sind sie gelb hinterlegt:

3 2 5 6 1 4 7 9 11 8 10 12

Der Algorithmus bringt die blauen und die roten Zahlen wieder in die richtige Ordnung. Man erhält dann das Folgende:

1 2 3 6 5 4 7 9 11 8 10 12

Das wird fortgesetzt bis der linke Teil des Arrays sortiert ist. Das sieht dann wie folgt aus:

'''''1 2 3 4 5 6''''' 7 9 11 8 10 12

Nun wird rechts von der 7 sortiert. Wieder wird ein Pivot gewählt, hier die 9, und die kleineren und größeren Zahlen auf die jeweils richtige Seite gebracht.

Der grundsätzlichen Algorithmus lässt mit PseudoCode wie folgt beschreiben:

== Pseudocode ==
Der folgende Pseudocode illustriert die Arbeitsweise des [[Algorithmus]]. Bei jedem Aufruf von quicksort(...) gibt links den Index des ersten Elements in der Teilliste an und rechts den des letzten. Beim ersten Aufruf (oberste Rekursionsebene) ist links = 0 und rechts = n-1. Die übergebene Liste wird dabei [[Rekursion|rekursiv]] immer weiter geteilt, bis sie nur noch einen Wert enthält.
<syntaxhighlight>
funktion quicksort(links, rechts)
falls links < rechts dann
teiler := teile(links, rechts)
quicksort(links, teiler - 1)
quicksort(teiler + 1, rechts)
ende
ende
</syntaxhighlight>
== Wahl des Pivot-Elements ==
Die Wahl des Pivotelements ist wichtig. Die schlechteste Wahl des Pivots ist das Element, welches ganz am linken oder ganz am rechten Rand des zu sortierenden Intervalls endet. Mit linkem oder rechten Element ist nicht das Element gemeint, welches sich in der unsortierten Liste ganz Links (im Beispiel die 7) oder rechts befindet, sondern das kleinste (im Beispiel die 1) bzw. das größte Element (im Beispiel die 12). Der QuickSort ist dann am Effizientesten, wenn man ein Pivot-Element wählt, welches am Schluss genau in der Mitte zu liegen kommt (im Beispiel die 6 oder die 7). Leider ist dieses Element nicht ganz einfach zu finden.

Man sollte deshalb nicht immer wie im Beispiel das erste Element als Pivot wählen. Dies ist zwar leicht zu implementieren, allerdings führt dies zu einem langsamen "QuickSort", falls das Array bereits sortiert ist, oder nahezu sortiert ist.

Als Kompromiss wird oft ein zufälliges Element als Pivot-Element genommen. Noch besser kann es sein, von drei zufällig gewählten Elementen jeweils das mittlere zu nehmen.

== Java Implementierung ==
Bisher wurde die allgemeine Funktionsweise des Quicksorts beschrieben. Am Besten lassen sich komplexe [[Algorithmus|Algorithmen]] nachvollziehen, wenn Sie anhand einer Implementierung mit Hilfe eines [[Debugger|Debuggers]] analysiert werden. Mit Hilfe des Quicksorts können beliebige Datenstrukturen sortiert werden. In der folgenden [[Java]] Implementierung wird ein [[Array]] bestehend aus Integern (kurz int) sortiert.
<syntaxhighlight lang="java">
public void quickSort(int array[], int links, int rechts) {
if (links < rechts) {
int i = teile(array,links,rechts);
quickSort(array,links,i-1);
quickSort(array,i+1,rechts);
}
}

public int teile(int array[], int links, int rechts) {
int pivot, i, j, help;
pivot = array[rechts];
i = links;
j = rechts-1;
while(i<=j) {
if (array[i] > pivot) {
// tausche x[i] und x[j]
help = array[i];
array[i] = array[j];
array[j] = help;

j--;
} else i++;
}

// tausche x[i] und x[rechts]
help = array[i];
array[i] = array[rechts];
array[rechts] = help;
return i;
}
</syntaxhighlight>
== Laufzeitanalyse ==
=== Worst-Case ===
[[Datei:Baum N-Ebenen.png|mini]]
Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.

In diesem Szenario benötigt [[Rekursion|rekursive]] Aufruf von n-1 Elementen c* (n - 1) für eine Konstante c. Dies Konstante c repräsentiert die Benötigte Zeit für eine Operation wie einen Aufruf oder einen Vergleich. Für n-2 Elemente werden die Zeit c*(n-2) benötigt und so weiter (siehe Abbildung).

Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe|gauschen Summenformel]]:
<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>
Im Rahmend er Laufzeitanalyse ignorieren wir Terme niedriger Ordnung und konstante Koeffizienten. In der Big-Θ-Notation folgt hieraus die Worst-Case-Laufzeit von QuickSort <math> O(n^2)</math>.

== Best Case ==
[[Datei:Verzweigungsbaum Quicksort symetrisch.png|mini]]
Der beste Fall von Quicksort liegt vor, wenn die Partitionen so gleichmäßig wie möglich aufgeteilt werden: Ihre Größen sind entweder gleich oder weichen nur um ein Element voneinander ab.

[[Datei:SubArrays symetrisch Quicksort.png|mini]]
Der erstere Fall tritt auf, wenn das Subarray eine ungerade Anzahl von Elementen hat und der Drehpunkt nach der Partitionierung genau in der Mitte liegt und jede Partition <math>(n-1) / 2 </math> hat. Der letztere Fall tritt auf, wenn das Subarray eine gerade Anzahl n von Elementen hat und eine Partition n / 2 hat, während die andere n-1 / 2 hat. In beiden Fällen hat jede Partition höchstens n / 2 Elemente.

Wird die Anzahl der zu sortierenden Elemente n verdoppelt, muss nur eine neue Ebene mit Teilarrays erzeugt werden. Dieses Wachstum lässt sich mit <math>log(n) </math> beschreiben.
{| class="wikitable" style="text-align:center"
|-
! Zu sortierende Elemente n
| style="color:green" | 4
| style="color:green" | 8
| style="color:green" | 16
| style="color:green" | 32
|-
! Zu sortierende Elemente n
| <math>\color{green}{2^2}</math>
| <math>\color{green}{2^3}</math>
| <math>\color{green}{2^4}</math>
| <math>\color{green}{2^5}</math>
|-
! Anzahl Ebene log(n)
| style="color:red" | 2
| style="color:red" | 3
| style="color:red" | 4
| style="color:red" | 5
|}

In jeder Ebene müssen n Elemente sortiert werden. Hieraus ergibt sich eine Laufzeit von <math> O(n * log(n))</math>.

Quicksort

2026-02-20T09:45:18Z

Thomas:

== Einführung ==
[[Datei:Rekursive Baumstruktur.jpg|mini]]
Ein oft eingesetzter [[Sortieren|Sortier]]-Algorithmus ist der Quicksort. Der Quicksort funktioniert nach dem Prinzip »teile und herrsche«, was mit Hilfe der [[Rekursion]] realisiert wird. Die zu sortierenden [[Daten]] werden immer in zwei Teile zerlegt ("Teile") und wieder sortiert ("Herrsche")). Diese zwei Teile werden wiederum jeweils in zwei Teile zerlegt und sortiert usw., bis die Daten sortiert sind. Die [[Rekursion]] beendet sich, wenn das Teilstück aus nur noch einem Element besteht (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm#mj035bded10a26be556df779f234784e89).

Die Zerlegung in zwei Teile erfolgt anhand eines sogenannten Pivot-Elementes. Ein Element der Liste wird als Pivot Element ausgewählt und dann werden alle weiteren Elemente der zu sortierenden Liste mit diesem Element verglichen. Die zu sortierende Liste wird in zwei Bereiche unterteilt. Alle Elemente die kleiner sind als das Pivot-Element werden links von dem Pivot-Element einsortiert. Alle Elemente die größer sind, werden rechts von Pivot-Element abgelegt.

Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich dem Pivot-Element und somit auch kleiner oder gleich den Elementen der rechten Liste. Die Elemente der linken und rechten Liste sind je Liste noch unsortiert.

Anschließend muss man noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort.

Die Teillisten sind immer Abschnitte auf der ursprünglichen Liste, so dass kein zusätzlicher Speicher benötigt wird.

== Beispiel ==
Als Beispiel betrachten wir eine Liste mit Zahlen. Wir wählen immer das erste Element als Pivot-Element. Zu Beginn ist die Zahl 7 zufällig das Pivot-Element.

7 10 8 6 11 4 9 3 1 5 2 12

Die Zahlen, die kleiner als das Pivot-Element 7 sind, wurden blau markiert. Die Zahlen größer 7 haben sind rot markiert. Als ersten Schritt ändert QuickSort die Liste folgendermaßen:

3 2 5 6 1 4 7 9 11 8 10 12

Nun sind alle Zahlen, welche kleiner sind als 7, links von ihr. Alle Zahlen welche größer sind als die 7, stehen rechts. Die Reihenfolge der Zahlen in den Teillisten ist hier willkürlich und hängt ab von der jeweiligen Implementierung. Entscheidend ist, dass alle Zahlen die kleiner sind als 7 links stehen und alle Zahlen die größer sind als 7 rechts.

Als nächstes wird der Teil links von der 7 wieder per QuickSort sortiert. Als Pivot wird die Zahl 3 gewählt. Die Zahlen die kleiner sind als 3 werden wieder blau markiert. Alle Zahlen größer 3 sind rot. Die Zahl 7 und die größeren Zahlen betrachten wir im Moment nicht, deshalb sind sie gelb hinterlegt:

3 2 5 6 1 4 7 9 11 8 10 12

Der Algorithmus bringt die blauen und die roten Zahlen wieder in die richtige Ordnung. Man erhält dann das Folgende:

1 2 3 6 5 4 7 9 11 8 10 12

Das wird fortgesetzt bis der linke Teil des Arrays sortiert ist. Das sieht dann wie folgt aus:

'''''1 2 3 4 5 6''''' 7 9 11 8 10 12

Nun wird rechts von der 7 sortiert. Wieder wird ein Pivot gewählt, hier die 9, und die kleineren und größeren Zahlen auf die jeweils richtige Seite gebracht.

Der grundsätzlichen Algorithmus lässt mit PseudoCode wie folgt beschreiben:

== Pseudocode ==
Der folgende Pseudocode illustriert die Arbeitsweise des [[Algorithmus]]. Bei jedem Aufruf von quicksort(...) gibt links den Index des ersten Elements in der Teilliste an und rechts den des letzten. Beim ersten Aufruf (oberste Rekursionsebene) ist links = 0 und rechts = n-1. Die übergebene Liste wird dabei [[Rekursion|rekursiv]] immer weiter geteilt, bis sie nur noch einen Wert enthält.
<syntaxhighlight>
funktion quicksort(links, rechts)
falls links < rechts dann
teiler := teile(links, rechts)
quicksort(links, teiler - 1)
quicksort(teiler + 1, rechts)
ende
ende
</syntaxhighlight>
== Wahl des Pivot-Elements ==
Die Wahl des Pivotelements ist wichtig. Die schlechteste Wahl des Pivots ist das Element, welches ganz am linken oder ganz am rechten Rand des zu sortierenden Intervalls endet. Mit linkem oder rechten Element ist nicht das Element gemeint, welches sich in der unsortierten Liste ganz Links (im Beispiel die 7) oder rechts befindet, sondern das kleinste (im Beispiel die 1) bzw. das größte Element (im Beispiel die 12). Der QuickSort ist dann am Effizientesten, wenn man ein Pivot-Element wählt, welches am Schluss genau in der Mitte zu liegen kommt (im Beispiel die 6 oder die 7). Leider ist dieses Element nicht ganz einfach zu finden.

Man sollte deshalb nicht immer wie im Beispiel das erste Element als Pivot wählen. Dies ist zwar leicht zu implementieren, allerdings führt dies zu einem langsamen "QuickSort", falls das Array bereits sortiert ist, oder nahezu sortiert ist.

Als Kompromiss wird oft ein zufälliges Element als Pivot-Element genommen. Noch besser kann es sein, von drei zufällig gewählten Elementen jeweils das mittlere zu nehmen.

== Java Implementierung ==
Bisher wurde die allgemeine Funktionsweise des Quicksorts beschrieben. Am Besten lassen sich komplexe [[Algorithmus|Algorithmen]] nachvollziehen, wenn Sie anhand einer Implementierung mit Hilfe eines [[Debugger|Debuggers]] analysiert werden. Mit Hilfe des Quicksorts können beliebige Datenstrukturen sortiert werden. In der folgenden [[Java]] Implementierung wird ein [[Array]] bestehend aus Integern (kurz int) sortiert.
<syntaxhighlight lang="java">
public void quickSort(int array[], int links, int rechts) {
if (links < rechts) {
int i = teile(array,links,rechts);
quickSort(array,links,i-1);
quickSort(array,i+1,rechts);
}
}

public int teile(int array[], int links, int rechts) {
int pivot, i, j, help;
pivot = array[rechts];
i = links;
j = rechts-1;
while(i<=j) {
if (array[i] > pivot) {
// tausche x[i] und x[j]
help = array[i];
array[i] = array[j];
array[j] = help;

j--;
} else i++;
}

// tausche x[i] und x[rechts]
help = array[i];
array[i] = array[rechts];
array[rechts] = help;
return i;
}
</syntaxhighlight>
== Laufzeitanalyse ==
=== Worst-Case ===
[[Datei:Baum N-Ebenen.png|mini]]
Betrachten wir zunächst die Worst-Case-Laufzeitanalyseaufzeit. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.

In diesem Szenario benötigt [[Rekursion|rekursive]] Aufruf von n-1 Elementen c* (n - 1) für eine Konstante c. Dies Konstante c repräsentiert die Benötigte Zeit für eine Operation wie einen Aufruf oder einen Vergleich. Für n-2 Elemente werden die Zeit c*(n-2) benötigt und so weiter (siehe Abbildung).

Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe|gauschen Summenformel]]:
<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>
Im Rahmend er Laufzeitanalyse ignorieren wir Terme niedriger Ordnung und konstante Koeffizienten. In der Big-Θ-Notation folgt hieraus die Worst-Case-Laufzeit von QuickSort <math> O(n^2)</math>.

== Best Case ==
[[Datei:Verzweigungsbaum Quicksort symetrisch.png|mini]]
Der beste Fall von Quicksort liegt vor, wenn die Partitionen so gleichmäßig wie möglich aufgeteilt werden: Ihre Größen sind entweder gleich oder weichen nur um ein Element voneinander ab.

[[Datei:SubArrays symetrisch Quicksort.png|mini]]
Der erstere Fall tritt auf, wenn das Subarray eine ungerade Anzahl von Elementen hat und der Drehpunkt nach der Partitionierung genau in der Mitte liegt und jede Partition <math>(n-1) / 2 </math> hat. Der letztere Fall tritt auf, wenn das Subarray eine gerade Anzahl n von Elementen hat und eine Partition n / 2 hat, während die andere n-1 / 2 hat. In beiden Fällen hat jede Partition höchstens n / 2 Elemente.

Wird die Anzahl der zu sortierenden Elemente n verdoppelt, muss nur eine neue Ebene mit Teilarrays erzeugt werden. Dieses Wachstum lässt sich mit <math>log(n) </math> beschreiben.
{| class="wikitable" style="text-align:center"
|-
! Zu sortierende Elemente n
| style="color:green" | 4
| style="color:green" | 8
| style="color:green" | 16
| style="color:green" | 32
|-
! Zu sortierende Elemente n
| <math>\color{green}{2^2}</math>
| <math>\color{green}{2^3}</math>
| <math>\color{green}{2^4}</math>
| <math>\color{green}{2^5}</math>
|-
! Anzahl Ebene log(n)
| style="color:red" | 2
| style="color:red" | 3
| style="color:red" | 4
| style="color:red" | 5
|}

In jeder Ebene müssen n Elemente sortiert werden. Hieraus ergibt sich eine Laufzeit von <math> O(n * log(n))</math>.

Datei:SubArrays symetrisch Quicksort.png

2026-02-20T09:42:17Z

Thomas:

SubArrays symetrisch Quicksort

Datei:Verzweigungsbaum Quicksort symetrisch.png

2026-02-20T09:41:08Z

Thomas:

Verzweigungsbaum Quicksort symetrisch

Laufzeitanalyse

2026-02-20T08:21:35Z

Thomas: /* Einführung */

== Einführung ==
Die Laufzeitanalyse betrachtet die Zeitkomplexität eines [[Algorithmus]]. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der [[Anweisung|Befehle]] analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe. Die Eingabe wird auch als Problemgröße bezeichnet.

Die Analyse für kleine Eingabemengen ist häufig nicht so bedeutsam, weil für diesen Fall auch schwach konzipierte [[Algorithmus|Algorithmen]] befriedigende Ergebnisse liefern. Wichtiger sind die Betrachtungen für sehr große Problemgrößen und einer ungünstigen Anordnung der Werte (worst-case). Dabei wird von der asymptotischen [[Programmausführung|Laufzeit]] gesprochen und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Soll z.B. eine Folge von Zahlen [[Sortieren|sortiert]] werden, dann betrachtet man eine theoretisch unendliche lange Folge von Zahlen.

Lässt sich ein Algorithmus mathematisch durch die Funktion beschreiben, so gilt: <math>f(x)=1/x+x</math>

Die rot dargestellte Funktion<math> \color{Red}{f(x) = 1/x + x} </math>nähert sich für große x der grün dargestellte Asymptote <math> \color{green}{g(x)} </math> an.

Die Laufzeit wird in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der Landau-Notation(Groß-O-Notation) abgeschätzt.

In der Praxis ist die Laufzeitanalyse interessant, weil hierdurch entschieden werden kann, ob ein Programm bei anwachsender Eingabemenge wirtschaftlich betrieben werden kann.

Programmausführung

2026-02-20T08:17:46Z

Thomas:

[[Datei:SoftwareentwicklungAlsModell.png|mini]]
Die Programmausführung wird auch als Programmablauf, Laufzeit, Ausführungszeit oder Runtime bezeichnet. Um ein Programm auszuführen, arbeiten verschiedene Hardware- und Software-Komponenten eines Computers zusammen. Es wird auf unterster Ebene der Maschinensprache der Software über das Betriebssystem (d. h. ebenfalls durch dessen Maschinbefehle) in den Hauptspeicher des Computers geladen und dem Rechenwerk Schritt für Schritt zur Ausführung zugeführt.

Die Maschinensprache muss hierzu in einer Form/Struktur ([[Syntax]]) vorliegen, die von der Hardware ausgeführt werden kann. Inhalt und Struktur der Befehle zeigen an, was zu tun ist, welche Bereiche im Hauptspeicher dabei benutzt oder verändert werden sollen. Dieses Arbeitsprinzip gilt für jede Art von Software. Software wird in den meisten Fällen nicht in Maschinensprache erstellt. Mit Hilfe von Interpretern oder [[Compiler|Compilern]] wird die Software in Maschinensprache übersetzt, damit sie von einem Prozessor ausgeführt werden kann.

Alternativ kann eine Laufzeitumgebung zwischen geschaltet werden, die letztlich auch eine Software ist und Maschinensprache erzeugt.

[[Kategorie:Programmierung]]

Laufzeitanalyse

2026-02-20T08:13:52Z

Thomas: Die Seite wurde neu angelegt: „== Einführung == Die Laufzeitanalyse betrachtet die Zeitkomplexität eines Algorithmus. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der Befehle analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe. Die Eingabe…“

Quicksort

2026-02-20T08:12:12Z

Thomas:

== Einführung ==
[[Datei:Rekursive Baumstruktur.jpg|mini]]
Ein oft eingesetzter [[Sortieren|Sortier]]-Algorithmus ist der Quicksort. Der Quicksort funktioniert nach dem Prinzip »teile und herrsche«, was mit Hilfe der [[Rekursion]] realisiert wird. Die zu sortierenden [[Daten]] werden immer in zwei Teile zerlegt ("Teile") und wieder sortiert ("Herrsche")). Diese zwei Teile werden wiederum jeweils in zwei Teile zerlegt und sortiert usw., bis die Daten sortiert sind. Die [[Rekursion]] beendet sich, wenn das Teilstück aus nur noch einem Element besteht (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm#mj035bded10a26be556df779f234784e89).

Die Zerlegung in zwei Teile erfolgt anhand eines sogenannten Pivot-Elementes. Ein Element der Liste wird als Pivot Element ausgewählt und dann werden alle weiteren Elemente der zu sortierenden Liste mit diesem Element verglichen. Die zu sortierende Liste wird in zwei Bereiche unterteilt. Alle Elemente die kleiner sind als das Pivot-Element werden links von dem Pivot-Element einsortiert. Alle Elemente die größer sind, werden rechts von Pivot-Element abgelegt.

Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich dem Pivot-Element und somit auch kleiner oder gleich den Elementen der rechten Liste. Die Elemente der linken und rechten Liste sind je Liste noch unsortiert.

Anschließend muss man noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort.

Die Teillisten sind immer Abschnitte auf der ursprünglichen Liste, so dass kein zusätzlicher Speicher benötigt wird.

== Beispiel ==
Als Beispiel betrachten wir eine Liste mit Zahlen. Wir wählen immer das erste Element als Pivot-Element. Zu Beginn ist die Zahl 7 zufällig das Pivot-Element.

7 10 8 6 11 4 9 3 1 5 2 12

Die Zahlen, die kleiner als das Pivot-Element 7 sind, wurden blau markiert. Die Zahlen größer 7 haben sind rot markiert. Als ersten Schritt ändert QuickSort die Liste folgendermaßen:

3 2 5 6 1 4 7 9 11 8 10 12

Nun sind alle Zahlen, welche kleiner sind als 7, links von ihr. Alle Zahlen welche größer sind als die 7, stehen rechts. Die Reihenfolge der Zahlen in den Teillisten ist hier willkürlich und hängt ab von der jeweiligen Implementierung. Entscheidend ist, dass alle Zahlen die kleiner sind als 7 links stehen und alle Zahlen die größer sind als 7 rechts.

Als nächstes wird der Teil links von der 7 wieder per QuickSort sortiert. Als Pivot wird die Zahl 3 gewählt. Die Zahlen die kleiner sind als 3 werden wieder blau markiert. Alle Zahlen größer 3 sind rot. Die Zahl 7 und die größeren Zahlen betrachten wir im Moment nicht, deshalb sind sie gelb hinterlegt:

3 2 5 6 1 4 7 9 11 8 10 12

Der Algorithmus bringt die blauen und die roten Zahlen wieder in die richtige Ordnung. Man erhält dann das Folgende:

1 2 3 6 5 4 7 9 11 8 10 12

Das wird fortgesetzt bis der linke Teil des Arrays sortiert ist. Das sieht dann wie folgt aus:

'''''1 2 3 4 5 6''''' 7 9 11 8 10 12

Nun wird rechts von der 7 sortiert. Wieder wird ein Pivot gewählt, hier die 9, und die kleineren und größeren Zahlen auf die jeweils richtige Seite gebracht.

Der grundsätzlichen Algorithmus lässt mit PseudoCode wie folgt beschreiben:

== Pseudocode ==
Der folgende Pseudocode illustriert die Arbeitsweise des [[Algorithmus]]. Bei jedem Aufruf von quicksort(...) gibt links den Index des ersten Elements in der Teilliste an und rechts den des letzten. Beim ersten Aufruf (oberste Rekursionsebene) ist links = 0 und rechts = n-1. Die übergebene Liste wird dabei [[Rekursion|rekursiv]] immer weiter geteilt, bis sie nur noch einen Wert enthält.
<syntaxhighlight>
funktion quicksort(links, rechts)
falls links < rechts dann
teiler := teile(links, rechts)
quicksort(links, teiler - 1)
quicksort(teiler + 1, rechts)
ende
ende
</syntaxhighlight>
== Wahl des Pivot-Elements ==
Die Wahl des Pivotelements ist wichtig. Die schlechteste Wahl des Pivots ist das Element, welches ganz am linken oder ganz am rechten Rand des zu sortierenden Intervalls endet. Mit linkem oder rechten Element ist nicht das Element gemeint, welches sich in der unsortierten Liste ganz Links (im Beispiel die 7) oder rechts befindet, sondern das kleinste (im Beispiel die 1) bzw. das größte Element (im Beispiel die 12). Der QuickSort ist dann am Effizientesten, wenn man ein Pivot-Element wählt, welches am Schluss genau in der Mitte zu liegen kommt (im Beispiel die 6 oder die 7). Leider ist dieses Element nicht ganz einfach zu finden.

Man sollte deshalb nicht immer wie im Beispiel das erste Element als Pivot wählen. Dies ist zwar leicht zu implementieren, allerdings führt dies zu einem langsamen "QuickSort", falls das Array bereits sortiert ist, oder nahezu sortiert ist.

Als Kompromiss wird oft ein zufälliges Element als Pivot-Element genommen. Noch besser kann es sein, von drei zufällig gewählten Elementen jeweils das mittlere zu nehmen.

== Java Implementierung ==
Bisher wurde die allgemeine Funktionsweise des Quicksorts beschrieben. Am Besten lassen sich komplexe [[Algorithmus|Algorithmen]] nachvollziehen, wenn Sie anhand einer Implementierung mit Hilfe eines [[Debugger|Debuggers]] analysiert werden. Mit Hilfe des Quicksorts können beliebige Datenstrukturen sortiert werden. In der folgenden [[Java]] Implementierung wird ein [[Array]] bestehend aus Integern (kurz int) sortiert.
<syntaxhighlight lang="java">
public void quickSort(int array[], int links, int rechts) {
if (links < rechts) {
int i = teile(array,links,rechts);
quickSort(array,links,i-1);
quickSort(array,i+1,rechts);
}
}

public int teile(int array[], int links, int rechts) {
int pivot, i, j, help;
pivot = array[rechts];
i = links;
j = rechts-1;
while(i<=j) {
if (array[i] > pivot) {
// tausche x[i] und x[j]
help = array[i];
array[i] = array[j];
array[j] = help;

j--;
} else i++;
}

// tausche x[i] und x[rechts]
help = array[i];
array[i] = array[rechts];
array[rechts] = help;
return i;
}
</syntaxhighlight>
== Laufzeitanalyse ==
=== Worst-Case ===
[[Datei:Baum N-Ebenen.png|mini]]
Betrachten wir zunächst die Worst-Case-Laufzeitanalyseaufzeit. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.

In diesem Szenario benötigt [[Rekursion|rekursive]] Aufruf von n-1 Elementen c* (n - 1) für eine Konstante c. Dies Konstante c repräsentiert die Benötigte Zeit für eine Operation wie einen Aufruf oder einen Vergleich. Für n-2 Elemente werden die Zeit c*(n-2) benötigt und so weiter (siehe Abbildung).

Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe|gauschen Summenformel]]:
<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>
Im Rahmend er Laufzeitanalyse ignorieren wir Terme niedriger Ordnung und konstante Koeffizienten. In der Big-Θ-Notation folgt hieraus die Worst-Case-Laufzeit von QuickSort <math> O(n^2)</math>.

Datei:Baum N-Ebenen.png

2026-02-20T08:10:21Z

Thomas:

Baum N-Ebenen

Quicksort

2026-02-20T08:07:20Z

Thomas: /* Einführung */

Datei:Rekursive Baumstruktur.jpg

2026-02-20T07:50:20Z

Thomas:

Rekursive Baumstruktur

Quicksort

2026-02-20T07:47:23Z

Thomas: Die Seite wurde neu angelegt: „== Einführung == Ein oft eingesetzter Sortier-Algorithmus ist der Quicksort. Der Quicksort funktioniert nach dem Prinzip »teile und herrsche«, was mit Hilfe der Rekursion realisiert wird. Die zu sortierenden Daten werden immer in zwei Teile zerlegt ("Teile") und wieder sortiert ("Herrsche")). Diese zwei Teile werden wiederum jeweils in zwei Teile zerlegt und sortiert usw., bis die Daten sortiert sind. Die Rekursion beendet sic…“

== Einführung ==
Ein oft eingesetzter [[Sortieren|Sortier]]-Algorithmus ist der Quicksort. Der Quicksort funktioniert nach dem Prinzip »teile und herrsche«, was mit Hilfe der [[Rekursion]] realisiert wird. Die zu sortierenden [[Daten]] werden immer in zwei Teile zerlegt ("Teile") und wieder sortiert ("Herrsche")). Diese zwei Teile werden wiederum jeweils in zwei Teile zerlegt und sortiert usw., bis die Daten sortiert sind. Die [[Rekursion]] beendet sich, wenn das Teilstück aus nur noch einem Element besteht (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm#mj035bded10a26be556df779f234784e89).

Sortieren

2026-02-20T07:45:44Z

Thomas: /* Übersicht */

Einführung
Ein übliches Problem in der Informatik ist es, Daten zu sortieren. Wer das Sortieren verstanden hat, dem wird es nicht schwerfallen, andere Algorithmen zu verstehen. Das Sortieren könnte man sozusagen auch als »Basics für Algorithmen« bezeichnen.
[[Datei:Sortiertes kartenspiel.png|mini]]

Primär geht es darum, die einzelnen Sortierverfahren näherzubringen, speziell deren Funktionen. Die Implementierung ist zumeist problemabhängig und richtet sich nach der Art der Daten, die es zu sortieren gilt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).Es gibt unterschiedliche Algorithmen für ein gegebenes Problem und so gibt es verschiedene Sortierverfahren. Jeder Algorithmus arbeitet unterschiedlich effizient, um ein Problem zu lösen. Die Zeitkomplexität eines Sortieralgorithmus gibt an, wie viele Operationen nötig sind, um einen Sortiervorgang abzuschließen. Bei gegebenen Hardwareausstattung lässt sich also messen, wie lange ein Sortiervorgang dauert.

== Platzkomplexität – In-place ==
Zusätzlich wird die Platzkomplexität eines Sortierverfahrens betrachtet. Hier wird analysiert, ob und wie viel zusätzlicher Speicher für den Sortiervorgang an sich benötigt wird. Bei in-Place wird nur eine konstante Menge an zusätzlichem Speicher benötigt z.B. Hilfsvariablen für den Dreieckstausch. Bei out-of-place wird eine dynamische Anzahl von zusätzlichem Speicher benötigt die abhängig von der Eingabegröße ist.

== Vergleichsbasierte Verfahren ==
Sortierverfahren können sich allgemein durch die Basis der Arbeitsweise unterscheiden. Zum einen können Sortieralgorithmen vergleichsbasiert arbeiten oder eben nicht. Das heißt, dass ein Teil der Sortieralgorithmen Vergleiche von Elementen der Liste verwendet, um die Elemente entsprechend in die richtige Reihenfolge zu tauschen. Beim nicht vergleichsbasierten Verfahren liegt der Fokus auf der konditionierten Eingabe. Im Folgenden werden die vergleichsbasierten sortierverfahren behandelt.

== Stabilität ==

Zusätzliche kann zwischen stabilem und instabilem Verfahren unterschieden werden. Bei stabile Verfahren bleibt die Reihenfolge der Datensätze gleich, deren Sortierschlüssel auch gleich sind. Angenommen man möchte in einem Verein die bereits alphabetisch geordnete Mitglieder nach dem Geburtsdatum sortieren. Stabile Verfahren sorgen dafür, dass die Mitglieder mit gleichem Geburtsdatum weiterhin noch nach der alphabetischen Reihenfolge sortiert bleiben. Das Verfahren sortiert in erster Priorität nach dem Geburtsdatum und in zweiter Priorität nach alphabetische Reihenfolge.
== Übersicht ==
{| class="wikitable sortable" style="text-align:center;"
! rowspan="2" | Name
! colspan="3" | Laufzeit
! colspan="3" | Platzkomplexität
! rowspan="2" | Stabil
! rowspan="2" | In-Place
! rowspan="2" | Vergleichs-orientiert
|-
! Best-Case !! Average-Case !! Worst-Case !! Best-Case !! Average-Case !! Worst-Case
|-
| [[Bubble-sort|Bubble Sort]]
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| [[Insertion-sort|Insertion Sort]]
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| Quicksort
| O(n log n) || O(n log n) || O(n²)
| O(log n) || O(log n) || O(n)
| nein || ja/nein || ja
|-
| Selection Sort
| O(n²) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| nein || ja || ja
|}

Insertionsort

2026-02-20T07:44:57Z

Thomas: /* Pseudo Code */

Insertionsort

2026-02-18T13:39:29Z

Thomas: /* Best Case */

Einführung
Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relative simpel. Das Prinzip von Insertion Sort ist: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links weitergereicht – und das so lange, bis das bewegte Element größer oder gleich dem Element ist, das an der im Augenblick abgefragten Position liegt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).

Der Platz für das Element, das verschoben wird, ist frei. Diese Lücke wird mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

== Beispiel ==
[[Datei:Animation Insertio-Sort.gif|mini]]
Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite grün dargestellt befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links gewandert ist. Das aktuell eingefügte Element ist fett markiert. (http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertion.htm).
{| class="wikitable" style="text-align:center; font-family:monospace;"
|-
| ''5'' || 7 || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''5''' || '''7''' || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''''0''''' || 5 || 7 || 3 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || '''''3''''' || 5 || 7 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || 3 || '''''4''''' || 5 || 7 || 2 || 6 || 1 || (2)
|-
| 0 || '''''2''''' || 3 || 4 || 5 || 7 || 6 || 1 || (4)
|-
| 0 || 2 || 3 || 4 || 5 || '''''6''''' || 7 || 1 || (1)
|-
| 0 || '''''1''''' || 2 || 3 || 4 || 5 || 6 || 7 || (6)
|}
== Pseudo Code ==
Der Algorithmus sieht im Pseudocode so aus:
<syntaxhighlight line>
prozedur INSERTIONSORT(A ist Liste sortierbarer Elemente)
wiederhole bis zur Länge von A und beginne beim 2. Element
einzusortierender_wert = A an der Stelle i
j = i
wiederhole solange j > 1 und A an der Stelle j-1 > einzusortierender_wert
A an der Stelle j = A an der Stelle j-1
j = j − 1
ende wiederhole
A an der Stelle j = einzusortierender_wert
ende wiederhole
ende prozedur
</syntaxhighlight >

== Komplexität ==
=== Worst Case ===
Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

<math>[11,7,5,3,2,0]</math>

Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n.

Beim ersten äußeren Schleifendurchlauf ist c = 1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe oben) der Datenstruktur. Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche , c = 2. Beim dritte Mal, c = 3 bis zum letzten Mal, wenn c = n-1. Es gilt also:

<math>c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))</math>

Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für [[Arithmetische-reihe|arithmetische Reihen]], erhalten wir:

<math>c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2</math>

Für sehr große n können wir den niederwertigen Term <math>cn/2 </math> und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Der InsertionSort liegt hier in der Komplexitätsklasse <math>O(n2)</math>

=== Best Case ===
Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. <math>O(n)</math>). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.

Insertionsort

2026-02-18T13:39:13Z

Thomas: /* Worst Case */

Einführung
Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relative simpel. Das Prinzip von Insertion Sort ist: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links weitergereicht – und das so lange, bis das bewegte Element größer oder gleich dem Element ist, das an der im Augenblick abgefragten Position liegt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).

Der Platz für das Element, das verschoben wird, ist frei. Diese Lücke wird mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

== Beispiel ==
[[Datei:Animation Insertio-Sort.gif|mini]]
Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite grün dargestellt befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links gewandert ist. Das aktuell eingefügte Element ist fett markiert. (http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertion.htm).
{| class="wikitable" style="text-align:center; font-family:monospace;"
|-
| ''5'' || 7 || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''5''' || '''7''' || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''''0''''' || 5 || 7 || 3 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || '''''3''''' || 5 || 7 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || 3 || '''''4''''' || 5 || 7 || 2 || 6 || 1 || (2)
|-
| 0 || '''''2''''' || 3 || 4 || 5 || 7 || 6 || 1 || (4)
|-
| 0 || 2 || 3 || 4 || 5 || '''''6''''' || 7 || 1 || (1)
|-
| 0 || '''''1''''' || 2 || 3 || 4 || 5 || 6 || 7 || (6)
|}
== Pseudo Code ==
Der Algorithmus sieht im Pseudocode so aus:
<syntaxhighlight line>
prozedur INSERTIONSORT(A ist Liste sortierbarer Elemente)
wiederhole bis zur Länge von A und beginne beim 2. Element
einzusortierender_wert = A an der Stelle i
j = i
wiederhole solange j > 1 und A an der Stelle j-1 > einzusortierender_wert
A an der Stelle j = A an der Stelle j-1
j = j − 1
ende wiederhole
A an der Stelle j = einzusortierender_wert
ende wiederhole
ende prozedur
</syntaxhighlight >

== Komplexität ==
=== Worst Case ===
Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

<math>[11,7,5,3,2,0]</math>

Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n.

Beim ersten äußeren Schleifendurchlauf ist c = 1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe oben) der Datenstruktur. Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche , c = 2. Beim dritte Mal, c = 3 bis zum letzten Mal, wenn c = n-1. Es gilt also:

<math>c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))</math>

Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für [[Arithmetische-reihe|arithmetische Reihen]], erhalten wir:

<math>c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2</math>

Für sehr große n können wir den niederwertigen Term <math>cn/2 </math> und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Der InsertionSort liegt hier in der Komplexitätsklasse <math>O(n2)</math>

=== Best Case ===
Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. O(n)). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.

Insertionsort

2026-02-18T13:38:29Z

Thomas: /* Worst Case */

Einführung
Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relative simpel. Das Prinzip von Insertion Sort ist: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links weitergereicht – und das so lange, bis das bewegte Element größer oder gleich dem Element ist, das an der im Augenblick abgefragten Position liegt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).

Der Platz für das Element, das verschoben wird, ist frei. Diese Lücke wird mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

== Beispiel ==
[[Datei:Animation Insertio-Sort.gif|mini]]
Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite grün dargestellt befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links gewandert ist. Das aktuell eingefügte Element ist fett markiert. (http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertion.htm).
{| class="wikitable" style="text-align:center; font-family:monospace;"
|-
| ''5'' || 7 || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''5''' || '''7''' || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''''0''''' || 5 || 7 || 3 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || '''''3''''' || 5 || 7 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || 3 || '''''4''''' || 5 || 7 || 2 || 6 || 1 || (2)
|-
| 0 || '''''2''''' || 3 || 4 || 5 || 7 || 6 || 1 || (4)
|-
| 0 || 2 || 3 || 4 || 5 || '''''6''''' || 7 || 1 || (1)
|-
| 0 || '''''1''''' || 2 || 3 || 4 || 5 || 6 || 7 || (6)
|}
== Pseudo Code ==
Der Algorithmus sieht im Pseudocode so aus:
<syntaxhighlight line>
prozedur INSERTIONSORT(A ist Liste sortierbarer Elemente)
wiederhole bis zur Länge von A und beginne beim 2. Element
einzusortierender_wert = A an der Stelle i
j = i
wiederhole solange j > 1 und A an der Stelle j-1 > einzusortierender_wert
A an der Stelle j = A an der Stelle j-1
j = j − 1
ende wiederhole
A an der Stelle j = einzusortierender_wert
ende wiederhole
ende prozedur
</syntaxhighlight >

== Komplexität ==
=== Worst Case ===
Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

<math>[11,7,5,3,2,0]</math>

Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n.

Beim ersten äußeren Schleifendurchlauf ist c = 1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe oben) der Datenstruktur. Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche , c = 2. Beim dritte Mal, c = 3 bis zum letzten Mal, wenn c = n-1. Es gilt also:

<math>c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))</math>

Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für [[Arithmetische-reihe|arithmetische Reihen]], erhalten wir:

<math>c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2</math>

Für sehr große n können wir den niederwertigen Term cn/2 und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Der InsertionSort liegt hier in der Komplexitätsklasse O(n2)

=== Best Case ===
Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. O(n)). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.

Insertionsort

2026-02-18T13:37:46Z

Thomas: /* Komplexität */

Einführung
Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relative simpel. Das Prinzip von Insertion Sort ist: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links weitergereicht – und das so lange, bis das bewegte Element größer oder gleich dem Element ist, das an der im Augenblick abgefragten Position liegt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).

Der Platz für das Element, das verschoben wird, ist frei. Diese Lücke wird mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

== Beispiel ==
[[Datei:Animation Insertio-Sort.gif|mini]]
Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite grün dargestellt befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links gewandert ist. Das aktuell eingefügte Element ist fett markiert. (http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertion.htm).
{| class="wikitable" style="text-align:center; font-family:monospace;"
|-
| ''5'' || 7 || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''5''' || '''7''' || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''''0''''' || 5 || 7 || 3 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || '''''3''''' || 5 || 7 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || 3 || '''''4''''' || 5 || 7 || 2 || 6 || 1 || (2)
|-
| 0 || '''''2''''' || 3 || 4 || 5 || 7 || 6 || 1 || (4)
|-
| 0 || 2 || 3 || 4 || 5 || '''''6''''' || 7 || 1 || (1)
|-
| 0 || '''''1''''' || 2 || 3 || 4 || 5 || 6 || 7 || (6)
|}
== Pseudo Code ==
Der Algorithmus sieht im Pseudocode so aus:
<syntaxhighlight line>
prozedur INSERTIONSORT(A ist Liste sortierbarer Elemente)
wiederhole bis zur Länge von A und beginne beim 2. Element
einzusortierender_wert = A an der Stelle i
j = i
wiederhole solange j > 1 und A an der Stelle j-1 > einzusortierender_wert
A an der Stelle j = A an der Stelle j-1
j = j − 1
ende wiederhole
A an der Stelle j = einzusortierender_wert
ende wiederhole
ende prozedur
</syntaxhighlight >

== Komplexität ==
=== Worst Case ===
Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

[11,7,5,3,2,0]

Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n.

Beim ersten äußeren Schleifendurchlauf ist c = 1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe oben) der Datenstruktur. Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche , c = 2. Beim dritte Mal, c = 3 bis zum letzten Mal, wenn c = n-1. Es gilt also:

c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))

Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für [[Arithmetische-reihe|arithmetische Reihen]], erhalten wir:

c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2

Für sehr große n können wir den niederwertigen Term cn/2 und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Der InsertionSort liegt hier in der Komplexitätsklasse O(n2)

=== Best Case ===
Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. O(n)). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.

Arithmetische-reihe

2026-02-18T13:36:08Z

Thomas: Die Seite wurde neu angelegt: „== Einführung == Die gaußsche Summenformel, auch kleiner Gauß genannt, ist eine Formel für die Summe der ersten aufeinanderfolgenden natürlichen Zahlen (Quelle: https://de.wikipedia.org/wiki/Gau%C3%9Fsche_Summenformel) : <math>0 + 1 + 2 + 3 + 4 + \dots + n = \sum_{k=0}^{n} k = \frac{n(n+1)}{2} = \frac{n^2+n}{2}</math> Diese Summenformel wie auch die Summenformel für die ersten Quadratzahlen war bereits in der vorgriechischen Mathematik bekannt.…“

== Einführung ==
Die gaußsche Summenformel, auch kleiner Gauß genannt, ist eine Formel für die Summe der ersten

aufeinanderfolgenden natürlichen Zahlen (Quelle: https://de.wikipedia.org/wiki/Gau%C3%9Fsche_Summenformel) :

<math>0 + 1 + 2 + 3 + 4 + \dots + n = \sum_{k=0}^{n} k = \frac{n(n+1)}{2} = \frac{n^2+n}{2}</math>

Diese Summenformel wie auch die Summenformel für die ersten Quadratzahlen war bereits in der vorgriechischen Mathematik bekannt.

Carl Friedrich Gauß entdeckte diese Formel als neunjähriger Schüler wieder. Die Geschichte ist durch Wolfgang Sartorius von Waltershausen überliefert:

„Der junge Gauss war kaum in die Rechenclasse eingetreten, als Büttner die Summation einer arithmetischen Reihe aufgab. Die Aufgabe war indess kaum ausgesprochen als Gauss die Tafel mit den im niedern Braunschweiger Dialekt gesprochenen Worten auf den Tisch wirft: »Ligget se’.« (Da liegt sie.)“

– Wolfgang Sartorius von Waltershausen

== Erklärung ==
Wie berechnet man die Summe 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 möglichst schnell? Man vertauscht die Reihenfolge der Summanden wie folgt: Zuerst addieren wir 8 + 1, die größten und kleinsten Werte. Dann berechnen wir 7 + 2, die zweitgrößten und zweitkleinsten Werte. Das Ergebnis in beiden Fällen 9. Wie wäre es mit 6 + 3 ? Auch 9. Zuletzt, 5 + 4. Noch einmal 9! Das Ergebnis:

<math>(8+1)+(7+2)+(6+3)+(5+4)= 9 + 9 + 9 + 9 = 4 * 9 = 36 .</math>

Es gibt vier Paare von Zahlen, die sich jeweils zu 9 addieren. Allgemein kann man mit zwei Schritten jede Folge von aufeinander folgenden Ganzzahlen zusammenzufassen:

Füge die kleinste und die größte Zahl hinzu.

Multiplizieren Sie mit der Anzahl der Paare.

Dies gilt auch für ungleiche Paare. Zählen Sie einfach die ungepaarte Zahl in der Mitte der Sequenz als ein halbes Paar. Ein Beispiel:

<math>1 + 2 + 3 + 4 + 5</math>

Es gibt zwei volle Paare 1 + 5 und 2 + 4, jeweils summierend auf 6 und ein halbes Paar 3,die Hälfte von 6. Was insgesamt 2,5 Paare ergibt:

<math>2.5 * 6 = 15 </math>

Allgemein gilt die Summe der kleinsten und größten Summanden ist n + 1 . Da es n Zahlen insgesamt gibt, gibt es n / 2 Paare (ob n ungerade oder gerade ist) . Daher ist die Summe der Zahlen von 1 bis n :

<math>(n + 1) * (n / 2)</math>

Dies entspricht

<math>n²/2 + n/2</math>