Tri à l'aide de piles en lecture seule

Considérez le paramètre suivant:

• on nous donne une pile qui contient n éléments.$s$$n$
• nous pouvons utiliser un nombre constant de piles supplémentaires.$O(1)$
• nous pouvons appliquer les opérations suivantes sur ces piles:
  1. vérifier si une pile est vide,
  2. comparer les éléments supérieurs de deux piles,
  3. supprimer l'élément supérieur d'une pile,
  4. imprimer l'élément supérieur dans une pile,
  5. copier l'élément supérieur d'une pile dans une autre pile,
  6. copier le contenu d'une pile dans une autre pile.

Notez que ce sont les seules opérations autorisées. Nous ne pouvons pas échanger des éléments et nous ne sommes pas autorisés à pousser un élément sur l'une des piles à l'exception de la copie de l'élément supérieur dans une pile (après quoi le contenu précédent de la pile cible est rejeté et il ne contiendra que l'élément copié) .

Voici un algorithme pour trier les piles avec comparaisons O ( n 2 ) :$O(n^2)$

last := empty
for i from 1 to n
  min := empty
  w := s
  while w is not empty
    if w.top > last and w.top < min
      min := w.top
    delete w.top
  print min
  last := min

Pouvons-nous faire mieux?

Existe-t-il un programme qui imprime la liste triée des éléments dans les piles en utilisant uniquement comparaisons log n ) ?$O(n\log n)$

Je pense que je peux maintenant démontrer une borne inférieure non triviale. L'idée est de mettre en œuvre un tel programme avec une famille de programmes de branchement de comparaison. L'hypothèse "en lecture seule" signifie que notre famille de programmes de branchement utilise peu d' espace , c'est-à-dire . Ensuite, nous appliquons la borne inférieure S T = Ω ( n 2 ) prouvée par Borodin et al. dans "A Time-Space Tradeoff for Sorting on non-inconscious Machines". Cela nous donne un n 2 / log $O(\log n)$$ST=\Omega(n^2)$$n^2/\log n$ limite inférieure pour le moment.

Plus en détail: on peut se passer de l'opération 5 ci-dessus. En gros, si nous pouvons déjà comparer les têtes de deux listes et imprimer la tête d'une liste, il n'est pas nécessaire pour nous d'isoler la tête d'une liste sur un registre particulier. En supposant cela, nous voyons que chaque registre de la machine ne stocke que la sous-chaîne finale de l'entrée.

Supposons que notre programme de registres ait lignes de code et k registres, X 1 , … , X k .$\ell$$k$$X_1,\dots,X_k$

Fixez . Nous construisons le programme de branchement de comparaison pour les chaînes de longueur n comme suit. Créez un nœud pour chaque tuple ( i , d 1$n$$n$ où 1 ≤ i ≤ ℓ et 0 ≤ d 1 , … , d k ≤ n . L'idée est que les calculs dans la machine de registre correspondent aux chemins dans le programme de branchement, et nous sommes au nœud ( i , d 1 , … , $(i,d_1,\dots,d_k)$$1\le i\le \ell$$0\le d_1 ,\dots, d_k \le n$ si nous sommes à la ligne i dans la machine de registre et que la longueur de la chaîne stockée dans X i est d i . Maintenant, nous devons définir les bords dirigés du programme de branchement$(i,d_1 ,\dots, d_k)$$i$$X_i$$d_i$

Si la ligne est de la forme$i$

si alors goto i 1 d' autre goto i $X_u<X_v$$i_1$$i_2$

alors pour tout , le nœud ( i , d 1 , … , d k ) est étiqueté en comparant le d $d_1,\dots,d_k$$(i,d_1,\dots,d_k)$$d_u$ élément -th et -th d'entrée, et en ayant le bord «vrai» aller à ( i 1 , d 1 , … , d k ) , et le bord «faux» à ( i 2 , d 1 , … , d $d_v$$(i_1,d_1,\dots,d_k)$ .$(i_2,d_1,\dots,d_k)$

Si la ligne est de la forme$i$

, passez à la ligne i $X_1 \leftarrow tail(X_2)$$i'$

alors il y a une flèche de n'importe quel nœud à ( i ′ , d 2 - 1 , … , d k$(i,d_1,\dots,d_k)$$(i',d_2-1,\dots,d_k)$ .

Si la ligne est de la forme$i$

, passez à la ligne i $print(head(X_u))$$i'$

alors il y a une flèche de n'importe quel nœud $(i,d_1,\dots,d_k)$$(i',d_1,\dots,d_k)$$d_u$

$\ell\cdot n^k$$O(\log n)$

Êtes-vous capable de compter les éléments? Ensuite, je pense qu'il y a une implémentation de Mergesort assez facile. Si vous pouviez mettre des symboles supplémentaires sur la pile, vous pourriez le résoudre avec 3 piles comme ceci:

Si nous n'avons qu'un seul élément, la liste est déjà triée. Supposons maintenant que nous avons déjà trié la moitié supérieure de la pile. Nous pouvons copier la moitié supérieure (dans l'ordre inverse) dans la deuxième pile et placer un symbole de séparation dessus. Maintenant, nous avons à nouveau 3 piles (car nous pouvons ignorer les symboles déjà triés sous le symbole de séparation) et pouvons trier la moitié inférieure. Enfin, nous pouvons copier la moitié inférieure triée dans une troisième pile dans l'ordre inverse et fusionner les deux moitiés dans la pile d'origine.

$O(n \log n)$

$n \log n$

Comme vous ne pouvez pas mettre de nouveaux éléments sur la pile, vous pouvez rencontrer des problèmes aux points de séparation. Pour résoudre ce problème, vous pouvez effectuer les opérations suivantes avec des piles supplémentaires:

$n-2^{\lfloor \log n\rfloor}$

Enfin, répétez la procédure avec les éléments supplémentaires au plus $\log n$$c$$cn \log n+c\frac{n}{2} \log \frac{n}{2}+c\frac{n}{4} \log \frac{n}{4}+\ ... = O(n \log n)$$O(n \log n)$