Simplesort

Simplesort ist ein nicht stabiles In-place-Sortierverfahren, das dem Selectionsort ähnelt. Simplesort hat für ein Array der Länge n in der Landau-Notation einen Zeit-Aufwand in O(n²). Simplesort ist ein besonders einfacher Algorithmus.

Die intuitive Idee hinter Simplesort ist, dass man die Positionen im zu sortierenden Array nacheinander betrachtet (äußere Schleife) und das jeweils dorthin gehörende Element sucht (innere Schleife) und dort einsortiert. Das gleiche Prinzip nutzt Selectionsort, aber bei Simplesort kann es je Position, die in der äußeren Schleife betrachtet wird, mehrere Vertauschungen von zwei Elementen geben, bis das richtige Element an dieser Position steht. Selectionsort ermittelt erst den Index des richtigen Elements und macht dann nur eine Vertauschung, um es an seinen Platz zu setzen.

Algorithmus

myArray ist das zu sortierende Array (Indizes von 1 bis N).

Schleife über zielPos = 1 .. N-1
{
  // Suche kleinere Elemente im nachfolgenden, noch unsortieren Bereich:
  Schleife über pruefPos = zielPos+1 .. N
  {
    Falls myArray[pruefPos] < myArray[zielPos] dann
    {
      Vertausche myArray[pruefPos] mit myArray[zielPos]
    }
  }
}

Erklärung

Die Elemente werden hier aufsteigend sortiert. Im ersten äußeren Schleifendurchlauf ist zielPos = 1, also die erste Position in myArray. Die innere Schleife prüft nun alle nachfolgenden Positionen in myArray (pruefPos von zielPos+1 bis N), ob dort ein kleinerer Wert als an zielPos steht, und wenn ein solcher gefunden wird, dann wird er mit Position zielPos getauscht. Sollte in der inneren Schleife später ein noch kleinerer Wert gefunden werden, so wird dieser an die Position zielPos getauscht, und der dortige kleinere Wert landet wieder weiter hinten. Schließlich steht der kleinste Wert ganz vorne an zielPos = 1.

In der nächsten Iteration der äußeren Schleife wird die zweite Position im Array betrachtet: zielPos = 2. Im Bereich dahinter (3 bis N) wird nun ein kleineres Element gesucht und ggfs. an Position 2 gesetzt. Die beiden kleinsten Werte stehen dann an ihrer endgültigen Position.

Der fertig sortierte Anfangsbereich des Arrays vergrößert sich mit jedem Durchlauf der äußeren Schleife um eins, bis das Array komplett sortiert ist.

Es ist ebenso gut möglich, die Laufrichtungen der Schleifen umzukehren. Wenn die äußere Schleife absteigt, dann muss das jeweils größte Element im verbleibenden unsortierten Bereich (1 bis zielPos-1) gesucht werden.

Weblinks

• Simplesort auf sortieralgorithmen.de