Сортировка по четным и нечетным

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

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

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

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

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

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

Алгоритм

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

функция oddEvenSort ( список ) { функция swap ( список , i , j ) { var temp = список [ i ]; список [ i ] = список [ j ]; список [ 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}$

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

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

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

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

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

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

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

Ссылки

1. Филлипс, Малкольм. "Сортировка массива". Homepages.ihug.co.nz . Архивировано из оригинала 28 октября 2011 г. Получено 3 августа 2011 г.
2. Н. Хаберманн (1972) «Сортировка по параллельному соседу (или слава принципа индукции)», CMU Computer Science Report (доступен как Технический отчет AD-759 248, Национальная техническая информационная служба, Министерство торговли США, 5285 Port Royal Rd Springfield VA 22151).
3. Лакшмиварахан, С.; Дхалл, СК и Миллер, Л.Л. (1984), Альт, Франц Л. и Йовитс, Маршалл К. (ред.), «Параллельные алгоритмы сортировки», Advances in Computers , 23 , Academic Press: 295–351, doi :10.1016/S0065-2458(08)60467-2, ISBN 978-0-12-012123-6
4. Седжвик, Роберт (2003). Алгоритмы в Java, части 1-4 (3-е изд.). Addison-Wesley Professional. стр. 454–464. ISBN 978-0-201-36120-9.
5. Кент, Аллен ; Уильямс, Джеймс Г. (1993). Энциклопедия компьютерных наук и технологий: Приложение 14. CRC Press. С. 33–38. ISBN 978-0-8247-2282-1.
6. "Пять лекций по КА" (PDF) . Liinwww.ira.uka.de . Получено 2017-07-30 .
7. Ланг, Ганс Вернер. «Принцип 0-1». inf.hs-flensburg.de . Получено 30 июля 2017 г. .
8. "Распределенная сортировка" (PDF) . Net.t-labs.tu-berlin.de . Получено 2017-07-30 .