Réseaux de sorting standard pour les petites valeurs de n

Je recherche une implémentation réseau de sorting d’un type à 5 éléments, mais comme je ne pouvais pas trouver une bonne référence sur SO, j’aimerais demander des réseaux de sorting pour toutes les petites valeurs de n, au moins n = 3. par n = 6, mais des valeurs plus élevées seraient également intéressantes. Une bonne réponse devrait au moins les énumérer sous forme de séquences d’opérations “swap” (sortinger sur 2 éléments), mais il pourrait également être intéressant de voir la décomposition récursive en termes de réseaux de sorting d’ordre inférieur.

Pour ma candidature, je ne me préoccupe que de la médiane de 5 éléments, et non de les ranger. C’est-à-dire que l’ordre des 4 autres éléments peut être non spécifié dans le résultat tant que la médiane se termine au bon endroit. Une approche liée aux réseaux de sorting peut-elle être utilisée pour calculer la médiane avec moins de conversions qu’un sorting complet? Si tel est le cas, une telle solution à mon problème (pour n = 5) et dans d’autres cas constituerait également une excellente réponse.

(Remarque: j’ai balisé cette question C parce que C est la langue que j’utilise et je pense que les personnes qui suivent l’étiquette C ont de bonnes réponses tant qu’il se traduit facilement en C, ce qu’il devrait naturellement faire tant que les critères susmentionnés sont remplis.)

Choisissez-en une dans chaque section, probablement celle qui fonctionne le plus rapidement sur votre matériel, car nous sums résolument dans le domaine de “l’optimisation démoniaque”: http://smarterrecall.com/networks.html , reproduit ci-dessous:

J’ai créé ce site pour répertorier tous les réseaux de sorting optimaux possibles jusqu’à 6 entrées écrites à l’aide d’un programme MatLab. Le temps d’exécution le plus long concerne 5 entrées à 45 secondes. Si vous êtes intéressé à me contacter, je peux être contacté à rpl1 [AT] rice [DOT] edu Cheers, Richard L.

 ---------- - 2-input: 1 network [[1 2]] ---------- - 3-input: 6 networks [[1 2][1 3][2 3]] [[1 2][2 3][1 2]] [[1 3][1 2][2 3]] [[1 3][2 3][1 2]] [[2 3][1 2][2 3]] [[2 3][1 3][1 2]] ---------- - 4-input: 3 networks [[1 2][3 4][1 3][2 4][2 3]] [[1 3][2 4][1 2][3 4][2 3]] [[1 4][2 3][1 2][3 4][2 3]] ---------- - 5-input: 180 networks [[1 2][3 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 2][3 4][1 3][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 4][1 3][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 2][3 4][1 3][4 5][2 5][3 4][1 3][2 4][2 3]] [[1 2][3 4][1 4][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 4][1 4][3 5][1 3][2 5][2 3][4 5][3 4]] [[1 2][3 4][1 5][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 2][3 4][1 5][2 4][1 3][2 5][2 3][4 5][3 4]] [[1 2][3 4][1 5][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 2][3 4][2 4][3 5][1 2][4 5][1 3][2 4][2 3]] [[1 2][3 4][2 4][3 5][1 3][2 5][2 3][4 5][3 4]] [[1 2][3 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 2][3 5][1 3][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 5][1 3][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 2][3 5][1 3][4 5][2 5][3 4][1 3][2 4][2 3]] [[1 2][3 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 2][3 5][1 4][2 5][1 3][2 4][2 3][4 5][3 4]] [[1 2][3 5][1 4][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 5][1 5][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 5][1 5][3 4][1 3][2 4][2 3][4 5][3 4]] [[1 2][3 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 2][3 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[1 2][3 5][2 5][3 4][1 3][2 4][2 3][4 5][3 4]] [[1 2][4 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 2][4 5][1 3][2 5][1 4][2 3][2 4][3 5][3 4]] [[1 2][4 5][1 3][2 5][2 4][3 5][1 2][3 4][2 3]] [[1 2][4 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 2][4 5][1 4][2 3][2 4][3 5][1 2][3 4][2 3]] [[1 2][4 5][1 4][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 2][4 5][1 4][3 5][2 5][3 4][1 3][2 4][2 3]] [[1 2][4 5][1 5][2 3][2 4][3 5][1 2][3 4][2 3]] [[1 2][4 5][1 5][3 4][1 3][2 4][2 3][4 5][3 4]] [[1 2][4 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 2][4 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[1 2][4 5][2 5][3 4][1 3][2 4][2 3][4 5][3 4]] [[1 3][2 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 3][2 4][1 2][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 4][1 2][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 3][2 4][1 2][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 3][2 4][1 4][2 5][1 2][3 5][2 3][4 5][3 4]] [[1 3][2 4][1 4][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 4][1 5][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 3][2 4][1 5][3 4][1 2][3 5][2 3][4 5][3 4]] [[1 3][2 4][1 5][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 3][2 4][2 5][3 4][1 2][3 5][2 3][4 5][3 4]] [[1 3][2 4][2 5][3 4][1 3][4 5][1 2][3 4][2 3]] [[1 3][2 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 3][2 5][1 2][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 5][1 2][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 3][2 5][1 2][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 3][2 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 3][2 5][1 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[1 3][2 5][1 4][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]] [[1 3][2 5][1 5][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 3][2 5][2 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[1 3][2 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 3][4 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 3][4 5][1 2][3 5][1 4][2 3][2 4][3 5][3 4]] [[1 3][4 5][1 2][3 5][2 5][3 4][1 3][2 4][2 3]] [[1 3][4 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 3][4 5][1 4][2 3][2 4][3 5][1 2][3 4][2 3]] [[1 3][4 5][1 4][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 3][4 5][1 4][2 5][2 4][3 5][1 2][3 4][2 3]] [[1 3][4 5][1 5][2 3][2 4][3 5][1 2][3 4][2 3]] [[1 3][4 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]] [[1 3][4 5][2 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[1 3][4 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 3][4 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[1 4][2 3][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 4][2 3][1 2][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 4][2 3][1 2][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 4][2 3][1 2][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 4][2 3][1 3][2 5][1 2][4 5][2 4][3 5][3 4]] [[1 4][2 3][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 4][2 3][1 5][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 4][2 3][1 5][3 4][1 2][3 5][2 3][4 5][3 4]] [[1 4][2 3][1 5][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 4][2 3][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 4][2 3][2 5][3 4][1 2][3 5][2 3][4 5][3 4]] [[1 4][2 3][2 5][3 4][1 3][4 5][1 2][3 4][2 3]] [[1 4][2 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 4][2 5][1 2][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 4][2 5][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 4][2 5][1 2][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 4][2 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 4][2 5][1 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 4][2 5][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 4][2 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]] [[1 4][2 5][1 5][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 4][2 5][2 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 4][2 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 4][2 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 4][3 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 4][3 5][1 2][4 5][1 3][2 4][2 3][4 5][3 4]] [[1 4][3 5][1 2][4 5][2 5][3 4][1 3][2 4][2 3]] [[1 4][3 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 4][3 5][1 3][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 4][3 5][1 3][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 4][3 5][1 3][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 4][3 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]] [[1 4][3 5][1 5][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 4][3 5][2 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 4][3 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 4][3 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[1 5][2 3][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 5][2 3][1 2][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 5][2 3][1 2][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 5][2 3][1 2][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 5][2 3][1 3][2 4][1 2][4 5][2 4][3 5][3 4]] [[1 5][2 3][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 5][2 3][1 4][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 3][1 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 3][1 4][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 5][2 3][2 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 3][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 5][2 3][2 5][3 4][1 3][4 5][1 2][3 4][2 3]] [[1 5][2 4][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 5][2 4][1 2][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 5][2 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 5][2 4][1 2][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 5][2 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 4][1 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 4][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 5][2 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]] [[1 5][2 4][1 4][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 5][2 4][2 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 5][2 4][2 5][3 4][1 3][4 5][1 2][3 4][2 3]] [[1 5][3 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 5][3 4][1 2][4 5][1 3][2 4][2 3][4 5][3 4]] [[1 5][3 4][1 2][4 5][2 5][3 4][1 3][2 4][2 3]] [[1 5][3 4][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 5][3 4][1 3][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 5][3 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][3 4][1 3][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 5][3 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]] [[1 5][3 4][1 4][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 5][3 4][2 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][3 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 5][3 4][2 4][3 5][1 2][4 5][1 3][2 4][2 3]] [[2 3][4 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[2 3][4 5][1 2][3 5][1 4][2 3][2 4][3 5][3 4]] [[2 3][4 5][1 2][3 5][2 5][3 4][1 3][2 4][2 3]] [[2 3][4 5][1 3][2 4][1 2][4 5][2 4][3 5][3 4]] [[2 3][4 5][1 3][2 4][1 4][3 5][1 2][3 4][2 3]] [[2 3][4 5][1 3][2 5][1 4][3 5][1 2][3 4][2 3]] [[2 3][4 5][1 4][2 5][1 2][3 4][2 3][4 5][3 4]] [[2 3][4 5][1 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[2 3][4 5][1 4][3 5][2 3][4 5][1 2][3 4][2 3]] [[2 3][4 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]] [[2 3][4 5][1 5][2 4][1 4][3 5][1 2][3 4][2 3]] [[2 3][4 5][1 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[2 4][3 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[2 4][3 5][1 2][4 5][1 3][2 4][2 3][4 5][3 4]] [[2 4][3 5][1 2][4 5][2 5][3 4][1 3][2 4][2 3]] [[2 4][3 5][1 3][2 5][1 2][3 4][2 3][4 5][3 4]] [[2 4][3 5][1 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[2 4][3 5][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[2 4][3 5][1 4][2 3][1 2][3 5][2 3][4 5][3 4]] [[2 4][3 5][1 4][2 3][1 3][4 5][1 2][3 4][2 3]] [[2 4][3 5][1 4][2 5][1 3][4 5][1 2][3 4][2 3]] [[2 4][3 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]] [[2 4][3 5][1 5][2 3][1 3][4 5][1 2][3 4][2 3]] [[2 4][3 5][1 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[2 5][3 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[2 5][3 4][1 2][4 5][1 3][2 4][2 3][4 5][3 4]] [[2 5][3 4][1 2][4 5][2 5][3 4][1 3][2 4][2 3]] [[2 5][3 4][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[2 5][3 4][1 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[2 5][3 4][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[2 5][3 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]] [[2 5][3 4][1 4][2 3][1 3][4 5][1 2][3 4][2 3]] [[2 5][3 4][1 4][3 5][1 2][4 5][1 3][2 4][2 3]] [[2 5][3 4][1 5][2 3][1 2][3 4][2 3][4 5][3 4]] [[2 5][3 4][1 5][2 3][1 3][4 5][1 2][3 4][2 3]] [[2 5][3 4][1 5][2 4][1 3][4 5][1 2][3 4][2 3]] ---------- - 6-input: 90 networks [[1 2][3 4][5 6][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 2][3 4][5 6][1 3][2 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 2][3 4][5 6][1 4][2 6][3 5][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 2][3 4][5 6][1 5][2 3][4 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 2][3 4][5 6][1 5][2 4][3 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 2][3 4][5 6][1 6][2 4][3 5][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 2][3 5][4 6][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 2][3 5][4 6][1 3][2 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 2][3 5][4 6][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 2][3 5][4 6][1 4][2 5][3 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 2][3 5][4 6][1 5][2 6][3 4][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 2][3 5][4 6][1 6][2 5][3 4][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 2][3 6][4 5][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 2][3 6][4 5][1 3][2 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 2][3 6][4 5][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 2][3 6][4 5][1 4][2 6][3 5][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 2][3 6][4 5][1 5][2 6][3 4][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 2][3 6][4 5][1 6][2 5][3 4][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 3][2 4][5 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 3][2 4][5 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 3][2 4][5 6][1 4][2 5][3 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 3][2 4][5 6][1 5][2 3][4 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 3][2 4][5 6][1 5][2 6][3 4][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 3][2 4][5 6][1 6][2 5][3 4][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 3][2 5][4 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 3][2 5][4 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 3][2 5][4 6][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 3][2 5][4 6][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 3][2 5][4 6][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 3][2 5][4 6][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 3][2 6][4 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 3][2 6][4 5][1 2][3 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 3][2 6][4 5][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 3][2 6][4 5][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 3][2 6][4 5][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 3][2 6][4 5][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 3][5 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 4][2 3][5 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 4][2 3][5 6][1 3][2 5][4 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 4][2 3][5 6][1 5][2 4][3 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 4][2 3][5 6][1 5][2 6][3 4][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 4][2 3][5 6][1 6][2 5][3 4][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 3][4 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 5][2 3][4 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 5][2 3][4 6][1 3][2 4][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 5][2 3][4 6][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 3][4 6][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 3][4 6][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 3][4 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 6][2 3][4 5][1 2][3 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 6][2 3][4 5][1 3][2 4][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 6][2 3][4 5][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 3][4 5][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 3][4 5][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] 

Personnellement, je vérifierais que le réseau de sorting est correct avant de l’utiliser, plutôt que de prendre le mot d’une page aléatoire sur Internet. La force brute “seulement” nécessite de l’exécuter avec un nombre infini d’entrées: “évidemment” n! les entrées suffisent, tout comme 2**n ( https://en.wikipedia.org/wiki/Sorting_network#Zero-one_principle ).

Tous les réseaux 5 optimaux impliquent “3” dans le dernier échange. La sélection de la médiane dans moins de swaps n’est donc pas si facile. Cela peut être fait en 6 comparaisons, cependant. Il y a beaucoup plus de code que ce dont vous avez besoin ici, si vous pouvez ignorer les pleurs de la question:

Code pour calculer la “médiane de cinq” en C #

Pour choisir une médiane, vous ne devez pas nécessairement effectuer d’ échanges, à l’exception peut-être d’un échange inconditionnel si vous souhaitez conserver les 5 valeurs. Un déménagement pourrait être suffisant.

Le demandeur était particulièrement intéressé par une implémentation de la médiane de 5 basée sur les réseaux de sorting, je vais donc aborder ce cas spécifique. Une brève revue de la littérature indique à quoi ressemblent les solutions optimales selon divers parameters.

Michael Codish, Luís Cruz-Filipe, Thorsten Ehlers, Mike Müller et Peter Schneider-Kamp. “Tri des réseaux: à la fin et à nouveau.” Le Journal 1 du Journal of Computer and System Sciences (2016) montre que pour n = 5, le nombre minimal de permutations de comparaison est de 9 et la profondeur minimale du réseau est de 5. Chaque comparaison-swap équivaut à deux minutes / minute. max opérations, le nombre minimal d’opérations min / max requirejs est de 18.

Lukáŝ Sekanina, “Exploration évolutive de l’espace de conception pour les circuits médians”. Dans EvoWorkshops , mars 2004, pages 240-249, donne le nombre minimal d’opérations min / max requirejs pour un réseau de sélection de médiane à cinq entrées optimal égal à 10 dans le tableau 1.

William Gasarch, Wayne Kelly et William Pugh. “Trouver le i plus grand de n pour petit i, n.” ACM SIGACT News 27, no. 2 (1996): 88-96, tableau 1: au moins 6 comparaisons sont nécessaires pour la médiane sur 5.

En règle générale, les réseaux de sorting comportant un nombre minimal d’opérations ne se réduisent pas à des réseaux de sélection médiane comportant un nombre minimal d’opérations, simplement en éliminant les opérations redondantes. Mais il est possible de trouver des réseaux qui réduisent de manière optimale au moins certaines valeurs de n . Pour n = 5, une recherche en force brute de ces réseaux est possible.

Le code ci-dessous indique quatre variantes de réseaux de sorting à cinq entrées comprenant neuf opérations de comparaison-permutation ou, alternativement, des opérations de 18 minutes / maximum. Lorsqu’ils sont compilés avec FULL_SORT = 0 ils se transforment en réseaux de sélection médiane avec des opérations de 10 min / max. Donc, selon cette mésortingque, le sorting et la sélection médiane sont optimaux.

Toutefois, lorsqu’elles sont utilisées comme réseau de sorting, les quatre variantes ont une profondeur de six au lieu de cinq. De plus, lorsqu’ils sont configurés en tant que réseau de sélection médiane basé sur des comparaisons au lieu d’opérations min / max, ils nécessitent tous sept comparaisons au lieu de six minimum.

Exemple de résultats de compilation dans Comstackr Explorer (godbolt): Utilisation d’opérations 18 min / max pour un sorting à cinq entrées, à l’aide d’opérations 10 min / max pour une médiane à cinq entrées.

 #include  #include  #include  #define VARIANT 1 #define USE_MIN_MAX 1 #define FULL_SORT 0 typedef float T; #if USE_MIN_MAX #define MIN(a,b) ((T)(fmin(a,b))) #define MAX(a,b) ((T)(fmax(a,b))) #define SWAP(i,j) do { T s = MIN(a##i,a##j); T t = MAX(a##i,a##j); a##i = s; a##j = t; } while (0) #else // USE_MIN_MAX #define MIN(a,b) (((a) > (b)) ? (b) : (a)) #define MAX(a,b) (((a) > (b)) ? (a) : (b)) #define SWAP(i,j) do { if (a##i > a##j) { T temp = a##i; a##i = a##j; a##j = temp; }} while (0) #endif // USE_MIN_MAX /* Use sorting/median network to fully or partially sort array of five values and return the median value */ T network5 (T *a) { // copy to scalars T a0, a1, a2, a3, a4; a0=a[0];a1=a[1];a2=a[2];a3=a[3];a4=a[4]; #if VARIANT == 1 SWAP (0, 1); SWAP (2, 3); SWAP (0, 2); SWAP (1, 3); SWAP (2, 1); SWAP (1, 4); SWAP (1, 2); SWAP (0, 1); SWAP (3, 4); #elif VARIANT == 2 SWAP (3, 4); SWAP (0, 2); SWAP (2, 4); SWAP (0, 3); SWAP (2, 3); SWAP (1, 2); SWAP (0, 1); SWAP (2, 3); SWAP (3, 4); #elif VARIANT == 3 SWAP (3, 2); SWAP (0, 4); SWAP (2, 4); SWAP (0, 3); SWAP (2, 3); SWAP (1, 2); SWAP (0, 1); SWAP (2, 3); SWAP (3, 4); #elif VARIANT == 4 SWAP (2, 4); SWAP (0, 1); SWAP (0, 2); SWAP (1, 4); SWAP (2, 3); SWAP (1, 2); SWAP (2, 3); SWAP (0, 1); SWAP (3, 4); #else #error unsupported VARIANT #endif #if FULL_SORT // copy back sorted results a[0]=a0;a[1]=a1;a[2]=a2;a[3]=a3;a[4]=a4; #endif // return median-of-5 return a2; } 

Trop long pour un commentaire. La réponse ci-dessus du professeur Falken peut être validée dans MATLAB selon les axes suivants: en utilisant un peu de recherche / remplacement ou regex-fu, écrivez

 sn{3} = [... [[1,2],[1,3],[2,3]];... [[1,2],[2,3],[1,2]];... [[1,3],[1,2],[2,3]];... [[1,3],[2,3],[1,2]];... [[2,3],[1,2],[2,3]];... [[2,3],[1,3],[1,2]]; ]; 

et de même pour les autres valeurs de n, puis exécutez

 for n = 3:6 test_in = cellfun(@str2num,num2cell(dec2bin(0:(2^n-1),n))); for j = 1:size(sn{n},1) test_out = test_in; for k = 1:2:size(sn{n},2) temp1 = test_out(:,sn{n}(j,k)); temp2 = test_out(:,sn{n}(j,k+1)); ind = temp2 < temp1; test_out(ind,sn{n}(j,k)) = temp2(ind); test_out(ind,sn{n}(j,k+1)) = temp1(ind); end end test = cellfun(@issorted,mat2cell(test_out,ones(1,2^n),n)); assert(all(test),['n = ',num2str(n),' failed test']); end 

Les assertions valent pour chaque valeur de n.