Сортировка по четным – нечетным - Odd–even sort

Сортировка по четным и нечетным
	Пример нечетно-четной перестановки сортировки списка случайных чисел.
Класс	Алгоритм сортировки
Структура данных	Множество
Наихудшая производительность
Лучшая производительность
Сложность пространства в наихудшем случае

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

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

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

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

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

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

Алгоритм

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

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;
      }
    }
  }
}

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

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

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

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

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

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

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

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