Swap-Sort
# Swap-Sort

Swap-Sort ist ein Sortieralgorithmus, der ein Array aus paarweise verschiedenen Zahlen sortiert.

## Idee

Die Idee von Swap-Sort ist, von jedem Element eines Arrays A(1…n) die Anzahl m der kleineren Werte (die in A sind) zu zählen und das Element dann mit dem Element in A(m+1) zu vertauschen. Somit ist sichergestellt, dass das ausgetauschte Element bereits an der richtigen, also endgültigen Stelle steht.

Nachteil dieses Algorithmus ist, dass jedes Element nur einmal vorkommen darf, da sonst keine Terminierung erfolgt.

## Prinzip

A ist ein Array mit n Elementen. Swap-Sort arbeitet in folgenden Schritten:

* Beginne mit i = 1
* Zähle, wie viele Elemente kleiner als A(i) sind, m sei diese Anzahl. Tausche danach A(i) mit A(m+1)
* Ist i = m+1, so erhöhe i um 1
* Ist i = n, so ist die Sortierung beendet. Andernfalls gehe wieder zu Schritt 2.

## Beispiel

Es soll ein Array mit dem Inhalt {7,8,5,2,4,9,3,1} sortiert werden.

## Komplexität

Für die Bestimmung der Anzahl kleinerer Einträge ist ein vollständiger Array-Durchlauf nötig. Ein solcher muss für jedes Element des Arrays durchgeführt werden. Es ergibt sich eine Komplexität von ${\mathcal {O}}(n^{2})$.

