Frage von grafensport, 58

Welches ist der beste Sortieralgorithmus?

Ich denke das diese Frage objektiv beantwortbar ist. Ich sage der gesuchte Algorithmus hat eine möglich kurze Laufzeit (selbst bei Datenmengen, wie sie in Enterprise-Systemen verarbeitet werden müssen) und ist stabil. Wie lässt sich der Umsetzen (Pseudocode reicht vollkommen)? Und Themenverwandt weiß man welcher Sortieralgorithmus eigentlich von Datenbanken wie SQL im Hintergrund angewendet wird oder sind das Firmengeheimnisse?

Antwort
von FaronWeissAlles, 52

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)

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten