Comment réparer cet algorithme de sorting non récursif impair-pair-fusion?

Je cherchais un algorithme de sorting non récursif impair-pair-fusion et ai trouvé 2 sources:

  • un livre de Sedgewick R.
  • cette question SO

Les deux algorithmes sont identiques mais faux. Le réseau de sorting résultant n’est pas un réseau de sorting pair-impair.

Voici une image du réseau résultant avec 32 entrées. Une ligne verticale entre 2 lignes horizontales signifie que vous comparez la valeur a [x] à a [y], si elle est supérieure, échangez les valeurs du tableau.

sorting impair / pair pour 32 entrées http://soffr.miximages.com/c/11fig07.gif (cliquable)

J’ai copié le code de Java en C et remplacé la fonction exch par un printf pour imprimer les candidats à l’échange.

Quand on dessine un diagramme des paires, on voit que trop de paires sont générées.

Quelqu’un at-il une idée de la façon de résoudre cet algorithme?

Pourquoi ai-je besoin d’une version non récursive?
Je veux transformer ce réseau de sorting en matériel. Il est facile d’insérer des étapes de pipeline dans un algorithme non récursif.

J’ai également étudié la version récursive, mais c’est trop complexe pour transformer l’algorithme en matériel en pipeline.

Mon code C:

 #include  #include  void sort(int l, int r) { int n = r-l+1; for (int p=1; p0; k/=2) for (int j=k%p; j+k<n; j+=(k+k)) for (int i=0; i<njk; 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); } 

Le résultat:

 0 -o--------o-------------------------o---------------o------------------------- | | | | 1 -o--------|-o------o----------------|-o-------------oo----------------------- | | | | | | 2 -oo------o-|------oo--------------|-|-o----o--------oo--------------------- | | | | | | | | | 3 -oo--------o--------o--------------|-|-|-o--|-o--------oo-------o----------- | | | | | | | | 4 -ooo----o---o----o-----o----------o-|-|-|--o-|-o--------oo-----oo--------- | | | | | | | | | | | | | | 5 -ooo----|-o-|-o--oo---oo---o------o-|-|----o-|-o--------oo-----oo---o--- | | | | | | | | | | | | | | 6 -oooo--o-|-o-|----oo---oooo------o-|------o-|----------oo-----oooo- | | | | | | | | | | | | | | 7 -oooo----o---o------o-----o---o--------o--------o------------o-------o---o- 

Lorsque je connais les paires d’échange correctes et que l’algorithme est égal à l’image, je le traduis en VHDL pour des tests sur ma plate-forme matérielle.

Autres implémentations de réseau de sorting matériel open source

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

Appendice:
Odd-even mergesort (sorte de Batcher) est comme une sorte de bitonique (à ne pas confondre avec la sorte de bitère de Batcher). Mais dans le matériel, cet algorithme a une complexité de taille supérieure à celle du sorting bitonique, alors que la latence est la même.

Ces algorithmes peuvent être implémentés avec une bonne utilisation des ressources par rapport aux algorithmes logiciels rapides comme quicksort.

Wikipédia: impair-pair mergesort

Remarque:
Étant donné que les réseaux de sorting sont statiques et indépendants des valeurs d’entrée, aucune comparaison ni échange ne sont nécessaires pour générer le réseau. C’est une des raisons pour lesquelles il peut être transformé en matériel. Mon code génère les index pour les opérations de comparaison. En matériel, ces connexions verticales seront remplacées par des circuits de comparaison et d’échange. Ainsi, les données non sortingées traverseront le réseau et seront sortingées du côté sortie.

    Le code suivant fonctionne pour les tableaux de toute taille et n’est pas récursif. C’est un portage direct de l’implémentation de la fonction correspondante dans le module Algorithm::Networksort de Perl. La mise en œuvre correspond à l’algorithme décrit par Knuth dans The Art of Computer Programming, vol 3 (algorithme 5.2.2M). Cela n’aide en rien de corriger votre algorithme, mais il vous donne au moins une implémentation non récursive de travail de la fusion impair-pair de Batcher avec seulement trois boucles nestedes 🙂

     #include  #include  void oddeven_merge_sort(int length) { int t = ceil(log2(length)); int p = pow(2, t - 1); while (p > 0) { int q = pow(2, t - 1); int r = 0; int d = p; while (d > 0) { for (int i = 0 ; i < length - d ; ++i) { if ((i & p) == r) { printf("%2i cmp %2i\n", i, i + d); } } d = q - p; q /= 2; r = p; } p /= 2; } } 

    Si vous pouvez mettre la main sur un exemplaire du livre The Art of Computer Programming, vol. 3 , vous aurez une explication intéressante du fonctionnement et des raisons du fonctionnement de l'algorithme, ainsi que quelques détails supplémentaires.

    Je pense avoir trouvé une solution. Je l’ai vérifié pour la length = 2, 4, 8, 16 .

    Voici mon code:

     void sort(int length) { int G = log2ceil(length); // number of groups for (int g = 0; g < G; g++) // iterate groups { int B = 1 << (G - g - 1); // number of blocks for (int b = 0; b < B; b++) // iterate blocks in a group { for (int s = 0; s <= g; s++) // iterate stages in a block { int d = 1 << (g - s); // compare distance int J = (s == 0) ? 0 : d; // starting point for (int j = J; j+d < (2< 

    Cette solution introduit une cinquième boucle for pour gérer les sous-blocs dans un groupe. La boucle j a une valeur de départ et d’abandon modifiée pour gérer les comptes impairs d’étapes post-fusion sans générer d’étapes de comparaison doublées.

    Ceci est un sous-programme fixe non récursif.

     void sort(int n) { 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++) // wrong for (int i = 0; i < k; i++) // correct if ((i + j)/(p + p) == (i + j + k)/(p + p)) printf("%2i cmp %2i\n", i + j, i + j + k); } 

    ou

     void sort(int n) { for (int p = 1; p < n; p += p) for (int k = p; k > 0; k /= 2) for (int j = 0; j < k; j++) for (int i = k % p; i + k < n; i += k + k) if ((i + j)/(p + p) == (i + j + k)/(p + p)) printf("%2i cmp %2i\n", i + j, i + j + k); }