Сортировка чёт-нечет

Чёт-нечётная сортировка
Чёт-нечётная сортировка
	англ. Odd-even sort
Область использования	Сортировка данных, параллельные вычисления
Ключевые слова	сортировка сравнением, транспозиционная сортировка, кирпичная сортировка
Базовые понятия	сравнение, обмен, чётная фаза, нечётная фаза

Чёт-нечётная сортировка
Чёт-нечётная сортировка
	англ. Odd-even sort
Область использования	Сортировка данных, параллельные вычисления
Ключевые слова	сортировка сравнением, транспозиционная сортировка, кирпичная сортировка
Базовые понятия	сравнение, обмен, чётная фаза, нечётная фаза

Сортиро́вка чёт-не́чет — относительно простой алгоритм алгоритм сортировки, разработанный для использования на параллельных процессорах, является модификацией пузырьковой сортировки. Суть модификации в том, чтобы сравнивать элементы массива под чётными и нечётными индексами с последующими элементами независимо. Алгоритм был впервые представлен Н. Хаберманом (N. Haberman) в 1972 году.

Заводится флаг, определяющий, отсортирован ли массив. В начале итерации ставится в состояние «истина», далее каждый нечётный элемент сверяется с последующим, и, если они стоят в расположены в неправильном порядке (предыдущий больше следующего), элементы меняются местами, и флаг ставится в состояние «ложь». То же самое делается с чётными элементами. Алгоритм не прекращает работу, пока флаг не останется в состоянии «истина».

Программная реализация чёт-нечётной сортировки базируется на двух подходах к управлению итерациями:

Фиксированное число проходов. Количество итераций жёстко ограничивается размером массива ( $n$ ). Данный метод гарантирует упорядочивание данных в худшем случае, упрощает код и анализ временной сложности. Он используется в приведённых реализациях на C++ и JavaScript. В наихудшем и среднем случаях сложность составляет $O(n^{2})$ сравнений и перестановок^[1].

Адаптивный проход с флагом оптимизации. Выполнение цикла продолжается до тех пор, пока на очередной итерации (чётной и нечётной) происходит хотя бы один обмен элементов. Наличие флага sorted (как в примере на PHP) позволяет досрочно завершить алгоритм, если исходный массив изначально упорядочен или близок к этому состоянию. В лучшем случае (для уже отсортированного массива) сложность снижается до $O(n)$ ^[2].

В последовательном режиме сложность подходов различается:

Фиксированное число проходов (C++/JS) всегда даёт $\Theta (n^{2})$ сравнений и перестановок, поскольку число итераций не зависит от начальной упорядоченности данных^[3].
Адаптивный подход с флагом sorted (PHP) в худшем случае требует $O(n^{2})$ операций, а в лучшем (если массив уже отсортирован) — $O(n)$ , так как алгоритм завершается после первого же прохода ^[3].

В параллельной архитектуре при наличии $n$ независимых вычислительных узлов алгоритм может быть выполнен за $O(n)$ шагов^[4]. Более эффективная параллельная версия — сортирующая сеть Батчера (Batcher’s odd-even mergesort) — достигает параллельного времени $O(\log ^{2}n)$ ^[2]^[5].

template < typename T, size_t N >
void oddEvenSorting(T (&array)[N]) {
	for (size_t i = 0; i < N; i++) {
	   // (i % 2) ? 0 : 1 возвращает 0, если i нечётное, 1 — если чётное
		for (size_t j = (i % 2) ? 0 : 1; j + 1 < N; j += 2) {
			if (array[j] > array[j + 1]) {
				std::swap(array[j], array[j + 1]);
			}
		}
	}
}

function oddEvenSorting(array) {
    const arrayLength = array.length; //длина массива
	for (let i = 0; i < arrayLength; i++) {
	   // (i % 2) ? 0 : 1 возвращает 0, если i нечётное, 1 — если чётное
		for (let j = (i % 2) ? 0 : 1; j < arrayLength - 1; j += 2) {
			if (array[j] > array[j + 1])
				[array[j], array[j + 1]] = [array[j + 1], array[j]]; //swap
		}
    }
    return array;
}

function oddEvenSort(array &$arr): void {
    $n = count($arr);
    $sorted = false;
    
    while (!$sorted) {
        $sorted = true;
        
        // Нечётная фаза: сравниваем пары (1,2), (3,4), (5,6), ...
        for ($i = 1; $i < $n - 1; $i += 2) {
            if ($arr[$i] > $arr[$i + 1]) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$i + 1];
                $arr[$i + 1] = $temp;
                $sorted = false;
            }
        }
        
        // Чётная фаза: сравниваем пары (0,1), (2,3), (4,5), ...
        for ($i = 0; $i < $n - 1; $i += 2) {
            if ($arr[$i] > $arr[$i + 1]) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$i + 1];
                $arr[$i + 1] = $temp;
                $sorted = false;
            }
        }
    }
}

	// for ($x = 0; $x < $lengthArray; $x++) { 
	// 	if (!$sorted) {
	// 		$sorted = true;
	// 		for ($i = 0; $i < $lengthArray - 1; $i += 2) {
	// 			if ($array[$i] > $array[$i + 1]) {
	// 				FunctionSwapVariables($array[$i], $array[$i + 1]);
	// 				$sorted = false;
	// 			}
	// 		}
	// 		for ($i = 1; $i < $lengthArray - 2; $i += 2) {
	// 			if ($array[$i] > $array[$i + 1]) {
	// 				FunctionSwapVariables($array[$i], $array[$i + 1]);
	// 				$sorted = false;
	// 			}
	// 		}
	// 	} else return 'Массив успешно отсортирован';
	// }
}

↑ Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. — 2-е изд. — М.: Вильямс, 2000. — С. 120–125.
↑ ¹ ² Algorithms and Applications // San Jose State University
↑ ¹ ² Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 2-е изд. — М.: Вильямс, 2011. — Глава 27 «Сортирующие сети», раздел 27.5 и задача 27-2.
↑ Odd-Even Transposition Sort (OETS) // MobyLab. URL: https://mobylab.docs.crescdi.pub.ro/en/docs/parallelAndDistributed/laboratory3/oddEvenTranspositionSort/
↑ Parallel algorithms on sequences and strings // Carnegie Mellon University

Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. — 2-е изд. — М.: Вильямс, 2000. — 832 с. — ISBN 978-5-8459-0082-1.
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 2-е изд. — М.: Вильямс, 2011. — 1296 с. — ISBN 978-5-8459-0857-5. (Глава 27 «Сортирующие сети», раздел 27.5 и задача 27-2.)
Habermann, N. (1972). Parallel Neighbor Sort (or the Glory of the Induction Principle). CMU Computer Science Report. Technical Report AD-759 248, National Technical Information Service, US Department of Commerce.
Batcher, K. E. (1968). Sorting networks and their applications. Proceedings of the AFIPS Spring Joint Computer Conference, 32, 307—314.
Алгоритмы и приложения (конспект лекций) // San Jose State University. (дата обращения: 30.08.2026).
Odd-Even Transposition Sort (OETS) // MobyLab. (дата обращения: 30.08.2026).
Parallel algorithms on sequences and strings // Carnegie Mellon University. (дата обращения: 30.08.2026).

[knuth-1] Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. — 2-е изд. — М.: Вильямс, 2000. — С. 120–125.

[sjsu-2] ¹ ² Algorithms and Applications // San Jose State University

[cormen-3] ¹ ² Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 2-е изд. — М.: Вильямс, 2011. — Глава 27 «Сортирующие сети», раздел 27.5 и задача 27-2.

[4] Odd-Even Transposition Sort (OETS) // MobyLab. URL: https://mobylab.docs.crescdi.pub.ro/en/docs/parallelAndDistributed/laboratory3/oddEvenTranspositionSort/

[5] Parallel algorithms on sequences and strings // Carnegie Mellon University

[1]

[2]

[3]

[4]

[5]

Алгоритмы сортировки
Теория	Сложность О-нотация Отношение порядка Типы сортировки Устойчивая Внутренняя Внешняя
Обменные	Пузырьком Перемешиванием Гномья Быстрая Расчёской Сортировка чёт-нечет Поразрядная
Выбором	Выбором Пирамидальная Плавная
Вставками	Вставками Шелла Деревом
Слиянием	Слиянием
Без сравнений	Подсчётом Блочная
Гибридные	Introsort Timsort
Прочее	Топологическая Сети Битонная
Непрактичные	Bogosort Stooge sort Блинная Медленная

Сортировка чёт-нечет

Описание алгоритма

Реализации на языках программирования

Реализация на C++

Реализация на JavaScript

Реализация на PHP

Примечания

Литература

Дополнительно по теме

Категории