Metzgers gerade und ungerade Sortierung

Einleitung


Der Odd-Even-Mergesort-Algorithmus wurde 1968 von Batcher entwickelt. Der Algorithmus ist nicht zu populär und nicht zu berühmt. Die Parallelisierung ist jedoch recht einfach und die Implementierung nicht zu kompliziert. Persönlich fand ich über ihn heraus, als ich MPI herausfand und eine Testaufgabe auf coursera sah: eine Metzgersorte schreiben.

Grundlegende Operationen


Der obige Code ist in Bezug auf die Leistung nicht ideal, aber es ist am einfachsten, den Algorithmus zu verstehen und zu verstehen.

Im Algorithmus benötigen wir die folgenden drei abstrakten Operationen:

Compare-Exchange - Wir tauschen Elemente aus, wenn sie nicht in Ordnung sind.

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

mische perfekt - teilen das Array in der Mitte, und ferner das erste Element des ersten Halb - das erste Ergebnis, das erste Element der zweiten Hälfte - das zweite Ergebnis der zweiten Hälfte des ersten bis dritten resultierenden usw. Das Array muss eine gerade Länge haben. In der Tat legen wir die Elemente der ersten Hälfte auf den geraden Positionen, und die zweiten - auf den ungeraden.

template 
void shuffle(std::vector& a, unsigned int l, unsigned int r)
{
    auto half = (unsigned int) (l + r) / 2;
    std::vector 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];
}

Perfektes Entmischen - Vorgang im Gegensatz zum vorherigen. Elemente, die gerade Positionen einnehmen, werden an die erste Hälfte des Ergebnisfeldes gesendet, ungerade an die zweite.

template 
void unshuffle(std::vector& a, unsigned int l, unsigned int r)
{
    auto half = (unsigned int) (l + r) / 2;
    std::vector 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];
}

Der Algorithmus selbst


Wie so oft in Posts / Artikeln / Büchern über das Sortieren wird davon ausgegangen, dass das Array, das zu unserer Eingabe kommt, eine Größe hat, die der Zweierpotenz entspricht. Dies vereinfacht die Beschreibung des Algorithmus und den Nachweis seiner Richtigkeit. Diese Einschränkung wird später entfernen.

Unter Verwendung der eingeführten Operationen wird der Algorithmus ziemlich einfach formuliert. Mit der Unshuffle-Operation teilen wir das Array in zwei Hälften. Als Nächstes müssen Sie jede dieser Hälften sortieren und dann mit der Zufallsoperation wieder zusammenführen. Der Algorithmus ist nicht nur gerade-ungerade Art genannt merge - ein Ansatz , ähnlich dem bekannten The merge Die Art , mit der Ausnahme , dass die Teilung der Logik auf der anderen Seite - auf einem Index Parität, anstatt nur zwei.

Die einfachste Implementierung mit den eingegebenen Operationen:

template 
void OddEvenMergeSort(std::vector& 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]);    //*
}

Bemerkung
Wenn Sie, wie ich, in „Fundamental Algorithms in C ++“ über diesen Algorithmus von Sedgwick lesen, werden Sie möglicherweise feststellen, dass er in der OddEvenMergeSort-Funktion keine mit „*“ markierten Zeilen hat. Ich weiß nicht, ob es sich bereits um einen Tippfehler handelt. Der in seinem Buch angegebene Algorithmus ist jedoch beispielsweise in der Zeile "ABABABAB" falsch.

Nach dem ersten Unshuffle-Aufruf erhalten wir "AAAABBBB". Als nächstes rufen wir rekursiv die "AAAA" - und "BBBB" -Teile auf. Wir gehen davon aus, dass der Algorithmus korrekt funktioniert. Nach den Anrufen erhalten wir dann die Teile "AAAA" und "BBBB". Mische, erhalte "ABABABAB". Paarweise Vergleiche degenerieren zu einem 4-fachen Aufruf von compexch ("A", "B"), der nichts ändert.

Drei zusätzliche Zeilen lösen dieses Problem. In Zukunft, wenn es Zeit gibt, werde ich beschreiben, warum.

Beschreibung


Das Prinzip der Operation selbst unterscheidet sich praktisch nicht von der Sortierung der Zusammenführung. Zusammenführungsoperationen werden jedoch auf völlig unterschiedliche Weise durchgeführt. Wenn wir beim Zusammenführen zwei Indizes erhalten - in der ersten und zweiten Hälfte des Arrays, in denen die Hälften bereits sortiert sind, und bei jedem Schritt einfach den kleinsten Strom in jede Hälfte als Ergebnis setzen, dann führen wir hier nur die Mischoperation aus und vergleichen dann die resultierende paarweise Array.

Wie fange ich an?


Rufen Sie einfach an
 OddEvenMergeSort(a, 0, a.size() - 1); 


Was ist mit Arrays mit einer Länge, die keine Potenz von zwei ist?


Am einfachsten ist es, die erforderliche Anzahl von Elementen zur Potenz von zwei zu addieren, die a priori mehr (oder weniger) eines Elements im ursprünglichen Array sind.

Der zweite Ansatz ist dieser.

Weil Jede Zahl kann als Summe von Zweierpotenzen dargestellt werden, dann das Array in solche Subarrays aufteilen, einzeln nach Metzger sortieren und mit einer ähnlichen Operation wie beim Zusammenführen kombinieren .
In diesem Fall können kleine Subarrays nach einem anderen Algorithmus sortiert werden, für den beispielsweise keine rekursiven Aufrufe erforderlich sind .

Arbeitsbeispiel


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

Jetzt auch beliebt: