Dev Faq
6
votes

Tri d'une pile en ordre croissant en C, en utilisant deux piles

On m'a donné une tâche pour trier les nombres dans la pile A d'entiers dans l'ordre croissant en utilisant deux piles A et b .

. En utilisant onze opérations:

  1. SA : Swap A - Échangez les 2 premiers éléments en haut de la pile A
  2. sb : Swap b - Échangez les 2 premiers éléments en haut de la pile B .
  3. ss : SA et sb en même temps.
  4. pa : push a - Prenez le premier élément en haut de B et mettez-le en haut de A < / code>.
  5. pb : push b - Prenez le premier élément en haut de A et mettez-le en haut de B < / code>.
  6. ra : pivoter a - Défilez tous les éléments de la pile A par 1. Le premier élément devient le dernier.
  7. rb : rotation b - Défilez tous les éléments de la pile B par 1. Le premier élément devient le dernier.
  8. rr : ra et rb en même temps.
  9. rra : inverse rotation A - Décalageez tous les éléments de la pile A par 1. Le dernier élément devient le premier.
  10. rrb : inverse rotation b - Décalage tous les éléments de la pile B par 1. Le dernier élément devient le premier.
  11. rrr : rra et rrb en même temps.

    ma fonction de tri xxx

    Ma fonction Trier la pile, je pense qu'il faut trop d'étapes pour trier. J'ai besoin de suggestions ou de conseils sur la manière de le faire trier la pile avec moins d'étapes prises. Code complet en ligne

1 commentaires

@Polikdir Comment est-ce un duplicata?, Les deux questions sont totalement différentes.

3 Réponses :

1
votes

donné deux piles A et B, où A est remplie d'une permutation aléatoire d'éléments et de B est vide et une variable temporaire t-mesure de contenir un élément (et un compteur mais le compteur ne compte pas) Vous pouvez trier Une commande ascendante en b par:

  1. Déplacez tous les éléments de A à B, mais gardez le plus grand élément de T
  2. Déplacez tous les éléments de B à un
  3. Mettez l'élément dans T sur la pile B
  4. boucle jusqu'à ce que l'a soit vide
    1. Déplacez tous les éléments de A à B, mais gardez le plus grand élément de T
    2. Déplacez tous les éléments de B sur A à l'exception des plus gros (s) sur le bas (voici l'endroit où le compteur est utile pour conserver le nombre d'éléments déjà triés dans B)
    3. Mettez l'élément dans T sur la pile B

      Vous pouvez (et devrait) mettre tout cela dans une seule boucle, bien sûr.

0 commentaires
0
votes

Ceci est vraiment un problème de deux file d'attente, car les opérations de rotation tournent efficacement une pile en une file d'attente. Dans ce cas, une sorte de fusion de bas en bas peut être effectuée, ce qui serait relativement rapide.

Utilisation d'une liste liée (au lieu d'un tableau) pour implémenter la pile / la file d'attente accélérerait la rotation.

0 commentaires
0
votes

Voici une solution en Java. xxx

0 commentaires

Articles qui pourrait vous intéresser :

Que puis-je utiliser pour la conversion d'entrée au lieu de scanf?
Comment puis-je calculer a * b / c lorsque a et b sont tous deux plus petits que c, mais que a * b déborde?
Comment vérifier si un pointeur void (void *) est l'un des deux types de données?
L'écran LCD affiche des caractères aléatoires (MPLAB)