Iteratives Mergesort mit Stackemulation

[Delphi-Laie]

Danke für die Anerkennung!

Zitat von Benmik:

Die verlinkte Webseite ("Sortierkino") ist schon beeindruckend. Man hat schon geahnt, dass es noch so einiges jenseits von Quick- und Bubblesort gibt, aber das ist wirklich eine erschlagende Fülle.

Nunja, viele der in meinem Programm angebotenen Algorithmen sind nur eine Modifikation bekannter Algorithmen, die ich aber aus Demonstrationsgründen wert erachtete, als separaten Eintrag mit aufzunehmen / -führen.

Zitat von Benmik:

Ich hielt Quicksort für den Allgemeingebrauch immer für den Algorithmus der Wahl (und fühlte mich dadurch bestätigt, dass Delphi ihn ja auch für Binary Search nimmt), aber das muss man vielleicht überdenken.

Für die Erstsortierung - dann logischerweise unsortierter - Daten trifft das auch zu, dafür ist Quicksort wirklich die Wahl ohne Qual, weil es der schnellste der In-Situ-Algorithmen ist. Bei bereits sortierten Daten macht sich jedoch die Nichstabilität des Quicksorts unangenehm bemerkbar. Außerdem droht der Algorithmus dann bei bestimmten Strukuturen der Eingangsmenge zu entarten (quadratische Komplexität). Es gibt natürlich auch Lösungen, die die Wahrscheinlichkeit dafür auf ein Minimum reduzieren (oder ganz beseitgen?), so z.B. das 3-Wege-Quicksort. Weiterer Aspekt: Quicksort ist mit akzeptablem Aufwand auch für mittelmäßig routinierte Programmierer zu implementieren.