Zum Inhalt springen

Sortieren: Unterschied zwischen den Versionen

Aus FLBK-Wiki
durchsicht>Wiki-Durchsicht
Durchsicht vom 15.11.2026: Befunde behoben
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]]


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 gegebener 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 oder höchstens logarithmisch wachsende 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 Struktur der Schlüssel, zum Beispiel einem begrenzten Wertebereich. 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ätzlich kann zwischen stabilem und instabilem Verfahren unterschieden werden. Bei stabilen Verfahren bleibt die Reihenfolge der Datensätze gleich, deren Sortierschlüssel auch gleich sind. Angenommen man möchte in einem Verein die bereits alphabetisch geordneten 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 alphabetischer Reihenfolge.
== Übersicht ==
== Übersicht ==
{| class="wikitable sortable" style="text-align:center;"
{| class="wikitable sortable" style="text-align:center;"
Zeile 21: Zeile 21:
! rowspan="2" | Stabil
! rowspan="2" | Stabil
! rowspan="2" | In-Place
! rowspan="2" | In-Place
! rowspan="2" | Vergleichs-orientiert
! rowspan="2" | Vergleichsbasiert
|-
|-
! Best-Case !! Average-Case !! Worst-Case !! Best-Case !! Average-Case !! Worst-Case
! Best-Case !! Average-Case !! Worst-Case !! Best-Case !! Average-Case !! Worst-Case
Zeile 38: Zeile 38:
| 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)
| nein || ja/nein || ja
| nein || ja || ja
|-
|-
| [[Selection-sort|Selection Sort]]
| [[Selection-sort|Selection Sort]]

Version vom 15. November 2026, 18:03 Uhr

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.

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 gegebener 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 oder höchstens logarithmisch wachsende 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 Struktur der Schlüssel, zum Beispiel einem begrenzten Wertebereich. Im Folgenden werden die vergleichsbasierten Sortierverfahren behandelt.

Stabilität

Zusätzlich kann zwischen stabilem und instabilem Verfahren unterschieden werden. Bei stabilen Verfahren bleibt die Reihenfolge der Datensätze gleich, deren Sortierschlüssel auch gleich sind. Angenommen man möchte in einem Verein die bereits alphabetisch geordneten 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 alphabetischer Reihenfolge.

Übersicht

Name Laufzeit Platzkomplexität Stabil In-Place Vergleichsbasiert
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 ja
Selection Sort O(n²) O(n²) O(n²) O(1) O(1) O(1) nein ja ja