Logo Logo
InfoHome Themen Projekte Links Software
Themen
JavaHamster
BlueJ
Java
Sprachelemente
Abstrakte Datentypen
Swing
Sortieren
Binäre Suche
InsertionSort
SelectionSort
BubbleSort
ShakerSort
Quicksort
MergeSort
Komplexität
HTML
XHTML
CSS
XML
Datenbanken
MySQL
Theoretische Informatik
PHP
Kara
Lego-Roboter
Algorithmen

Sortierverfahren

Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine Ordnungsrelation definiert ist, die verschiedene gleichartige Objekte erlaubt, ansonsten aber eine eindeutige Reihenfolge festlegt. Diese Voraussetzung ist zum Beispiel bei der lexikographischen Ordnung von Zeichenketten oder der numerischen Ordnung von Zahlen erfüllt.

Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten. Die Komplexität eines Algorithmus, also die Anzahl der nötigen Operationen, wird üblicherweise in der Landau-Notation (später...) dargestellt. Einige Sortierverfahren benötigen außerdem neben dem zur Speicherung des Arrays nötigen noch weiteren Speicherplatz. Komplexität und Speicherbedarf hängen bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bester Fall), Average Case (Durchschnittsverhalten) und Worst Case (schlechtester Fall).

Man unterscheidet zudem zwischen stabilen und instabilen Sortierverfahren. Stabile Sortierverfahren sind solche, die die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind, nicht verändern, während instabile Sortierverfahren diese Reihenfolge ändern können.

Zudem unterscheidet man zwischen Sortierverfahren, die in-place (auch in situ) arbeiten, d.h. die ohne zusätzlichen Speicherplatz funktionieren, und solchen, die dies nicht tun.

» drucken: pdf | html

© 2004-2019 M. Blanke · Ursulaschule · Kleine Domsfreiheit 11-18 · 49074 Osnabrück