Нечетно-четная сортировка - Odd–even sort

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

Пример нечетно-четной перестановки сортировки списка случайных чисел.
Класс	Алгоритм сортировки
Структура данных	Массив
Худший случай спектакль	${displaystyle O (n ^ {2})}$
Лучший случай спектакль	${displaystyle O (n)}$
Худший случай космическая сложность	${displaystyle O (1)}$

В вычислениях нечетная – четная сортировка или нечетно-четная перестановка (также известен как кирпич сортировать^{[1][самостоятельно опубликованный источник ]} или сортировка по четности) является относительно простым алгоритм сортировки изначально разрабатывался для использования на параллельных процессорах с локальными соединениями. Это сортировка сравнения относится к пузырьковая сортировка, с которым он имеет много общих характеристик. Он работает, сравнивая все нечетные / четные индексированные пары смежных элементов в списке, и, если пара находится в неправильном порядке (первая больше, чем вторая), элементы меняются местами. На следующем шаге это повторяется для пар четных / нечетных индексов (соседних элементов). Затем он чередует нечетные / четные и четные / нечетные шаги, пока список не будет отсортирован.

Сортировка по массивам процессоров

На параллельных процессорах, с одним значением на процессор и только локальными соединениями между левым и правым соседями, все процессоры одновременно выполняют операцию сравнения-обмена со своими соседями, чередуя пары нечетно-четный и четно-нечетный. Этот алгоритм был первоначально представлен и показал свою эффективность на таких процессорах Хаберманом в 1972 году.^[2]

Алгоритм эффективно распространяется на случай нескольких элементов на процессор. В алгоритме разделения слиянием нечетных и четных Боде – Стивенсона каждый процессор сортирует свой собственный подсписок на каждом шаге, используя любой эффективный алгоритм сортировки, а затем выполняет операцию разделения слияния или транспонирования-слияния со своим соседом, при этом соседние пары чередуются. между нечетно-четным и четно-нечетным на каждом шаге.^[3]

Сортировка нечетных и четных слиянием Батчера

Связанный, но более эффективный алгоритм сортировки - это Сортировка по четным и нечетным дозаторам, используя операции сравнения-обмена и операции перетасовки.^[4]Метод Батчера эффективен на параллельных процессорах с соединениями на большие расстояния.^[5]

Алгоритм

Однопроцессорный алгоритм, например пузырьковая сортировка, это просто, но не очень эффективно. Здесь с нуля предполагается индекс:

функция oddEvenSort(список) {  функция своп(список, я, j) {    вар темп = список[я];    список[я] = список[j];    список[j] = темп;  }  вар отсортированный = ложный;  в то время как (!отсортированный) {    отсортированный = правда;    для (вар я = 1; я < список.длина - 1; я += 2) {      если (список[я] > список[я + 1]) {        своп(список, я, я + 1);        отсортированный = ложный;      }    }    для (вар я = 0; я < список.длина - 1; я += 2) {      если (список[я] > список[я + 1]) {        своп(список, я, я + 1);        отсортированный = ложный;      }    }  }}

Доказательство правильности

Заявление: Пусть ${displaystyle a_ {1}, ..., a_ {n}}$ быть последовательностью данных, упорядоченной <. Алгоритм нечетно-четной сортировки правильно сортирует эти данные в ${displaystyle n}$ проходит. (Под проходом здесь подразумевается полная последовательность нечетно-четных или четно-нечетных сравнений. Проходы выполняются в следующем порядке: проход 1: чет-нечет, проход 2: чет-нечет и т. Д.)

Доказательство:

Это доказательство частично основано на доказательстве Томаса Уорша.^[6]

Поскольку алгоритм сортировки включает только операции сравнения-обмена и не принимает во внимание (порядок операций сравнения-обмена не зависит от данных), согласно принципу сортировки Кнута 0–1,^[7][8] достаточно проверить правильность, когда каждый ${displaystyle a_ {i}}$ равно 0 или 1. Предположим, что есть ${displaystyle e}$ 1с.

Обратите внимание, что крайняя правая единица может быть как в четной, так и в нечетной позиции, поэтому она не может быть перемещена при первом нечетно-четном проходе. Но после первого нечетно-четного паса крайняя правая 1 будет в четной позиции. Отсюда следует, что он будет перемещен вправо всеми оставшимися проходами. Так как крайний правый начинается в позиции больше или равной ${displaystyle e}$, его нужно переместить самое большее ${displaystyle n-e}$ шаги. Отсюда следует, что требуется не более ${displaystyle n-e + 1}$ проходит, чтобы переместить крайнюю правую единицу в правильное положение.

Теперь рассмотрим вторую крайнюю правую цифру 1. После двух проходов цифра 1 справа сдвинется вправо как минимум на один шаг. Отсюда следует, что для всех оставшихся проходов мы можем рассматривать вторую крайнюю правую 1 как крайнюю правую 1. Вторая крайняя правая 1 начинается с позиции по крайней мере ${displaystyle e-1}$ и должен быть перемещен в позицию не более ${displaystyle n-1}$, поэтому его нужно переместить не более ${displaystyle (n-1) - (e-1) = n-e}$ шаги. После максимум 2 проходов крайний правый 1 уже будет перемещен, поэтому запись справа от второго крайнего правого 1 будет 0. Следовательно, для всех проходов после первых двух, второй крайний правый 1 будет перемещаться вправо. Таким образом, требуется не более ${displaystyle n-e + 2}$ проходит, чтобы переместить вторую крайнюю правую единицу в правильное положение.

Продолжая таким образом, по индукции можно показать, что ${displaystyle i}$-й крайний правый 1 перемещается в правильное положение не более чем в ${displaystyle n-e + i}$ проходит. поскольку ${displaystyle ileq e}$, следует, что ${displaystyle i}$-й крайний правый 1 перемещается в правильное положение не более чем в ${displaystyle n-e + e = n}$ проходит. Таким образом, список правильно отсортирован по ${displaystyle n}$ проходит. QED.

Отметим, что каждый проход занимает ${displaystyle O (n)}$ шагов, поэтому этот алгоритм ${displaystyle O (n ^ {2})}$ сложность.

использованная литература