ch suchte nach einem nicht-rekursiven Sortieralgorithmus für ungerade-gerade-Zusammenführung und fand 2 Quelle

a Buch vonSedgewick R.DiesSO frage

Beide Algorithmen sind identisch, aber falsch. Das resultierende Sortiernetzwerk ist kein Sortiernetzwerk mit ungerader / gerader Zusammenführung.

Hier ist ein Bild des resultierenden Netzwerks mit 32 Eingängen. Eine vertikale Linie zwischen zwei horizontalen Linien bedeutet, dass der Wert a [x] mit einem [y] verglichen wird. Wenn dieser Wert größer ist, werden die Werte im Array vertauscht.

odd-even-merge sort für 32 Eingaben http://flylib.com/books/3/55/1/html/2/images/11fig07.gi (anklickbar)

Ich habe den Code von Java nach C kopiert und das @ ersetexch Funktion von einemprintf, um die Austauschkandidaten auszudrucken.

Wenn man ein Diagramm der Paare zeichnet, kann man sehen, dass zu viele Paare erzeugt werden.

Hat jemand eine Idee, wie man diesen Algorithmus repariert?

Warum brauche ich eine nicht rekursive Version?
Ich möchte dieses Sortiernetzwerk in Hardware umwandeln. Es ist einfach, Pipeline-Stufen in nicht-rekursive Algorithmen einzufügen.

Ich habe auch die rekursive Version untersucht, aber sie ist zu komplex, um den Algorithmus in Pipeline-Hardware umzuwandeln.

Mein C-Code:

#include <stdlib.h>
#include <stdio.h>

void sort(int l, int r)
{ int n = r-l+1;

  for (int p=1; p<n; p+=p)
    for (int k=p; k>0; k/=2)
      for (int j=k%p; j+k<n; j+=(k+k))
        for (int i=0; i<n-j-k; i++)
          if ((j+i)/(p+p) == (j+i+k)/(p+p))
              printf("%2i cmp %2i\n", l+j+i, l+j+i+k);
}
int main(char* argv, int args)
{ const int COUNT = 8;
  sort(0, COUNT);
}

Das Ergebnis

0 -o--------o-------------------------o---------------o-------------------------
   |        |                         |               |
1 -o--------|-o------o----------------|-o-------------o-o-----------------------
            | |      |                | |               |
2 -o-o------o-|------o-o--------------|-|-o----o--------o-o---------------------
   | |        |        |              | | |    |          |
3 -o-o--------o--------o--------------|-|-|-o--|-o--------o-o-------o-----------
                                      | | | |  | |          |       |
4 -o-o-o----o---o----o-----o----------o-|-|-|--o-|-o--------o-o-----o-o---------
   | | |    |   |    |     |            | | |    | |          |       |
5 -o-o-o----|-o-|-o--o-o---o-o---o------o-|-|----o-|-o--------o-o-----o-o---o---
            | | | |    |     |   |        | |      | |          |       |   |
6 -o-o-o-o--o-|-o-|----o-o---o-o-o-o------o-|------o-|----------o-o-----o-o-o-o-
   | | | |    |   |      |     |   |        |        |            |       |   |
7 -o-o-o-o----o---o------o-----o---o--------o--------o------------o-------o---o-

Wenn ich die richtigen Austauschpaare kenne und der Algorithmus dem Image entspricht, übersetze ich ihn für Tests auf meiner Hardwareplattform in VHDL.

Weitere Open-Source-Hardware-Sortiernetzwerk-Implementierungen:

PoC.sort.sortnet.oddevensort PoC.sort.sortnet.bitonicsort

Blinddarm
Odd Even Mergesort (a.k.a Batcher's Sort) ist wie bitonisches Sortieren (nicht zu verwechseln mit Batcher's bitonischem Sortieren). In der Hardware ist dieser Algorithmus jedoch komplexer als die bitonische Sortierung, während die Latenz gleich ist.

Dieser Algorithmus kann im Vergleich zu schnellen Softwarealgorithmen wie quicksort mit einer guten Ressourcennutzung implementiert werden.

Wikipedia: odd-even mergesort

Hinweis
Da sortierende Netzwerke statisch und unabhängig von den Eingabewerten sind, ist kein Vergleichen und Tauschen erforderlich, um das Netzwerk zu generieren. Das ist ein Grund, warum es in Hardware umgewandelt werden kann. Mein Code generiert die Indizes für die Vergleichsoperationen. In der Hardware werden diese vertikalen Verbindungen durch Vergleichs- und Austauschschaltungen ersetzt. Unsortierte Daten wandern also durch das Netzwerk und werden ausgangsseitig sortiert.