Odd-Even Sort
Odd-Even Sort — сортировка "кирпичиками": чередует нечётные и чётные пары соседей и меняет их местами при необходимости.
Основная идея
На каждой итерации обрабатываются сначала нечётные пары (1-2, 3-4, ...), затем чётные (0-1, 2-3, ...). Цикл повторяется, пока массив не отсортирован.
Пошаговый пример
Исходный массив:
[6, 3, 8, 1, 5, 2]- Нечётная фаза: сравниваем пары (1,2), (3,4), ...
- Чётная фаза: сравниваем пары (0,1), (2,3), ...
- Повторяем, пока на проходе не было ни одного обмена
Псевдокод
sorted = false
while not sorted:
sorted = true
for i in 1, 3, 5, ... (odd):
if arr[i] > arr[i + 1]:
swap; sorted = false
for i in 0, 2, 4, ... (even):
if arr[i] > arr[i + 1]:
swap; sorted = false
Оптимизация: Хорошо параллелится: пары в каждой фазе независимы.
Сложность
Время
O(n²) в среднем и худшем случае.
Память
O(1), in-place.
Когда используется
- Параллельные вычисления
- Учебные демонстрации
- Маленькие массивы
Ключевые свойства
- Стабильный
- In-place
- Хорошо распараллеливается
Комментарии к уроку
Войдите, чтобы оставить комментарий.
Пока нет комментариев — будьте первым.