demist Jul 3 2015 at 19:51

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

4 min

25K

Введение

Алгоритм четно-нечетной сортировки слиянием (odd-even mergesort) был разработан Бэтчером в 1968 году. Алгоритм не слишком популярный и не слишком известный. Однако он достаточно легко параллелится и его реализация не слишком сложна. Лично я узнал о нем когда разбирался с MPI и увидел тестовое задание на coursera: написать сортировку Бэтчера.

Базовые операции

Приведенный код не идеален в плане производительности, однако он наиболее прост для восприятия и понимания алгоритма.

В алгоритме нам понадобятся три следующих абстрактных операции:

compare-exchange — меняем элементы местами, если они идут не по порядку.

template <class T>
void compexch(T& a, T&b)
{
    if (b < a)
        std::swap(a, b);
}

perfect shuffle — делим массив пополам и далее первый элемент первой половины — первый в результате, первый элемент второй половины — второй в результате, второй первой половины — третий в результате и т.д. Массив обязательно четной длины. Фактически, мы расставляем элементы первой половины по четным позициям, а из второй — по нечетной.

template <class T>
void shuffle(std::vector<T>& a, unsigned int l, unsigned int r)
{
    auto half = (unsigned int) (l + r) / 2;
    std::vector<T> tmp(a.size());
    unsigned int i, j;
    for (i = l, j = 0; i <= r; i += 2, j++)
    {
        tmp[i] = a[l + j];
        tmp[i + 1] = a[half + j + 1];
    }
    for (auto i = 0; i < tmp.size(); i++)
       a[i] = tmp[i];
}

perfect unshuffle — операция, обратная предыдущей. Элементы, занимающие четные позиции, отправляются в первую половину массива-результата, нечетные — во вторую.

template <class T>
void unshuffle(std::vector<T>& a, unsigned int l, unsigned int r)
{
    auto half = (unsigned int) (l + r) / 2;
    std::vector<T> tmp(a.size());
    unsigned int i, j;
    for (i = l, j =0; i<=r; i += 2, j++)
    {
        tmp[l + j] = a[i];
        tmp[half + j + 1] = a[i + 1];
    }
    for (auto i = 0; i < tmp.size(); i++)
        a[i]  = tmp[i];
}

Собственно алгоритм

Как это часто бывает в постах/статьях/книгах про сортировки, мы предполагаем, что приходящий нам на вход массив имеет размер, равный степени двойки. Это упростит описание алгоритма и доказательство его корректности. Это ограничение снимем потом.

С помощью введенных операций алгоритм формулируется довольно просто. С помощью операции unshuffle мы разбиваем массив на две половины. Далее надо уже отсортировать каждую из этих половин и потом слить обратно с помощью операции shuffle. Алгоритм не просто так называется четно-нечетной сортировкой слиянием — подход аналогичен известной merge sort, разве что логика разбиения на части другая — по четности индекса, а не просто пополам.

Простейшая реализация с помощью введенных операций:

template <class T>
void OddEvenMergeSort(std::vector<T>& a, unsigned int l, unsigned int r)
{
    if (r == l + 1) compexch(a[l], a[r]); //мы дошли до подмассива размера 2 - теперь просто сравним элементы
    if (r < l + 2) return; //дошли до подмассива размера 1 - выходим, такой подмассив априори отсортирован
    unshuffle(a, l, r); //делим подмассив на две части
    auto half = (unsigned int) (l + r) / 2;
    OddEvenMergeSort(a, l, half);
    OddEvenMergeSort(a, half + 1, r); //вызываемся рекурсивно для половинок
    shuffle(a, l, r); //сливаем части
    for (auto i = l + 1; i < r; i += 2)
        compexch(a[i], a[i + 1]);
    auto halfSize = (r - l + 1) / 2 - 1;       //*
    for (int i = l + 1; i + halfSize < r; i++) //*
        compexch(a[i], a[i + halfSize]);    //*
}

Замечание

Если вы, как и я, читали про этот алгоритм у Сэджвика в «Фундаментальных алгоритмах на С++», то можете заметить, что у него в функции OddEvenMergeSort нет строк, помеченных "*". Уж опечатка это или что, не знаю. Однако алгоритм, приведенный в его книге, ошибается, например, на строке «ABABABAB».

После первого же вызова unshuffle мы получим «AAAABBBB». Далее мы вызываемся рекурсивно для частей «AAAA» и «BBBB». Будем считать, что алгоритм работает верно. Тогда после вызовов мы так и получим части «AAAA» и «BBBB». Сделаем shuffle, получим «ABABABAB». Попарное сравнение выродится в 4-х кратный вызов compexch(«A», «B»), которые ничего не изменят.

Три добавленные строки решают эту проблему. В будущем, если будет время, опишу, почему.

Описание

Сам принцип работы практически ничем не отличается от merge sort, однако операции слияния выполняются совершенно по-разному. Если в merge sort мы заводим два индекса — в первой и во второй половине массива, где половины уже отсортированы, и на каждом шаге просто ставим в результат наименьший из текущих в каждой половине, то здесь мы просто делаем операцию shuffle, а потом попарное сравнение получившегося массива.

Как запустить?

Достаточно вызвать

 OddEvenMergeSort(a, 0, a.size() - 1);

Как быть с массивами длины не являющейся степенью двойки?

Самый простой способ — добавить необходимое число элементов до степени двойки, которые априори все больше (или все меньше) любого элемента в исходном массиве.

Второй подход такой.

Т.к. любое число можно представить как сумму степеней двойки, то разбить массив на такие подмассивы, отсортировать их по отдельности сортировкой Бэтчера и объединить с помощью операции, аналогичной слиянию в merge sort
При этом маленькие подмассивы можно сортировать другим алгоритмом, который, например, не требует рекурсивных вызовов.

Пример работы

AGINORSTAEELMPXY
AIOSAEMXGNRTELPY
AOAMISEX
AAOM
AA
  MO
AMAO
AAMO
    IESX
    EI
      SX
    ESIX
    EISX
AEAIMSOX
AAEIMOSX
        GREPNTLY
        GERP
        EG
          PR
        EPGR
        EGPR
            NLTY
            LN
              TY
            LTNY
            LNTY
        ELGNPTRY
        EGLNPRTY
AEAGELINMPORSTXY
AAEEGILMNOPRSTXY

Tags:

алгоритмы сортировки

Hubs: