Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 15. August 2020 

Sortierverfahren


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Ein Sortierverfahren ist ein Algorithmus der dazu dient Menge von Werten zu sortieren. Voraussetzung ist auf den Werten eine totale Ordnung existiert etwa die alphabetische Ordnung von oder die numerische Ordnung von Zahlen. Die liegt üblicherweise in Form eines Arrays vor.

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

Man unterscheidet zudem zwischen stabilen und instabilen Sortierverfahren sowie zwischen solchen in-place arbeiten d.h. die ohne zusätzlichen Speicherplatz und solchen die dies nicht tun.

Allgemeine Verfahren basieren auf dem paarweisen der zu sortierenden Elemente. Bei der Komplexitätsanalyse davon ausgegangen dass der Aufwand zum Vergleich Elemente konstant ist.

Sortierverfahren Komplexität stabil zusätzlicher Speicherbedarf
Binarytreesort O(n·log(n)) ja O(n)
Bogosort O((n/2)!) nein O(n)
Bubblesort O(n 2 ) ja -
Cocktailsort (ShakerSort) O(n 2 ) ja -
Combsort O(n·log(n)) nein -
Heapsort O(n·log(n)) nein -
Insertionsort O(n 2 ) ja -
Introsort O(n·log(n)) nein -
Mergesort O(n·log(n)) ja bei Arrays: O(n)
Quicksort O(n·log(n)) im Worst Case O(n 2 ) nein -
Selectionsort O(n 2 ) nein -
Shellsort O(n·log(n) 2 ) ja -
Smoothsort O(n·log(n)) nein -

Es lässt sich beweisen dass ein Sortierverfahren nicht schneller als O(n·log(n)) sein kann. dazu BeweisUntereSchranke (Sortierverfahren) . Allerdings gibt es Daten bei denen aus dem Schlüssel auch ohne Vergleiche mit Elemente Information über die Position des Elementes der sortierten Folge gewinnen lässt. In diesem kann ein spezialisiertes Verfahren schneller sein.

Sortierverfahren Komplexität stabil zusätzlicher Speicherbedarf
Bucketsort O(n+k) ja O(n+k)
Countingsort O(m+n) ja -
Radixsort O(n·log(k)) nein O(n)



Bücher zum Thema Sortierverfahren

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Sortierverfahren.html">Sortierverfahren </a>