Simplesort

Simplesort ist ein stabiles in-place Sortierverfahren. In seiner einfachsten Form hat Simplesort für ein Array der Länge n in der Landau-Notation einen Zeit-Aufwand von O(n²). Simplesort zeichnet sich durch einen besonders einfachen Algorithmus aus.

Die intuitive Idee hinter Simplesort ist, dass man die Positionen im zu sortierenden Arrays nacheinander betrachtet und das jeweils passende Element einsortiert.

Algorithmus

In der folgenden Algorithmusbeschreibung ist x das zu sortierende Array und N dessen Länge.

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

Quellen

"Big Java, by Cay Horstmann"

Weblinks

Folien der Algorithmen und Datenstrukturen Vorlesungen für die MATSE-Ausbildung