Existe-t-il des algorithmes de tri comparatifs connus qui ne se réduisent pas au tri des réseaux, de telle sorte que chaque élément soit comparé ?O ( logn )O(logn)O(\log n) Autant que je sache, le seul moyen de trier avec comparaison sur chaque élément est de construire un réseau de tri AKS pour n...
Contexte: Chao Xu a posté il y a quelque temps la question suivante: " Existe-t-il des algorithmes de tri de comparaison connus qui ne se réduisent pas à des réseaux de tri, de sorte que chaque élément est comparé fois?O ( logn)O(Journaln)O(\log n) ". Il semble que nous soyons un peu coincés avec...
Le principe 0-1 dit que si un réseau de tri fonctionne pour toutes les séquences 0-1, alors il fonctionne pour n'importe quel ensemble de nombres. Existe-t-il un S⊂{0,1}nS⊂{0,1}nS\subset \{0,1\}^n tel que si un réseau trie chaque séquence 0-1 de S, alors il trie chaque séquence 0-1 et la taille de...
Étant donné nnn entrées x0,…,xn−1x0,…,xn−1x_0, \ldots, x_{n-1} , nous construisons un réseau de tri aléatoire avec mmm portes en choisissant itérativement deux variables xi,xjxi,xjx_i, x_j avec i<ji<ji < j et en ajoutant une porte de comparaison qui les échange si xi>xjxi>xjx_i > x_j ....
Je suis intéressé par le problème suivant. On nous donne en entrée une "permutation cible" , ainsi qu'une liste ordonnée d'indices . Ensuite, en commençant par la liste (c'est-à-dire la permutation d'identité), à chaque pas de temps nous l' dans avec le élément, avec probabilité indépendante . Soit...