Diskussion:Gnomesort

das gleiche wie bublesort?

ist das nicht das gleiche wie Bubblesort? --AMan 16:03, 5. Jan 2006 (CET)

Nein, Bei bubblesort wird die Liste solange KOMPLETT durchgegangen und benachbarte Elemente vertauscht, bis bei einem Durchlauf nichts mehr vertauscht wird. Gnomesort geht nach Vertauschungen wieder um eins zurück.

Implementierungen

Hallo,

irgendwie bin ich mit dem Artikel nicht ganz glücklich: Er besteht größtenteils aus unkommentierten Implementierungen in verschiedensten Programmiersprachen. Wenn dann noch so Ungereimtheiten wie völlig unterschiedlichen Umsetzungen in C und C++ erscheinen (die völlig unbegründet sind, weil der gezeigte C-Algorithmus auch mit einem C++-Compiler kompiliert läuft), unterstützt das solche Edits nur in der Grundaussage, dass hier kein enzyklopädischer Wert gesammelt wurde.

Was also nötig wäre: Code-Beispiele erläutern, erklären, warum es in einigen Sprachen weniger "Text" bedarf, in anderen dafür (letztendlich) effizienter läuft. Redundante Teile weglassen (C++/C), ggf. sprachspezifische Möglichkeiten einbauen, etc. pp. - Sinnvoll ist das alles jedoch wenig, weisen doch schon die Artikel von C & Co. auf die Vor- und Nachteile der Sprachen hin.

Was also sinnvoll wäre: Auslagerung nach Wikisource oder ähnliches

Grüße,

Sven

Den Algorithmus in tausenden unterschiedlichen Sprachen durchzuexerzieren finde ich weder erhellend, noch einer Enzyklopädie angemessen. Zum Verständnis des Algorithmus trägt das absolut nichts bei. Sinnvoller fände ich eine Animation, die den Algorithmus illustrieren und damit einen echten Beitrag zum dessen Verständnis leisten würde -- Georg-Johann 16:37, 21. Okt. 2008 (CEST)

Komplexität

Mag mal jemand die Komplexität des Algorithmus untersuchen? (: --Philipp Kern 16:09, 7. Okt. 2007 (CEST)

Autor des Algorithmus

Laut Dick Brune wurde der Algorithmus nicht zuerst von ihm vorgestellt: http://dickgrune.com/Programs/gnomesort.html (nicht signierter Beitrag von 109.91.53.236 (Diskussion) 21:20, 4. Okt. 2011 (CEST))

Fehler bei "Vergleich"

Im Abschnitt "Vergleich" heißt es (Zitat): "Dadurch ist Gnomesort oft schneller als Bubblesort, aber zum Beispiel im Worst-Case einer rückwärts sortierten Liste hat Bubblesort weniger Vergleiche als Gnomesort."

Tut mir wirklich leid wenn ich Euch das jetzt sagen muss, aber das ist falsch. Beide Sortierverfahren sind im "Worst-Case"-Fall zu 100% gleich schnell und benötigen identisch viele Vergleiche und identisch viele Vertauschungen von Zahlen.

Zahlen	Bubblesort	Gnomesort
10	Vergleiche: 90 Vertauschungen: 45	Vergleiche: 90 Vertauschungen: 45
100	Vergleiche: 9900 Vertauschungen: 4950	Vergleiche: 9900 Vertauschungen: 4950
1000	Vergleiche: 999.000 Vertauschungen: 499.500	Vergleiche: 999.000 Vertauschungen: 499.500
10.000	Vergleiche: 99.990.000 Vertauschungen: 49.995.000	Vergleiche: 99.990.000 Vertauschungen: 49.995.000

Ansonsten ist Gnomesort aber in der Tat schneller als Bubblesort. Schließlich rutschen einzelne Zahlen im Array nach vorne zu ihrer endgültigen Position. --77.21.185.91 17:36, 17. Jan. 2019 (CET)

Fehler in der Animation

Die Animation stellt die Funktionsweise leider nicht richtig dar, weil sich der gelbe Balken immer nur nach links bewegt, wenn Werte verschoben werden. Er müsste aber auf Position 1 beginnen und auch nach rechts laufen können. --77.21.163.85 17:43, 21. Feb. 2021 (CET)

Die Animation wurde um den Hinweis ergänzt, dass es hier nur um die Bewegungen der Elemente geht, aber nicht um die Vergleiche zwischen den Elementen. --31.17.34.192 16:39, 12. Jun. 2022 (CEST)

Meine Änderungen am Artikel

Ich habe mir mal erlaub ein paar Fehler im Abschnitt "Vergleich" zu korrigieren.

- Im Vergleich zu Bubblesort steigen die Blasen nur sehr langsam auf, aber dafür zusätzlich ab.

Die Blasen steigen nicht sehr langsam auf, sondern genauso schnell. Nur wenn Werte nach vorne verschoben werden, ist die Geschwindigkeit des Aufsteigens langsamer. Bei Bubblesort können die Werte aber ebenfalls absteigen und zwar um eine Position pro Durchlauf des Arrays. Weil die Werte bei Gnomesort mit einer rückwärtslaufenden Schleife nach vorne verschoben werden, bewegen sie sich verständlicherweise n * Position im Array Mal schneller nach vorne, als bei Bubblesort.

- Dadurch ist Gnomesort oft schneller als Bubblesort, aber zum Beispiel im Worst-Case einer rückwärts sortierten Liste hat Bubblesort weniger Vergleiche als Gnomesort.

Wie ich es bereits am 17. Januar 2019 im Diskussionspunkt Fehler bei "Vergleich" erklärt habe, ist die Anzahl der Vergleiche und Vertauschungen bei Gnomesort immer identisch mit der von Bubblesort. Und mit Ausnahme des Best- und Worst-Case, wo die Geschwindigkeiten identisch sind, ist Gnomesort grundsätzlich immer schneller als Bubblesort und zwar um etwa 41% (Tests mit 40.000 gemischten Zahlen, in einem Excel-Makro). Von oft schneller kann also keine Rede sein. --77.21.163.85 21:38, 22. Feb. 2021 (CET)

Codebeispiel

Mir ist aufgefallen, dass es hier noch kein Codebeispiel gibt. Im Internet gibt es zwar viele Varianten, aber bei fast allen gibt es das Problem, dass sie Fehler enthalten und gleich beim Start auf die Position A(-1) zugreifen, was zum Absturz führt. Daher hier für Euch meine Lösung:

Sub Gnomesort()
L = 0
R = Length(A)
POS = L
Do
If A(POS) > A(POS + 1) Then
    Swap A(POS) And A(POS + 1)
    If L < POS Then POS = POS - 1
Else
    POS = POS + 1
End If
Loop Until POS = R
End Sub

--31.17.34.192 14:54, 10. Apr. 2022 (CEST)