Cocktail-Shaker-Sortierung – Schüttlersortierung, eine Variante der bidirektionalen Blasensortierung.
Der Algorithmus funktioniert wie folgt:
- Die anfängliche Suchrichtung in der Schleife wird ausgewählt (normalerweise von links nach rechts)
- Als nächstes werden in der Schleife die Zahlen paarweise überprüft
- Wenn das nächste Element größer ist, werden sie vertauscht
- Wenn der Suchvorgang abgeschlossen ist, beginnt er erneut mit umgekehrter Richtung
- Die Suche wird wiederholt, bis keine Permutationen mehr vorhanden sind
Die zeitliche Komplexität des Algorithmus ist ähnlich wie bei einer Blase – O(n2).
Beispiel für die Implementierung in PHP:
<?php
function cocktailShakeSort($numbers)
{
echo implode(",", $numbers),"\n";
$direction = false;
$sorted = false;
do {
$direction = !$direction;
$firstIndex = $direction == true ? 0 : count($numbers) - 1;
$lastIndex = $direction == true ? count($numbers) - 1 : 0;
$sorted = true;
for (
$i = $firstIndex;
$direction == true ? $i < $lastIndex : $i > $lastIndex;
$direction == true ? $i++ : $i--
) {
$lhsIndex = $direction ? $i : $i - 1;
$rhsIndex = $direction ? $i + 1 : $i;
$lhs = $numbers[$lhsIndex];
$rhs = $numbers[$rhsIndex];
if ($lhs > $rhs) {
$numbers[$lhsIndex] = $rhs;
$numbers[$rhsIndex] = $lhs;
$sorted = false;
}
}
} while ($sorted == false);
echo implode(",", $numbers);
}
$numbers = [2, 1, 4, 3, 69, 35, 55, 7, 7, 2, 6, 203, 9];
cocktailShakeSort($numbers);
?>Ссылки
Источники
https://www.youtube.com/watch?v=njClLBoEbfI
https://www.geeksforgeeks.org/cocktail-sort/
https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort
