Diskussion:Selectionsort

Eignung

Ich vermisse (wie auch in vielen anderen sortierartikeln) eine kurze betrachtung über die eignung dieses algorithmus. Sicherlich würde man ihn nicht als general-purpose sortierung empfehlen, aber dort wo die vertauschung von elementen gegenüber dem vergleich extrem viel teurer ist wird dieser algorithmus bis zu einer gewissen menge an elementen einiges an besserer performance bringen als sogar z.b. introsort (nicht signierter Beitrag von 217.11.197.10 (Diskussion | Beiträge) 12:19, 14. Sep. 2009 (CEST))

Pseudo-Code

Ich hatte den Pseudo-Code zum Artikel hinzugefügt, welcher wieder gelöscht wurde mit Verweis auf die zahlreichen Code-Beispiele im Artikel. Ich fände es jedoch sinnvoller, dass stattdessen einige der konkreten Implementierungen gelöscht werden und der Pseudo-Code wieder hinzugefügt wird. --Farbing 12:05, 29. Jun. 2007 (CEST)

Mir waere Pseudocode auch lieber. Eher wuerde ich die vielen Programmbeispielen auslagern, z.B. auf einer Unterseite. Diese wurden bei den anderen Sortieralgorithmen irgendwann auch entfernt... Cheers, Pedro.Gonnet 12:36, 29. Jun. 2007 (CEST)

Knuth schreibt in seinem The Art Of Computer Programming, dass Pseudo-Code immer eine schlechte Wahl ist, weil er eine Genauigkeit vorgaukelt, die er nicht erfüllen kann. Seine Antwort darauf heißt, jeden Algorithmus in zwei Sprachen darzustellen, beide Male mit großer Genauigkeit und beide Male verständlich, das eine mal in einer abstrakten Hochsprache, das andere mal in genaustens definierten Maschinensprache. Die Hochsprache ist Englisch. Dem ist nichts hinzuzufügen. Es ist unenzyklopädisch, sich seine Lieblingssyntax auszusuchen, ein paar Schlüsselworte herauszunehmen und das dann "Pseudocode" zu nennen, als wäre es ein etabliertes Konstrukt. Der Artikel braucht tatsächlich nur zwei Versionen des Algorithmus: einmal auf Deutsch, und vielleicht auf Maschinensprache. Die übrigen Implementierungen sind eine zuckersüße Spielerei, die allerdings immerhin mehr nützt als wilkürlich erwählter Pseudocode. (Höre ich Lesbarkeit? Alle diese Sprachen wurden ebender zuliebe erfunden). igel+- 13:56, 30. Jun. 2007 (CEST) 

Ich würde dafür plädieren, dass man sich an den anderen Artikeln zu Sortierverfahren orientiert, auf denen auch nur der Pseudocode vorhanden ist, denn ich finde den auf den ersten Blick leserlicher als eine konkrete Programmiersprache (besonders gegenüber Maschinensprache). --Farbing 18:34, 30. Jun. 2007 (CEST)

Ich kann mir keinen Pseudocode vorstellen, der präziser, knapper oder anschaulicher wäre als

0.upto(list.size-2) do |start|
   min = start
   (start+1).upto(list.size-1) do |i|
     min = i if list[i] < list[min]
   end
   list[start], list[min] = list[min], list[start]
 end

Ein Problem an Pseudocode ist doch immer: welchen wählst du denn? Magst dus lieber mit Schlüsselwörtern? Das ist deine eigene Präferenz, dein POV, gewissermaßen. igel+- 19:12, 30. Jun. 2007 (CEST) 

wie wär es damit?

schleife A von anfang LISTE bis ende LISTE
   setze KLEINSTES auf den wert A
   schleife B von A + 1 bis ende LISTE
      wenn LISTE(B) kleiner als LISTE(KLEINSTES) dann setze KLEINSTES auf den wert B 
   ende schleife B
   vertausche die werte von LISTE(KLEINSTES) und LISTE(A)
ende schleife A

oder Pseudocode

für jedes A in anfang( LISTE ) bis ende( LISTE ) - 1 wiederhole:
   KLEINSTES := A
   für jedes B in A + 1 bis ende( LISTE ) wiederhole:
      falls LISTE[ B ] < LISTE[ KLEINSTES ] dann KLEINSTES := B
   für B ende
   TEMP := LISTE[ KLEINSTES ]
   LISTE[ KLEINSTES ] := LISTE[ A ]
   LISTE[ A ] := TEMP
für A ende

84.168.89.171 14:54, 5. Jul. 2007 (CEST)

Das ist ja hübsch und mich freut wirklich, dass du widerstehen konntest, englische Schlüsselwörter zu benutzen. Ich denke nach wie vor, dass die verständlichste Hochsprache die Muttersprache ist. Es muss deswegen noch nicht prosa sein. Mal sehen, ob wir uns einigen können. Ich modifiziere einmal obiges nach Knuths Muster:

Algorithmus S

Gegeben eine Liste X[1]...X[n]. Wir suchen eine Liste Y[1]...Y[n], die eine Permutation von X[1]...X[n] ist und die sortiert ist, das heißt, dass für i<=j folgt, dass Y[i]<=Y[j].

S1 (Initialisieren.)

Setze i ← n, m ← X[n], k ← n.

S2 (Alles sortiert?)

Falls i = 0, so endet der Algorithmus.

S3 (Minimumssuche initialisieren.)

Setze j ← i

S4 (Alle möglichen Minima geprüft?)

Falls j=0, so gehe zu S9.

S5 (Vergleiche)

Falls X[j] >= m, so gehe zu S8

S6 (Ändere m)

Setze k ← j, m ← X[j] (Dieser Wert von m ist das neue aktuelle Minimum)

S7 (Verringere j)

Verringere j um eins und gehe zu S3.

S8 (Tausche X[i])

Setze t ← X[k], X[k] ← X[i], X[i] ← t. (Vertausche X[i] mit dem aktuellen Minimum m an Position k).

S9 (Verringere i)

Verringere i um eins und gehe zu S2.

Diese Formulierung orientiert sich so gut wie möglich an der Knuth'schen Schreibweise; der macht in Abschnit 1.2.10 etwas ganz ähnliches, nämlich das Maximum suchen. Ich sage ja, Deutsch ist eine gute Hochsprache! igel+- 19:03, 5. Jul. 2007 (CEST)

Ach so, die Kür fehlt ja noch: Alle Veränderungen an X[1]...X[n] geschehen in Schritt S8, der paarweise Vertauschungen vornimmt. Verkettungen von Permutationen bleiben Permutationen, weshalb das am Algorithmusende entstandene X[1]...X[n] eine Permutation des ursprünglichen sein muss. Knuth beweist in seinem Abschnitt 1.2.10, dass S3 bis S7 das Minimum von X[0]...X[i] in m ablegt. Darum wissen wir sicher, dass nach der Vertauschung S8 gilt, dass S[i] < X[p] für alle p > i. Da alle folgenden Vertauschungen rechts von i durchgeführt werden ergibt sich per Induktion, dass am Algorithmusende X[1]...X[n] sortiert sein muss. Der Algorithmus terminiert auch als verschachtelte vollständige Schleife nach O(n^2) Schritten. igel+- 19:03, 5. Jul. 2007 (CEST)

ich dachte immer pseudocode sollte leicht verständlich sein. das ist diese version meiner meinung nach nicht. der unterschied ist, dass du schleifen durch bedingte sprünge ersetzt. in welcher gängigen sprache wird das heute so umgesetzt? mein ziel war es den selectionsort artikel anderen sortierbeiträgen anzugleichen und den wust aus programmiersprachen wegzubekommen. es ist sicher schön einen vergleich zwischen den verschiedenen sprachen zu haben trägt aber nicht umbedingt zum leichten verständniss bei.

übrigens:

S4 (Alle möglichen Minima geprüft?)

Falls j=0, so gehe zu S8.

S5 (Vergleiche)

Falls X[j] >= m, so gehe zu S7.

S7 (Verringere j)

Verringere j um eins und gehe zu S4.

84.168.89.171 19:38, 5. Jul. 2007 (CEST)

S4 stimmt schon, S5 und S7 sind wirklich falsch, Mift. Naja, wie auch immer: Der Vorteil dieser Schreibweise ist, dass sie ohne Schlüsselwörter auskommt. Solche sind nämlich immer willkürlich gewählt und täuschen Genauigkeit vor, die sie nicht halten können. Ich finde Schlüsselwort-Pseudocode ansonsten auch nicht lesbarer als das Ruby oben oder eine prosaische Beschreibung. 217.230.147.84 20:13, 5. Jul. 2007 (CEST)

wenn s4 stimmt, wird niemals etwas vertauscht. der nachteil von bedingten sprüngen gegenüber schleifen ist, das bei änderungen im ganzen code die sprungziele angepasst werden müssen. wir sollten ausserdem versuchen, nichts neues zu erfinden oder anderswo bewährtes hier einzuführen, sondern auf in wikipedia gebräuchliches zurückgreifen.

Öhh, nochmal, das ist eine sachte Modifikation von Knuths Maximum-Findungs-Algorithmus. Viel kanonischer geht es, denke ich, nicht. igel+- 20:24, 5. Jul. 2007 (CEST)

das mag sein, trägt aber nichts zur annäherung an andere sortierartikel bei. wenn wir uns beispielsweise Bubblesort, Quicksort oder Mergesort anschauen, so wird dort die funktionsweise mit Pseudocode erklärt. warum soll das hier anders sein? 84.168.89.171 20:40, 5. Jul. 2007 (CEST)

kann ich deine version so zusammenfassen? (ich habe versucht jeweils nur einen vorgang in eine zeile zu schreiben)

01 A ← elementanzahl(LISTE)	(Setze A auf das Listenende. A bezeichet die grösse der unsortierten Liste)
02 Falls A < 2, so endet der Algorithmus	(Weniger als zwei Elemente kann man nicht sortieren also Ende)
03 KLEINSTES ← A	(Das letze Element der unsortierten Liste als kleinstes annehmen)
04 B ← A - 1	(Beim voletzen Element der unsortierten Liste mit der Suche nach einem kleineren Element beginnen)
05 Falls B = 0, so gehe zu 10	(Ist die unsortierte Liste durchsucht, weiter bei 10)
06 Falls LISTE[B] >= LISTE[KLEINSTES], so gehe zu 08	(Element ist nicht kleiner? weiter bei 08 )
07 KLEINSTES ← B	(Element ist kleiner also aktuelles Element als kleinstes annehmen)
08 B ← B - 1	(Gehe einen Schritt weiter in der unsortierten Liste)
09 gehe zu 05	(Weiter bei 05)
10 LISTE[KLEINSTES] ↔ LISTE[A]	(Vertausche das gefundene Kleinste mit dem letzten Element der unsortierten Liste)
11 A ← A - 1	(Verleinere die unsortierte Liste um ein Element)
12 gehe zu 02	(Weiter bei 02)

84.168.92.213 19:00, 6. Jul. 2007 (CEST)

Varianten: Python

Zur Kombination von MinSuche und MaxSuche eine Verständnisfrage: Warum muss die Anzahl der Elemente in der Sequenz ungerade sein?

Ich habe die Zeilen, die dieses bewirken, auskommentiert, und dennoch korrekte Ergebnisse erhalten.

--Lupussy 11:37, 16. Jun. 2008 (CEST)

Struktogramm

Ich fände es sehr hilfreich wenn zu dem Artikel zusätzlich zum Pseudocode noch ein Nassi-Shneiderman-Diagramm (Struktogramm) des Selectionsort-Algorithmus hinzukäme. Diese sind (für mich jedenfalls) mit ihrer graphischen Gliederung noch intuitiver und schneller zu erfassen als Pseudocode. So wurde das unter anderem auch bei Insertionsort gemacht. Was haltet ihr davon? --Chrisma89 12:04, 7. Okt. 2010 (CEST)

Variante des Algorithmus

Wäre es nicht viel effizienter, bei einem Durchlauf den keinsten und den größten Wert zu ermitteln? Das würde die Geschwindigkeit halbieren. --Piegames (Diskussion) 12:21, 8. Jan. 2015 (CET)

Es halbiert zwar die Schleifendurchläufe, aber gleichzeitig verdoppelt sich die Anzahl der Vergleiche, was dann wieder auf das gleiche herauskommt.--Plankton314 (Diskussion) 12:26, 8. Jan. 2015 (CET)

Stimmt, danke --Piegames (Diskussion) 16:06, 9. Jan. 2015 (CET)

Nunja, wie man aus Loop Unrolling lernt, bringt auch das Reduzieren der Schleifendurchläufe einen Vorteil.

An der grundsätzlichen O(n^2) Komplexität ändert's aber nichts, das ist richtig.

--arilou (Diskussion) 14:02, 17. Mai 2016 (CEST)

Variante: Straight Select Sort, Ripple Sort

Manchmal findet man diese Variante (Min ermitteln, dann tauschen) als STRAIGHT select sort (direktes Austauschen), und direktes Tauschen evtl. gefundener kleinerer Werte als Standard-Verfahren durch Auswählen. Manchmal findet man das direkte Tauschen auch als Riple Sort. Auf jeden Fall sollte die Variante mit direktem Auswählen/Tauschen hier erwähnen. (nicht signierter Beitrag von 217.191.2.245 (Diskussion) 20:48, 8. Feb. 2015 (CET))

Bis zum ersten Komma hab' ich das verstanden. Danach weis ich nicht, wovon du sprichst.

"direktes Tauschen evtl. gefundener kleinerer Werte" hört sich irgendwie nach Bubblesort an? (Zu Ripplesort siehe dort, ist eine Bubblesort-Variante).

--arilou (Diskussion) 10:06, 10. Feb. 2015 (CET)

Gemeint ist vielleicht Simplesort --Megatherium (Diskussion) 12:58, 31. Aug. 2018 (CEST)

Weblink führt zu anderer Seite

• VisuSort Framework – Visualisierung diverser Sortieralgorithmen (Windows)

--78.94.249.41 13:13, 7. Jun. 2021 (CEST)