Sortieralgorithmen vergleich/bewertung

[deggit_biber]

Hallo,

ich weiß nicht, ob es hier hin gehört oder nicht, aber ihr könnt mir bestimmt weiterhelfen ;-)

Und zwar möchte ich verschiedene Sortieralgorithmen miteinander vergleichen! Jetzt frage ich mich aber gerade was wird als Kriterium in der Regel gezählt, wenn es um den Vergleich geht?

Nur die Vertauschungen von Zahlen die nicht passen? Oder alle Vergleiche die entstehen, um eine Reihe zu sortieren.

Für eine kurze Antwort wäre ich sehr dankbar!
Viele liebe Grüße,
deggit

 

[Meniskusschaden]

Ein paar mögliche Kriterien: Laufzeit, Speicherbedarf, in situ/ex situ, Stabilität, Einfachheit.

 

[Bitfehler]

Bei einigen der genannten Kriterien kann man noch zwischen den schlechtesten, besten und durchschnittlichen Fall unterscheiden.

PS: Wie bewertet man den Einfachheit objektiv?

 

[Meniskusschaden]

PS: Wie bewertet man den Einfachheit objektiv?

Darüber habe ich mir noch keine Gedanken gemacht. Man könnte vielleicht ein paar Eigenschaften wie Anzahl der Quelltextzeilen, Verschachtelungstiefe der Schleifen oder Anzahl der Fallunterscheidungen betrachten. Aber unabhängig davon, ob man eine objektive Metrik findet, halte ich es für ein relevantes Kriterium.

 

[Baldur]

Wirklich relevant dürfte eigentlich nur Speicherbedarf und Laufzeit sein. Stabil sollte eigentlich jeder Algorithmus sein, oder was meinst du damit?
Einfachkeit ist ja generell ein wichtiges Kriterium für Quelltext, aber speziell für (Sortier-)algorithmen (meiner Meinung nach) eher nebensächlich. Die sollen ja in erster Linie effizient sein, dafür versteckt man sie am Ende in einer Library und sollte nicht mehr viel dran ändern müssen. Falsch wärs aber sicher nicht, wenn man die Einfachkeit trotzdem als Kriterium mit einbezieht.

Bei Laufzeit kann man noch unterscheiden zwischen der absoluten Anzahl von Vergleichen und der Anzahl der nötigen Schreiboperationen. Je nachdem mit welchen Objekten man arbeitet kann ein compare(a, b) ja auch schon aufwändiger sein und demnach mehr Kosten verursachen als wie bei einfachen Zahlen.

Man sollte auf jeden Fall, wie schon erwähnt wurde zwischen besten und schlechtesten Fall bzw. Durchschnitt unterscheiden. Ich mag z.B. den Bubble-Sort immernoch sehr gern z.B. für Z-Order Geschichten, weil er fast immer nach einem Durchlauf fertig ist

 

[Meniskusschaden]

Stabil sollte eigentlich jeder Algorithmus sein, oder was meinst du damit?

Damit meine ich, dass Elemente mit gleichem Sortierkriterium ihre ursprüngliche Reihenfolge beibehalten. Ich glaube, "stabil" ist der gängige Begriff dafür. Ich meinte es nicht im Sinne von robust oder zuverlässig.

Einfachkeit ist ja generell ein wichtiges Kriterium für Quelltext, aber

Deswegen hatte ich es nach kurzem Zögern doch als Kriterium genannt, denn ich wollte nicht einsehen, dass ein Kriterium, dass generell relevant ist, beim Sortieren keine Rolle mehr spielen soll.

aber speziell für (Sortier-)algorithmen (meiner Meinung nach) eher nebensächlich. Die sollen ja in erster Linie effizient sein, dafür versteckt man sie am Ende in einer Library und sollte nicht mehr viel dran ändern müssen.

Das sehe ich grundsätzlich auch so. Allerdings mag es gelegentlich Fälle geben, in denen Effizienz aufgrund geringer Datenmengen unwichtig ist. Deshalb fand ich es korrekter, das Kriterium zu nennen. Wenn man mir einen Vergleich ohne dieses Kirterium vorlegen würde, würde ich mich aber auch nicht beklagen.

 

[Meniskusschaden]

Vielleicht noch eine Bemerkung zum praktischen Nutzen von stabilen Sortierverfahren. Wenn man nach mehreren Kriterien sortieren möchte, kann man einen stabilen Sortieralgorithmus einfach mehrmals nacheinander aufrufen, beginnend mit dem unwichtigsten Sortierkriterium. Bei Tabellen, die man per Klick in den Spaltenkopf sortieren kann, kann man als Anwender so eine mehrstufige Sortierung erreichen, obwohl eigentlich nur eine einstufige Sortierung programmiert wurde.

 

[Baldur]

Stimmt, hatte ich nicht dran gedacht. Wäre bei meinem Beispiel mit der Z-Order ggf auch unerwünscht wenn Objekte dauernd die Plätze tauschen würden.
Zum Thema Einfachkeit: Volle Zustimmung.

 

[deggit_biber]

Hallo,
danke für eure vielen Anregungen!
Um ein wenig praktischer zu werden. Was würdet ihr den mit einem Zählen hochzählen lassen, um eine Vergleichbarkeit etwas transparenter zu machen, nur die Vertauschungen oder alle Vergleiche?
viele liebe Grüße,
Deggit

 

[Baldur]

Ich würde beides machen, da beides je nach Datentyp unterschiedlich stark ins Gewicht fallen kann.

Bei Laufzeit kann man noch unterscheiden zwischen der absoluten Anzahl von Vergleichen und der Anzahl der nötigen Schreiboperationen. Je nachdem mit welchen Objekten man arbeitet kann ein compare(a, b) ja auch schon aufwändiger sein und demnach mehr Kosten verursachen als wie bei einfachen Zahlen.

Bei Zahlen ist ein Vergleich billig, bei Strings kann er schon deutlich teurer sein.