FLBK-Wiki - Benutzerbeiträge [de]

Methode

2026-10-05T08:50:00Z

Thomas:

== Einstieg ==
[[Objekt|Objekte]] bestehen aus [[Attribut|Attributen]] und Methoden. [[Attribut|Attribute]] sind nur Variablen und [[Konstante|Konstanten]], die Werte aufnehmen können, und beschreiben damit den [[Zustand]] des [[Objekt|Objektes]]. Im Gegensatz dazu gibt es die „Methoden“, die das dynamische Verhalten des Objektes oder einer [[Klasse]] definieren. Sie enthalten die [[Algorithmus|Algorithmen]] eines Objektes.

Methoden sind in der [[Objektorientierung|objektorientierten]] Programmierung Unterprogramme, die das [[Verhalten]] von Objekten beschreiben und implementieren. Durch Methoden des Objekts können andere Objekte mit diesem [[Objekt]] über Nachrichten in Verbindung treten.

Neben der Bindung einer Methode an ein Objekt (also der [[Instanz]] einer [[Klasse]]), gibt die Möglichkeit Methoden direkt ohne Instanzen auszuführen. Solchen Methoden nennt man statisch (''static'').

== Syntax ==
Eine Methode muss im [[Körper]] einer [[Klasse]] stehen und besteht aus einem [[Kopf]] und einem Körper. Der Kopf besteht aus der [[Sichtbarkeit]] und einer [[Methodensignatur|Signatur]]. Die Signatur besteht aus einem [[Rückgabeparameter]], dem Methodennamen und [[Eingabeparametern]]. Die Reihenfolge dieser Elemente ist für den [[Compiler]] entscheidend.

=== Kopf ===
Der Kopf einer Methode besteht aus der [[Sichtbarkeit]] und der [[Methodensignatur|Signatur]] plus Rückgabeparameter.

==== Sichtbarkeit ====
Die Sichtbarkeit gibt an, wer auf die Methode zugreifen darf.
===== private =====
Die Sichtbarkeit private besagt, dass nur innerhalb einer [[Klasse]] bzw. [[Instanz]] auf eine Methode zugegriffen werden darf.

===== public =====
Die Sichtbarkeit public macht die Methode öffentlich zugänglich. Hier gibt es keine Einschränkung.

===== protected =====
Die Sichtbarkeit protected ermöglicht den Zugriff innerhalb der [[Klasse]] selbst, aller Klassen eines [[Package|Packages]] (im [[Projekt]]) und ihrer [[Vererbung|erbenden]] Kinderklassen.

===== default =====
Wird keine Angabe zur Sichtbarkeit gemacht, können alle Klassen eines Packages (im [[Projekt]]) zugreifen.

==== Signatur ====

Eine [[Methodensignatur|Signatur]](oder Methodensignatur) definiert in der Programmierung die Schnittstelle einer Methode. Sie besteht aus dem Namen der Methode und der Anzahl und Reihenfolge der [[Eingabeparameter]].

==== Methodenname ====

Der Methodenname ist freiwählbar. In der objektorientierten Softwareentwicklung ist es üblich Methodennamen mit einem Verb zu benennen. Hierdurch wird deutlich, dass die Methode Verhalten repräsentiert. So ist der Quelltext leichter zu lesen und zu verstehen.
==== Parameter ====
===== Rückgabeparameter =====

Der Rückgabeparameter definiert den (Daten)-Typen möglicher Ergebnisse dieser Methode. Das Ergebnis wird aus dem [[Körper]] der Methode mittels eines return-Befehls (return) zurückgegeben. Möglich sind [[Primitive Datentypen|primitive Datentypen]] wie Integer, Double oder Boolean aber auch [[Komplexe Datentypen|komplexe Datentypen]]. Komplexe Datentypen könne ein beliebige [[Klassen]] sein wie z.B. Mitarbeiter.

Soll ein Methode kein Ergebnis liefern muss das Schlüsselwort ''void'' geschrieben werden.

===== Eingabeparameter =====

Um eine Methode flexibel und wieder verwendbar zu gestalten, können von außen Werte an Variablen übergeben werden. Diese Variablen nennt man [[Eingabeparameter]]. Möglich sind 0 bis N Variablen. Jede Variable muss [[Deklaration|deklariert]] werden; benötigt also einen [[Datentyp]] und einen Namen. Die einzelnen Variablen werden durch Kommas getrennt. Die gesamte Eingabeparameterliste wird in runde Klammern geschrieben (), egal ob sie null oder n Parameter enthält. Wie beim Rückgabeparameter können primitive und komplexe Datentypen vergeben werden.

=== Körper ===
Der Körper einer Methode folgt auf den Kopf und wird in geschweiften Klammern geschrieben {}. Im Körper - also innerhalb der geschweiften Klammern - kann ein beliebiger [[Algorithmus]] stehen. Wurde im Kopf ein Rückgabeparameter definiert (also nicht ''void''), dann muss in jedem Fall ein zum Datentyp des Rückgabeparameters kompatible Rückgabe erfolgen. Die Rückgabe wird im Körper durch das Schlüsselwort ''return'' kenntlich gemacht.

Der [[Algorithmus]] einer Methoden wird durch [[Kontrollstruktur|Kontrollstrukturen]], Ausdrücke und Operanden definiert.

== Arten ==
Methoden, die nur einen Wert einer Instanzvariablen setzen bezeichnet man auch als verändernde Methoden (englisch auch setter-Methode).

Methoden, die nur einen Wert einer Instanzvariablen zurückliefern, bezeichnet man auch als sondierende Methoden (englisch auch getter-Methode).

Neben diesen beiden Kategorien gibt es beliebige Methoden und komplexen Algorithmen.

=== Verändernde Methode ===
Verändernde Methoden werden auch '''setter-Methoden''' genannt. Ihre Aufgabe ist es, einen Wert einer [[Instanzvariable]] zu setzen. Im Rahmen der [[Deklaration]] von Instanzvariablen, haben sich gewisse Standards etabliert. Die [[Sichtbarkeit]] von Instanzvariablen sollte als "private" gewählt werden. So wird sichergestellt, dass Daten nicht ungefiltert in die Instanzvariable hineingeschrieben und gelesen werden können.

So kann es sinnvoll sein, dass Rechnungsbeträge nur durch positive Gleitkommazahlen abgebildet werden sollen. Wählt man den [[Datentyp]] double, ist das Speichern von negativen Werten nach wie vor möglich. Eine valide Postleitzahl wiederum besteht stets aus fünf Ziffern. Das Passwort eines Mitarbeiters soll mindestens aus sechs Zeichen bestehen und mindestens eine Ziffer beinhalten. Diese Auswahl an Beispielen zeigt, dass ein Mechanismus benötigt wird, der sicherstellt, dass die Wertzuweisung von Instanzvariablen einer Qualitätskontrolle unterzogen wird.

'''Beispiel einfache verändernde Methode'''

Kann jeder Wert in z.B. eine Instanzvariable geschrieben werden reicht folgende setter-Methode aus:
<syntaxhighlight lang="Java">
public void setName(String einName){

name = einName;

}</syntaxhighlight>

Diese Methode ist öffentlich zugänglich (''public''). Sie liefert kein Ergebnis (''void''). Daher darf auch im Körper der Methode kein return-Befehl stehen. Der Name der Methode lautet ''setName''. Set steht für setzen und ist ein Verb. Die Eingabeparameter stehen in runden Klammern(). Hier gibt es eine Eingabe. Der [[Datentyp]] ist String und der Name des Eingabeparameters lautet einName. Der Wert von einName wird an die Instanzvariable name übergeben.

'''Beispiel verändernde Methode mit Filter'''

Rechnungsbeträge sollen nur positive Werte speichern dürfen.
<syntaxhighlight lang="Java">
public void setRechnungsbetrag (double einRechnungsbetrag){

if (einRechnungsbetrag>=0){

rechnungsbetrag = einRechnungsbetrag;

}

}</syntaxhighlight>

=== Sondierende Methode ===
Private Attribute verhindern den Zugriff von außen. Das Auslesen von Werten wird durch sondierende Methoden ermöglicht. Die folgende Methode String getName() ist eine sondierende Methode für die Instanzvariable Name.
<syntaxhighlight lang="Java">
public String getName(){
return name;
}
</syntaxhighlight>

Diese Methode ist öffentlich zugänglich (public). Sie liefert ein Ergebnis vom Typ String. Daher muss auch im Körper der Methode ein return-Befehl stehen. Der Name der Methode lautet "getName". Get steht für gib und ist ein Verb. Die Eingabeparameter stehen in runden Klammern(). Hier gibt es keine Eingabeparameter, da nur der Werte der Instanzvariablen name zurückgegebenwerden soll.

=== Komplexere Methode ===

<syntaxhighlight lang="Java">
private Mitarbeiter findeMitarbeiter(String nachname, String vorname){

for(Mitarbeiter aktuellerMitarbeiter:mitarbeiterListe){

if(aktuellerMitarbeiter.equals(nachname)){

return aktuellerMitarbeiter;

}

}

return null;

}</syntaxhighlight>

Diese Methode ist nicht öffentlich zugänglich (''private''). Die Methode heißt ''findeMitarbeiter''. Sie liefert ein Ergebnis vom Typ Mitarbeiter. Mitarbeiter ist ein [[Klasse]]. Somit wird ein [[Objekt]] zurückgeben. Weil eine Rückgabe erwartet wird, muss im Körper der Methode ein return-Befehl stehen. Da in jedem Falle ein Rückgabe erfolgen muss, wird der return Befehl am Ende der Methode ausgeführt, für den Fall, dass kein Mitarbeiter gefunden wurde. Der Algorithmus der Mitarbeitersuche wurde durch die [[Kontrollstruktur|Kontrollstrukturen]] Verzweigung und Schleife realisiert. Die Eingabeparameter stehen in runden Klammern(). Hier gibt es zwei Eingabeparameter vom Typ String. Der erste heißt nachname, der zweite vorname.

== Überladen ==
Das Überladen von Methoden ist sinnvoll, wenn Methoden eine vergleichbare Funktionalität haben und daher auch den gleichen Namen tragen sollten. Zwei Methoden einer Klasse heißen überladen, wenn sie den gleichen Namen, aber eine unterschiedliche Eingabeparameterliste haben. Ein abweichender Rückgabeparameter der Methoden ist für das Überladen nicht relevant.

Eine unterschiedliche Parameterliste bedeutet, dass die Anzahl und/oder die Typen der Parameter unterschiedlich sind. Es spielt keine Rolle, ob die Methoden in der Klasse deklariert sind oder ob sie von einer anderen Klasse geerbt wurden.

Beim Methodenaufruf wird die speziellste passende Methode ausgeführt. D.h. es wird automatisch die Methode ausgewählt, für die am wenigsten Parameter implizit in andere Datentypen konvertiert werden müssen. Diese Auswahl muss eindeutig sein.

Die folgenden Methoden ermitteln das Minimum einer Eingabeparameterliste. Methode 3 wird einen Compilerfehler auslösen, da sich die [[Methodensignatur|Signatur]] nur durch den Rückgabeparameter unterscheidet. Dies ist nicht ausreichend, um einer Methode zu überladen.
<syntaxhighlight lang="Java">
public class Berchnung

{

//Methode 1

public int min (int i1, int i2) {

if (i1<i2){

return i1;

}else{

return i2;

}

}

//Methode 2

public double min (double i1, double i2) {

if (i1<i2){

return i1;

}else{

return i2;

}

}

//Methode 3

public float min (double i1, double i2) {

if (i1<i2){

return i1;

}else{

return i2;

}

}</syntaxhighlight>

== Polymorphie ==
[[Polymorphie]] bedeutet "Vielgestaltigkeit." Im Bereich der [[Objektorientierung]] bezieht sich Polymorphie darauf, dass verschiedene [[Objekt|Objekte]] bei Aufruf derselben Methode unterschiedliches Verhalten an den Tag legen können.

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

Methodensignatur

2026-10-05T08:45:51Z

Thomas: /* Aufbau */

== Einführung ==
In der [[Java]]-Programmierung spielt die Methodensignatur eine wichtige Rolle. Sie ist vergleichbar mit dem Steckbrief einer [[Methode]] und enthält alle wichtigen Informationen, die der [[Compiler]] benötigt, um sie eindeutig zu identifizieren.

== Aufbau ==
Die Methodensignatur in [[Java]] besteht aus zwei Elementen:
* Methodenname: Der Name, den die [[Methode]] trägt (z. B. berechneSumme).
* Eingabeparameterliste: Eine Liste der [[Datentyp|Datentypen]] der Parameter, die die [[Methode]] akzeptiert, in der korrekten Reihenfolge.#.

''Wichtig ist, dass der Rückgabetyp der [[Methode]] und der [[Sichtbarkeit|Zugriffsmodifikator]] (z.B. public, private) nicht Teil der Signatur sind. Die Signatur dient ausschließlich dazu, die Methode innerhalb einer [[Klasse]] zu identifizieren und von anderen Methoden zu unterscheiden.''

== Beispiel ==
<syntaxhighlight lang="Java">
public class Rechner {

// Erste Methode
public int addiere(int zahl1, int zahl2) {
return zahl1 + zahl2;
}

// Zweite Methode - hat eine andere Signatur!
public double addiere(double zahl1, double zahl2) {
return zahl1 + zahl2;
}

// Dritte Methode - hat eine andere Signatur!
public int subtrahiere(int zahl1, int zahl2) {
return zahl1 - zahl2;
}
}</syntaxhighlight>
Die Signaturen der Methoden in diesem Beispiel sind:

* addiere(int, int)
* addiere(double, double)
* subtrahiere(int, int)

Die beiden addiere-[[Methode|Methoden]] haben den gleichen Namen, aber unterschiedliche Parameterlisten (einmal int, einmal double). Der [[Compiler]] kann sie dank ihrer unterschiedlichen Signaturen auseinanderhalten. Dieses Konzept wird als Methodenüberladen (Method Overloading) bezeichnet.

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

Methodensignatur

2026-10-05T08:44:04Z

Thomas:

== Einführung ==
In der [[Java]]-Programmierung spielt die Methodensignatur eine wichtige Rolle. Sie ist vergleichbar mit dem Steckbrief einer [[Methode]] und enthält alle wichtigen Informationen, die der [[Compiler]] benötigt, um sie eindeutig zu identifizieren.

== Aufbau ==
Die Methodensignatur in [[Java]] besteht aus drei Elementen:
* Methodenname: Der Name, den die [[Methode]] trägt (z. B. berechneSumme).
* Eingabeparameterliste: Eine Liste der [[Datentyp|Datentypen]] der Parameter, die die [[Methode]] akzeptiert, in der korrekten Reihenfolge.#
* Rückgabeparamter: Ein [[Datentyp]] für die Rückgabe oder void für keine Rückgabe.

Wichtig ist, dass der Rückgabetyp der [[Methode]] und der [[Sichtbarkeit|Zugriffsmodifikator]] (z.B. public, private) nicht Teil der Signatur sind. Die Signatur dient ausschließlich dazu, die Methode innerhalb einer [[Klasse]] zu identifizieren und von anderen Methoden zu unterscheiden.

== Beispiel ==
<syntaxhighlight lang="Java">
public class Rechner {

// Erste Methode
public int addiere(int zahl1, int zahl2) {
return zahl1 + zahl2;
}

// Zweite Methode - hat eine andere Signatur!
public double addiere(double zahl1, double zahl2) {
return zahl1 + zahl2;
}

// Dritte Methode - hat eine andere Signatur!
public int subtrahiere(int zahl1, int zahl2) {
return zahl1 - zahl2;
}
}</syntaxhighlight>
Die Signaturen der Methoden in diesem Beispiel sind:

* addiere(int, int)
* addiere(double, double)
* subtrahiere(int, int)

Die beiden addiere-[[Methode|Methoden]] haben den gleichen Namen, aber unterschiedliche Parameterlisten (einmal int, einmal double). Der [[Compiler]] kann sie dank ihrer unterschiedlichen Signaturen auseinanderhalten. Dieses Konzept wird als Methodenüberladen (Method Overloading) bezeichnet.

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

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.