Links-Rechts-Links-Rechts
Während in Bubblesort die großen Zahlen des Arrays sehr schnell nach hinten durchgereicht werden, wandern kleine Zahlen mit jeder Iteration nur einen Schritt nach links. Das macht das Verfahren ineffizient.
Betrachten Sie die Bubblesort-Variante in diesem Video:
Sie versucht, die obige Schwäche zu beheben indem abwechselnd Links- und Rechtsdurchläufe durch die Daten durchgeführt werden. So können sowohl kleine Werte schnell nach vorne wandern als auch große Werte schnell nach hinten.
- Implementieren Sie das Verfahren. Merken Sie ständig die linke und rechte Unter- / Obergrenze an der der letzte Tausch stattgefunden hat. So wissen Sie, wie weit der nächste Links- / Rechtsdurchlauf laufen müssen.
- Schätzen Sie die Worst-Case-Komplexität ab: Erzielt das neue Sortierverfahren eine besser Komplexität als die quadratische Komplexität des Orignal-Bubblesort? Begründen Sie.
package de.hsrm.ads;
public class CocktailShakerSort {
public static void sort(int[] a) {
// FIXME: implement
}
}
Subato
