Diskussion:Simplesort

alte Frage 'Bubblesort'

Ok, und wieso ist das ding jetzt anders als bubblesort?

Dieser Abschnitt kann archiviert werden. arilou (Diskussion) 10:30, 2. Jan. 2019 (CET)

Besser gefragt... wo ist der Unterschied zu Selectionsort?

Also bei Bubblesort werden immer 2 direkt aufeinanderfolgende Elemente vertauscht.

Hier aber wird immer eine Position festgehalten und nachfolgende Elemente werden dort hingetauscht,wenn sie kleiner sind.

Das entspricht eigentlich dem Vorgehen bei Selectionsort,

nur dass hierbei statt das Minimum zu suchen und dann nur einmal zu tauschen,

immer getauscht wird, wenn ein darauffolgendes Element kleiner ist (wenn es also das bisher Kleinste bekannte ist).

Das führt aber dazu, dass zuletzt (wie bei Selectionsort) immer das Minimum der restlichen Elemente an die festgehaltene Position getauscht wird.

Der Unterschied ist also der, dass man sich bei Simplesort hier die Minimumvariable(oder Minindexvariable) spart,

mit dem Nachteil, dass im schlimmsten Fall in jedem Schritt (der inneren Schleife) getauscht werden muss.

Kleine Modifikation ergibt Selectionsort:

 Schleife über Position = 1 .. N
 {
   minIndex = Position;       
   Schleife über Position' = Position + 1 .. N
   {
     Falls x[minIndex] > x[Position'] ...
     {
       ...dann setze: minIndex = Position'       
     }      
   }
   Vertausche x[Position] und x[minIndex]
 }

Vielleicht sollte man die Parallelen zu Selectionsort besser herausarbeiten oder zumindestens erwähnen.

Gruß -Stefan-

Einfacher als Selectionsort, schneller als Bubblesort

Das es Aehnlichkeiten mit Selection sort hat, stimmt. Aber mit ein paar kleine Aenderungen laueft es wesentlich schneller als Bubble sort (fast so schnell wie Selection sort) und es ist viel einfacher zu merken z.B. fuer Schueler. Die bessere code ist (1. Element hat index 0):

 Simplesort (Array A, Integer len)
 {
   for X = 0 to len-2 {
     for Y = len-1 downto X+1 {
        if A[Y] < A[X] then Swap (A[X], A[Y])
     }
   }
 } 

Keine temporaere Variabelen, einfach so. Deshalb glaube ich dass Simple sort eigenlich nicht untergebuttert werden darf unter Selection sort.

- Hans (nicht signierter Beitrag von 82.95.228.79 (Diskussion) 21:08, 14. Dez. 2015 (CET))