TimSort - Sortieralgorithmus - Erklärung und Pseudocode - Implementierung

[iTobi97]

Hallo liebe Community,
ich möchte gerne zum einen den TimSort-Sortieralgorithmus verstehen, und ihn dann in Java implementieren. Zu diesem Sortieralgorithmus gibt es aber scheinbar fast keine Referenzen oder gute Erklärungen (geschweige denn in verständlicher Sprache), welche sich auch nie auf Java beziehen. Man findet nicht mal einen kurzen Pseudocode zur Implementierung. Ich bin Informatik-Student im ersten Semester, und mir fehlt da einfach noch die Erfahrung. Die vielen Bezeichnungen und Begriffe finde ich ziemlich verwirrend.

Vielleicht wäre jemand so toll, mir den Algorithmus in einfachen Worten zu erklären und den Algorithmus vielleicht in Pseudocodeform darzustellen.

Vielen Dank schon einmal im Voraus
VG

 

[Meniskusschaden]

Zu diesem Sortieralgorithmus gibt es aber scheinbar fast keine Referenzen oder gute Erklärungen (geschweige denn in verständlicher Sprache), welche sich auch nie auf Java beziehen.

Doch die gibt es. Eine gute Einführung ist zum Beispiel in diesem Dokument enthalten.

Man findet nicht mal einen kurzen Pseudocode zur Implementierung. Ich bin Informatik-Student im ersten Semester, und mir fehlt da einfach noch die Erfahrung. Die vielen Bezeichnungen und Begriffe finde ich ziemlich verwirrend.

Da Timsort kein eigenständiger Sortieralgorithmus ist, sondern verschiedene andere Algorithmen kombiniert, ist es da eben nicht mit ein paar Zeilen Pseudocode getan. Und um Timsort zu verstehen, muß man sich natürlich auch alle dabei verwendeten Algorithmen und möglichst auch die Terminologie erarbeiten. Das ist schon mehr Aufwand als bei einem eigenständigen Sortieralgorithmus.

Vielleicht wäre jemand so toll, mir den Algorithmus in einfachen Worten zu erklären und den Algorithmus vielleicht in Pseudocodeform darzustellen.

Aus den oben genannten Gründen wird vermutlich kaum jemand Lust haben, dir eine einfache Erklärung oder Pseudocode zu liefern. Ist doch klar, dass man so aus der hohlen Hand keine bessere Erklärung hin bekommt, als die bereits veröffentlichten Texte, die mit viel mehr Aufwand erstellt wurden. Stelle doch lieber konkrete Verständnisfragen. Das bringt bestimmt mehr.

 

[JStein52]

und beim googeln danach findet man auch gleich eine Java-Implementierung dazu ...