Четно-нечетная (чет-нечет) сортировка массива

Четно-нечетная сортировка массива

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

Сначала чет-нечет, потом нечет-чет, и так пока мы не отсортируем наш массив полностью.

К моему удивлению я не нашел хороших рабочих реализаций данного алгоритма сортировки массивов на популярных языках программирования и написал эту реализацию сам.

Пример кода сортировки чет-нечет на PHP:

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

function evenOddSort($array)
    {
        for($i = 0; $i < count($array); $i++)
            {
                if ($i % 2 === 0)
                    {
                        for($j = 2; $j < count($array); $j = $j + 2)
                            {
                                if ($array[$j] < $array[$j - 1])
                                    {
                                        $temp          = $array[$j];
                                        $array[$j]     = $array[$j - 1];
                                        $array[$j - 1] = $temp;
                                    }
                            }
                    }
                else
                    {
                        for($j = 1; $j < count($array); $j = $j + 2)
                            {
                                if ($array[$j] < $array[$j - 1])
                                    {
                                        $temp          = $array[$j];
                                        $array[$j]     = $array[$j - 1];
                                        $array[$j - 1] = $temp;
                                    }
                            }
                    }
             }
        return $array;
    }

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

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

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

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

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

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