Bubblesort

Häufig möchte man Daten der Größe nach sortieren. Hierfür gibt es verschiedene Sortierverfahren. Ein bekanntes, einfaches, aber auch langsames Verfahren ist Bubblesort. Liegen die zu sortierenden Daten in einem Array der Länge n vor und sollen die Daten aufsteigend sortiert werden, so wird in einer sogenannten Bubble-Phase das Array vom 1 'ten bis zum n-1 'ten Element durchlaufen. Dabei wird in jedem Schritt das aktuelle Element an der Stelle i mit dem nachfolgenden Element an der Stelle i+1 verglichen. Ist das Element an der Stelle i größer als das Element an der Stelle i+1, so vertauscht man beide Elemente. Hat man so eine Bubble-Phase durchlaufen, ist das größte Element am Ende des Arrays angekommen. Wiederholt man nun eine Bubble-Phase, so steht auch das zweitgrößte Element an der richtigen Stelle. Hat man n-1 Bubble-Phasen durchlaufen, ist das komplette Array sortiert. Um ein Array mit 4 Zahlen zu sortieren, benötigt man also drei Bubble-Phasen:

Erste Bubble-Phase:
[4, 2, 3, 1] -> [2, 4, 3, 1] Das erste Element wird mit dem zweiten verglichen. Sie werden vertauscht, da 4>2 ist.
[2, 4, 3, 1] -> [2, 3, 4, 1] Das zweite Element wird mit dem dritten verglichen. Sie werden vertauscht, da 4>3 ist.
[2, 3, 4, 1] -> [2, 3, 1, 4] Das dritte Element wird mit dem vierten verglichen. Sie werden vertauscht, da 4>1 ist.
Das größte Element ist an die richtige Stelle geblubbert.

Zweite Bubble-Phase:
[2, 3, 1, 4] -> [2, 3, 1, 4] Das erste Element wird mit dem zweiten verglichen. Sie werden nicht vertauscht, da 2<3 ist.
[2, 3, 1, 4] -> [2, 1, 3, 4] Das zweite Element wird mit dem dritten verglichen. Sie werden vertauscht, da 3>1 ist.
[2, 1, 3, 4] -> [2, 1, 3, 4] Das dritte Element wird mit dem vierten verglichen. Sie werden nicht vertauscht, da 3<4 ist.
Das zweitgrößte Element ist an die richtige Stelle geblubbert.

Dritte Bubble-Phase:
[2, 1, 3, 4] -> [1, 2, 3, 4] Das erste Element wird mit dem zweiten verglichen. Sie werden vertauscht, da 2>1 ist.
[1, 2, 3, 4] -> [1, 2, 3, 4] Das zweite Element wird mit dem dritten verglichen. Sie werden nicht vertauscht, da 2<3 ist.
[1, 2, 3, 4] -> [1, 2, 3, 4] Das dritte Element wird mit dem vierten verglichen. Sie werden vertauscht, da 3<4 ist.
Das drittgrößte Element ist an die richtige Stelle geblubbert.
Damit ist automatisch auch das kleinste Element an der richtigen Stelle.
Das Array ist aufsteigend sortiert.

Schreibe eine Funktion sort, die ein mit Zahlen gefülltes Array entgegennimmt und die diese Zahlen aufsteigend sortiert als Array zurückgibt. Wird ein leeres Array übergeben, so soll auch ein leeres Array zurückgegeben werden.

Beispiel: sort([4, 2, 3, 1]) sollte [1, 2, 3, 4] ergeben.