Welches ist der beste Sortieralgorithmus?

...komplette Frage anzeigen

Das Ergebnis basiert auf 0 Abstimmungen

Quelloffene Systeme verwenden diese Algorithmen (bitte beschreiben), SQL ist geheim 0%
Datenbaken sotieren ganz anders (z.B. über das Filesystems des Betriebssystems, bitte beschreiben) 0%
Das ist von System zu System unterschiedlich/es gibt keinen Standard 0%
Datenbanken verwenden im allgemeinen den Algorithmus (bitte Beschreiben) 0%
Datenbank sotieren nicht, ihr Suchalgorithmus liefert die Daten schon sotiert retur (und wie?) 0%

1 Antwort

Wie gut ein Sortieralgorithmus sortiert hängt stark von der Art/Struktur der Daten ab in denen sie vorliegen. Je nachdem wie er arbeitet kann das dann zum Vorteil oder zum Nachteil sein. Beispiel Telefonbuch: Liegen die Daten komplett zufällig vor? Liegen sie (zufällig) genau falsch herum sortiert vor? Sind sie bis auf wenige Ausnahmen schon richtig sortiert? Heißen 98% der Personen Müller?

Bei der Bewertung wird dann vor allem der Worst-Case und der Average-Case betrachtet bei verschiedenen Klassen von Eingabedaten. Die Menge der Daten spielt dabei eine eher nebensächliche Rolle. Interessant ist hingegen das Skalierungsverhalten. Das wird dann mit der O-Notation angegeben und besagt wie "extrem wächst der Aufwand bei n Datensätzen" (konstant - logarithmisch - linear - quasilinear - quadratisch - kubisch - faktoriell).

Ein als "gut" geltender Sortieralgorithmus hat bei möglichst vielen Arten von Situationen sowohl im Worst als auch im Average einen möglichst geringen Aufwand. Einer der in sehr vielen Fällen eine ganz passable Figur macht ist Quicksort. Trotzdem gibts andere die in bestimmten Situationen besser abschneiden. Einer der ziemlich schlecht ist wäre Bubblesort. In Informatik-Kursen wird der auch gern zur Demonstration herangezogen. Auf Wikipedia gibts Pseudocode dazu.

SQL ist nur eine Abfragesprache für Datenbanken. Was du meinst sind Datenbank-Managementsysteme (DBMS), die Sortieralgorithmen brauchen um die Daten filtern zu können. Und jedes DBMS kann alles mögliche einsetzen, denn es gibt ja mehr als nur MySQL da draußen: MSSQL, Oracle SQL, MariaDB (wobei das ein Fork von MySQL ist), SQLite, Northwind, PostgreSQL, nur um mal ein paar Namen zu nennen. Und die Technik dahinter ist eigentlich ziemlich harter Stoff. SQL selbst (als Sprache) ist nichts anderes als angewandte Mengenlehre. Es ist davon auszugehen dass diese Systeme nicht nur einen Algorithmus einsetzen sondern viele Techniken nutzen.

Open Source DBMS sind von Natur aus nicht geheim. Aber auch kommerzielle Systeme  sind nicht zwangsläufig so geheimnistuerisch was die verwendeten Algorithmen angeht. Zu MSSQL im speziellen gibt auch ein Buch wie der intern arbeitet (Microsoft SQL Server 2008 Internals)

Was möchtest Du wissen?