Шейкерная сортировка массива

Шейкерная сортировка массивов

Ее так же называют “коктейльная” сортировка или сортировка перемешиванием. Вы когда-нибудь смешивали коктейли в шейкере? Shake – в переводе с английского на русский означает: “встряхивать”. Как же мы сможем встряхнуть массив?

Данная сортировка похожа на пузырьковую, но немного отличается. В сортировке пузырьком мы выдавливали максимумы вверх, как пузырьки, слево-направо. В шейкерной сортировке мы тоже будем выдавливать, но в обе стороны. Сначала мы выдавливаем максимум идя слева-направо, затем разварачиваемся и выдавливаем минимум справа-налево и так пока наш массив не отсортируется полностью.

Давайте рассмотрим пример кода шейкерной сортировки на PHP:

<?php
function swap(&$a, &$b)
    {
        $a = $a ^ $b;
        $b = $a ^ $b;
        $a = $a ^ $b;
    }

function shaker($array)
    {
        $n     = count($array);
        $last  = $n - 1;
        $left  = 1;
        $right = $n - 1;
        do
            {
                for($j = $right; $j >= $left; $j--)
                    {
                        if ($array[$j - 1] > $array[$j])
                            {
                                swap($array[$j - 1], $array[$j]);
                                $last = $j;
                            }
                    }

                $left = $last + 1;
                for($j = $left; $j <= $right; $j++)
                    {
                        if ($array[$j - 1] > $array[$j])
                            {
                                swap($array[$j - 1], $array[$j]);
                                $last = $j;
                            }
                    }

                $right = $last-1;
            } while($left < $right);

        return $array;
    }

$array = [1, 2, 5, 6, 7, 4, 3, 8, 9, 0];
print_r($array);

$array = shaker($array);
print_r($array);
?>

Результат выполнения кода:

Array
(
    [0] => 1
    [1] => 2
    [2] => 5
    [3] => 6
    [4] => 7
    [5] => 4
    [6] => 3
    [7] => 8
    [8] => 9
    [9] => 0
)
Array
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 5
    [5] => 4
    [6] => 6
    [7] => 7
    [8] => 8
    [9] => 9
)

Как видите задача весьма простая и работает данный метод быстрее сортировки пузырьком. так как мы сразу выдавливаем и максимумы и минимумы в обе стороны. Глядя на этот пример можно смело сказать, что программирование – это творческая работа.

Подпишитесь на рассылку новых статей

Подпишитесь на рассылку свежих статей и присоединяйтесь к 7 остальным подписчикам.