Нечетно-четный сорт

Информацию о параллельном алгоритме (log n)² / n(log n)² см. в разделе « Сортировка слиянием нечетно-четного Бэтчера» .

Нечетно-четный сорт

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

В вычислительной технике используется сортировка «нечет-чет» или транспонированная сортировка «нечет-чет» (также известная как кирпичная сортировка) . или сортировка по четности ) — относительно простой алгоритм сортировки , изначально разработанный для использования на параллельных процессорах с локальными соединениями. Это сортировка сравнения, связанная с пузырьковой сортировкой , с которой она имеет много общих характеристик. Он работает путем сравнения всех нечетных/четных индексированных пар соседних элементов в списке, и, если пара находится в неправильном порядке (первый больше второго), элементы переключаются. Следующий шаг повторяет это для пар четных/нечетных индексов (соседних элементов). Затем он чередует шаги «нечетный/четный» и «четный/нечетный», пока список не будет отсортирован.

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

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

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

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

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

Алгоритм

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

function oddEvenSort(list) {  function swap(list, i, j) {    var temp = list[i];    list[i] = list[j];    list[j] = temp;  }  var sorted = false;  while (!sorted) {    sorted = true;    for (var i = 1; i < list.length - 1; i += 2) {      if (list[i] > list[i + 1]) {        swap(list, i, i + 1);        sorted = false;      }    }    for (var i = 0; i < list.length - 1; i += 2) {      if (list[i] > list[i + 1]) {        swap(list, i, i + 1);        sorted = false;      }    }  }}

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

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

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

Это доказательство во многом основано на доказательстве Томаса Ворша.

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

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

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

Продолжая таким же образом, по индукции можно показать, что $i$-я крайняя правая 1 перемещается в правильное положение не более чем за $n-e+i$ проходит. С $i\leq e$, отсюда следует, что $i$-я крайняя правая 1 перемещается в правильное положение не более чем за $n-e+e=n$ проходит. Таким образом, список правильно отсортирован в $n$ проходит. ЯВЛЯЕТСЯ

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