Sortieren - Versionsgeschichte

Thomas: /* Übersicht */

2026-02-20T10:58:14Z

Übersicht

← Nächstältere Version		Version vom 20. Februar 2026, 12:58 Uhr
Zeile 45:		Zeile 45:
	\| nein \|\| ja \|\| ja		\| nein \|\| ja \|\| ja
	\|}		\|}
			[[Kategorie:Programmierung]]
			[[Kategorie:AHR_I_Informatik_LK]]
			[[Kategorie:FI_I_TP2]]

Thomas am 20. Februar 2026 um 10:56 Uhr

2026-02-20T10:56:58Z

← Nächstältere Version		Version vom 20. Februar 2026, 12:56 Uhr
Zeile 1:		Zeile 1:
	Einführung		== 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.		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]]		[[Datei:Sortiertes kartenspiel.png\|mini]]

Thomas: /* Übersicht */

2026-02-20T10:56:34Z

Übersicht

← Nächstältere Version		Version vom 20. Februar 2026, 12:56 Uhr
Zeile 17:		Zeile 17:
	{\| class="wikitable sortable" style="text-align:center;"		{\| class="wikitable sortable" style="text-align:center;"
	! rowspan="2" \| Name		! rowspan="2" \| Name
	! colspan="3" \| Laufzeit		! colspan="3" \| [[Laufzeitanalyse\|Laufzeit]]
	! colspan="3" \| Platzkomplexität		! colspan="3" \| Platzkomplexität
	! rowspan="2" \| Stabil		! rowspan="2" \| Stabil

Thomas: /* Übersicht */

2026-02-20T10:56:14Z

Übersicht

← Nächstältere Version		Version vom 20. Februar 2026, 12:56 Uhr
Zeile 40:		Zeile 40:
	\| nein \|\| ja/nein \|\| ja		\| nein \|\| ja/nein \|\| ja
	\|-		\|-
	\| Selection Sort		\| [[Selection-sort\|Selection Sort]]
	\| O(n²) \|\| O(n²) \|\| O(n²)		\| O(n²) \|\| O(n²) \|\| O(n²)
	\| O(1) \|\| O(1) \|\| O(1)		\| O(1) \|\| O(1) \|\| O(1)
	\| nein \|\| ja \|\| ja		\| nein \|\| ja \|\| ja
	\|}		\|}

Thomas: /* Übersicht */

2026-02-20T10:47:40Z

Übersicht

← Nächstältere Version		Version vom 20. Februar 2026, 12:47 Uhr
Zeile 35:		Zeile 35:
	\| ja \|\| ja \|\| ja		\| ja \|\| ja \|\| ja
	\|-		\|-
	\| Quicksort		\| [[Quicksort]]
	\| O(n log n) \|\| O(n log n) \|\| O(n²)		\| O(n log n) \|\| O(n log n) \|\| O(n²)
	\| O(log n) \|\| O(log n) \|\| O(n)		\| O(log n) \|\| O(log n) \|\| O(n)

Thomas: /* Übersicht */

2026-02-20T07:45:44Z

Übersicht

← Nächstältere Version		Version vom 20. Februar 2026, 09:45 Uhr
Zeile 30:		Zeile 30:
	\| ja \|\| ja \|\| ja		\| ja \|\| ja \|\| ja
	\|-		\|-
	\| Insertion Sort		\| [[Insertion-sort\|Insertion Sort]]
	\| O(n) \|\| O(n²) \|\| O(n²)		\| O(n) \|\| O(n²) \|\| O(n²)
	\| O(1) \|\| O(1) \|\| O(1)		\| O(1) \|\| O(1) \|\| O(1)

Thomas: /* Übersicht */

2026-02-18T13:21:27Z

Übersicht

← Nächstältere Version		Version vom 18. Februar 2026, 15:21 Uhr
Zeile 25:		Zeile 25:
	! Best-Case !! Average-Case !! Worst-Case !! Best-Case !! Average-Case !! Worst-Case		! Best-Case !! Average-Case !! Worst-Case !! Best-Case !! Average-Case !! Worst-Case
	\|-		\|-
	\| Bubble Sort		\| [[Bubble-sort\|Bubble Sort]]
	\| O(n) \|\| O(n²) \|\| O(n²)		\| O(n) \|\| O(n²) \|\| O(n²)
	\| O(1) \|\| O(1) \|\| O(1)		\| O(1) \|\| O(1) \|\| O(1)

Thomas am 18. Februar 2026 um 13:07 Uhr

2026-02-18T13:07:43Z

← Nächstältere Version		Version vom 18. Februar 2026, 15:07 Uhr
Zeile 5:		Zeile 5:
	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.		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		== 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.		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		== 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.		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		== 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.		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.

Thomas: Die Seite wurde neu angelegt: „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. mini Primär geht es darum, die einzelnen Sortierverfahren näherzubringen, speziell deren Funktionen. Die Implementierung ist zumeist problemabhängig und…“

2026-02-18T13:06:59Z

Die Seite wurde neu angelegt: „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. mini Primär geht es darum, die einzelnen Sortierverfahren näherzubringen, speziell deren Funktionen. Die Implementierung ist zumeist problemabhängig und…“

Neue Seite

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
| O(n) || O(n²) || O(n²)
| O(1) || O(1) || O(1)
| ja || ja || ja
|-
| 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
|}