Comment sortinger une stack en utilisant uniquement des opérations de stack?

J’ai trouvé cette question sur le web.

Avec une stack S, écrivez un programme C pour sortinger la stack (dans l’ordre croissant). Nous ne sums pas autorisés à émettre des hypothèses sur la manière dont la stack est mise en œuvre. Les seules fonctions à utiliser sont:

Push Pop Top IsEmpty IsFull 

Je pense que nous pouvons construire un tas et le sortinger. Quelle est la solution optimale à cela?

En supposant que la seule structure de données autorisée ici soit la stack, vous pouvez utiliser 2 stacks.

Itérez jusqu’à ce que la stack d’origine soit vide et, à chaque itération, retirez un élément de la stack d’origine, tandis que l’élément supérieur de la deuxième stack est plus grand que l’élément supprimé, sautez la deuxième stack et placez-le dans la stack d’origine. Vous pouvez maintenant pousser l’élément que vous avez initialement extrait de la stack d’origine vers la deuxième stack.

La complexité temporelle de cette approche est O (N ^ 2).

Le code C pour implémenter cet algorithme serait (excusez mes compétences C rouillées):

 void SortStack(struct Stack * orig_stack) { struct Stack helper_stack; while (!IsEmpty(orig_stack)) { int element = Pop(orig_stack); while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element) { Push(orig_stack, Pop(&helper_stack)); } Push(&helper_stack, element); } while (!IsEmpty(&helper_stack)) { Push(orig_stack, Pop(&helper_stack)); } } 

Étant donné ces opérations de stack, vous pouvez écrire un type d’insertion récursif.

 void sort(stack s) { if (!IsEmpty(s)) { int x = Pop(s); sort(s); insert(s, x); } } void insert(stack s, int x) { if (!IsEmpty(s)) { int y = Top(s); if (x < y) { Pop(s); insert(s, x); Push(s, y); } else { Push(s, x); } } else { Push(s, x); } } 

Cela peut être fait de manière récursive en utilisant la même stack. O (n ^ 2) Je l’ai codé en C ++ mais la conversion en C est sortingviale. J’aime juste les modèles et vous avez tagué votre question en C ++

 template void Insert(const T& element, Stack& stack) { if(element > stack.Top()) { T top = stack.Pop(); Insert(element, stack); stack.Push(top); } else { stack.Push(element); } } template void StackSort(Stack& stack) { if(!stack.IsEmpty()) { T top = stack.Pop(); StackSort(stack); Insert(top, stack); } } 

Edité pour récupérer mon vote! :))

Le sorting de crêpes est un autre moyen intéressant de le faire: http://en.wikipedia.org/wiki/Pancake_sorting#cite_note-4 .

Code modifié à partir de la réponse de T33C
(donné avant que Svante ait corrigé la balise de langage de c ++ à c )):
stack.top() ne peut être vérifié que si !stack.empty()

 void insert(int element, stack &stack) { if (!stack.empty() && element > stack.top()) { int top = stack.top(); stack.pop(); insert(element, stack); stack.push(top); } else { stack.push(element); } } void sortStack(stack & stack) { if (!stack.empty()) { int top = stack.top(); stack.pop(); sortStack(stack); insert(top, stack); } } 

Tri en stack utilisant le sorting par fusion polyphasé

Cela devrait être le moyen le plus rapide d’implémenter un sorting à 3 stacks. L’objective est de créer une séquence ascendante au fur et à mesure que les éléments sont extraits d’une stack sortingée.

Article de wiki sur le sorting par fusion polyphasée (à l’aide de tableaux):

http://en.wikipedia.org/wiki/Polyphase_merge_sort

Exemple de code C ++ pour le sorting polyphasé à 3 stacks, utilisant des pointeurs, un pointeur en tant que pointeur de stack pour chaque stack et un pointeur vers la fin de chaque exécution et la fin de chaque stack. Le pointeur de taille d’exécution est utilisé pour garder trace du moment où la taille d’exécution augmente ou diminue en milieu de stack. Un indicateur de séquence décroissant est utilisé pour garder la trace si les séquences sont décroissantes ou croissantes lorsque les données sont transférées entre les stacks. Il est initialisé au début, puis alterne une fois que chaque paire est fusionnée.

 typedef unsigned int uint32_t; static size_t fibtbl[48] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733,1134903170,1836311903,2971215073}; // binary search: return index of largest fib() <= n size_t flfib(size_t n) { size_t lo = 0; size_t hi = sizeof(fibtbl)/sizeof(fibtbl[0]); while((hi - lo) > 1){ size_t i = (lo + hi)/2; if(n < fibtbl[i]){ hi = i; continue; } if(n > fibtbl[i]){ lo = i; continue; } return i; } return lo; } // poly phase merge sort array using 3 arrays as stacks, a is source uint32_t * ppmrg3s(uint32_t a[], uint32_t b[], uint32_t c[], size_t n) { if(n < 2) return a+n; uint32_t *asp = a; // a stack ptr uint32_t *aer; // a end run uint32_t *aes = a + n; // a end uint32_t *bsp = b + n; // b stack ptr uint32_t *ber; // b end run uint32_t *bes = b + n; // b end uint32_t *csp = c + n; // c stack ptr uint32_t *ces = c + n; // c end uint32_t *rsp = 0; // run size change stack ptr size_t ars = 1; // run sizes size_t brs = 1; size_t scv = 0-1; // size change increment / decrement bool dsf; // == 1 if descending sequence { // block for local variable scope size_t f = flfib(n); // fibtbl[f+1] > n >= fibtbl[f] dsf = ((f%3) == 0); // init compare flag if(fibtbl[f] == n){ // if exact fibonacci size, move to b for(size_t i = 0; i < fibtbl[f-1]; i++) *(--bsp) = *(asp++); } else { // else move to b, c // update compare flag dsf ^= (n - fibtbl[f]) & 1; // move excess elements to b aer = a + n - fibtbl[f]; while (asp < aer) *(--bsp) = *(asp++); // move dummy count elements to c aer = a + fibtbl[f - 1]; while (asp < aer) *(--csp) = *(asp++); rsp = csp; // set run size change ptr } } // end local variable block while(1){ // setup to merge pair of runs if(asp == rsp){ // check for size count change ars += scv; // (due to dummy run size == 0) scv = 0-scv; rsp = csp; } if(bsp == rsp){ brs += scv; scv = 0-scv; rsp = csp; } aer = asp + ars; // init end run ptrs ber = bsp + brs; while(1){ // merging pair of runs if(dsf ^ (*asp <= *bsp)){ // if a <= b *(--csp) = *(asp++); // move a to c if(asp != aer) // if not end a run continue; // continue back to compare do // else move rest of b run to c *(--csp) = *(bsp++); while (bsp < ber); break; // and break } else { // else a > b *(--csp) = *(bsp++); // move b to c if(bsp != ber) // if not end b run continue; // continue back to compare do // else move rest of a run to c *(--csp) = *(asp++); while (asp < aer); break; // and break } } // end merging pair of runs dsf ^= 1; // toggle compare flag if(bsp == bes){ // if b empty if(asp == aes) // if a empty, done break; std::swap(bsp, csp); // swap b, c std::swap(bes, ces); brs += ars; // update run size } else { // else b not empty if(asp != aes) // if a not empty continue; // continue back to setup next merge std::swap(asp, csp); // swap a, c std::swap(aes, ces); ars += brs; // update run size } } return csp; // return ptr to sorted array } 

Exemple de code Java pour le sorting à l'aide d'une classe de stack personnalisée (xstack) incluant une fonction d'échange.

 static final int[] FIBTBL = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733,1134903170,1836311903}; // return index of largest fib() <= n static int flfib(int n) { int lo = 0; int hi = 47; while((hi - lo) > 1){ int i = (lo + hi)/2; if(n < FIBTBL[i]){ hi = i; continue; } if(n > FIBTBL[i]){ lo = i; continue; } return i; } return lo; } // poly phase merge sort using 3 stacks static void ppmrg3s(xstack a, xstack b, xstack c) { if(a.size() < 2) return; int ars = 1; // init run sizes int brs = 1; int asc = 0; // no size change int bsc = 0; int csc = 0; int scv = 0-1; // size change value boolean dsf; // == 1 if descending sequence { // block for local variable scope int f = flfib(a.size()); // FIBTBL[f+1] > size >= FIBTBL[f] dsf = ((f%3) == 0); // init compare flag if(FIBTBL[f] == a.size()){ // if exact fibonacci size, for (int i = 0; i < FIBTBL[f - 1]; i++) { // move to b b.push(a.pop()); } } else { // else move to b, c // update compare flag dsf ^= 1 == ((a.size() - FIBTBL[f]) & 1); // i = excess run count int i = a.size() - FIBTBL[f]; // j = dummy run count int j = FIBTBL[f + 1] - a.size(); // move excess elements to b do{ b.push(a.pop()); }while(0 != --i); // move dummy count elements to c do{ c.push(a.pop()); }while(0 != --j); csc = c.size(); } } // end block while(true){ // setup to merge pair of runs if(asc == a.size()){ // check for size count change ars += scv; // (due to dummy run size == 0) scv = 0-scv; asc = 0; csc = c.size(); } if(bsc == b.size()){ brs += scv; scv = 0-scv; bsc = 0; csc = c.size(); } int arc = ars; // init run counters int brc = brs; while(true){ // merging pair of runs if(dsf ^ (a.peek() <= b.peek())){ c.push(a.pop()); // move a to c if(--arc != 0) // if not end a continue; // continue back to compare do{ // else move rest of b run to c c.push(b.pop()); }while(0 != --brc); break; // and break } else { c.push(b.pop()); // move b to c if(0 != --brc) // if not end b continue; // continue back to compare do{ // else move rest of a run to c c.push(a.pop()); }while(0 != --arc); break; // and break } } // end merging pair of runs dsf ^= true; // toggle compare flag if(b.empty()){ // if end b if(a.empty()) // if end a, done break; b.swap(c); // swap b, c brs += ars; if (0 == asc) bsc = csc; } else { // else not end b if(!a.empty()) // if not end a continue; // continue back to setup next merge a.swap(c); // swap a, c ars += brs; if (0 == bsc) asc = csc; } } a.swap(c); // return sorted stack in a } 

Si vous ne disposez d’aucune information supplémentaire sur le contenu de la stack, vous êtes pratiquement bloqué. Il vous suffit de prendre toutes les données, de les sortinger et de les remettre. Heapsort serait bien ici, tout comme quicksort ou introsort.

S’il n’y a pas de limitation à utiliser d’autres structures de données, je dirais le tas minimum. chaque fois que vous sortez un élément de la stack, mettez-le dans le tas. Lorsque le popping est terminé, prenez un élément du haut du tas (minimum du rest) et poussez-le dans la stack. Répéter ce processus jusqu’à ce que le tas soit vide.

Pour créer un tas, le temps moyen est O (nlogn); pour supprimer des éléments du tas et les remettre en ordre croissant, le temps moyen est également 0 (nlogn).

De quoi ça a l’air?

Notez que la réponse de Michael J. Barber (voir ci-dessus) n’est pas correcte, ce qui oublie de repousser l’élément dans la stack lorsqu’il est vide. La version correcte est la suivante:

 void sort(stack s) { if (!IsEmpty(s)) { int x = Pop(s); sort(s); insert(s, x); } } void insert(stack s, int x) { if (!IsEmpty(s)) { int y = Top(s); if (x < y) { Pop(s); insert(s, x); Push(s, y); } else { Push(s, x); } } else { Push(s, x); // !!! must step, otherwise, the stack will eventually be empty after sorting !!! } } 

Voici la solution en Javascript basée sur la réponse donnée par @OrenD

 var org = [4,67,2,9,5,11,3]; var helper = []; while(org.length > 0){ var temp = org.pop(); while((helper.length > 0) && (helper[helper.length-1] < temp)){ org.push(helper.pop()); } helper.push(temp); } while(helper.length > 0){ org.push(helper.pop()); } 

Jeu de trois stacks

Avec trois stacks S (stack source, la stack avec des éléments non sortingés), A, B, vous pouvez commencer à jouer à un jeu similaire au sorting par fusion.

Je pense qu’il est clair que si vous avez commandé des éléments sur A et B (dans le même sens, ascendant ou descendant), vous pouvez utiliser S pour fusionner les types A et B, puis déplacer le résultat, par exemple, B .

Le fait que vous ayez des éléments sur A, B ou S ne vous empêche pas de pouvoir utiliser A, B ou S pour la fusion (, tant que vous avez le marqueur de la taille actuelle de A, B et S ne dépasserait pas). Si votre procédure apporte des éléments ordonnés sur S, il n’est pas logique d’utiliser A et B pour supprimer la partie sortingée en A ou B dans la direction de votre choix: vous pouvez la placer dans l’ordre inverse de A ou B directement, ou par exemple , placez tous les éléments en A et inversez encore une fois en B.

Supposons que vous avez 4 éléments sortingés sur A, 16 sur B et des éléments non sortingés sur S.

A.push (S.pop) et créez maintenant une fusion sortingée en 2 éléments. Encore une fois B.push (S.pop) et créez une autre fusion sortingée à 2 éléments. Si les fusions ne sont pas séparées et / ou ne vont pas dans la même direction, vous pouvez manipuler les éléments comme bon vous semble jusqu’à atteindre la fusion sortingée à 4 éléments sur B (ou même S). Maintenant, fusionnez la fusion sortingée à 4 éléments initiale de A et cette partie sur B, jusqu’à atteindre la fusion sortingée à 8 éléments.

Vous répétez tout jusqu’à ce que vous créiez une autre fusion sortingée en 8 éléments. Vous le placez dans le bon ordre sur B (ou S) et fusionnez afin d’obtenir une fusion sortingée à 16 éléments. Maintenant, vous le placez sur A (ou S) et fusionnez avec la fusion de 16 éléments que nous avons eu sur B tout au long.

L’implémentation optimisée est délicate car vous devez réduire le nombre de fusions sortingées déplacées (inversées) d’une stack à une autre. Cependant, si vous corrigez et décidez pour quoi vous allez utiliser A, B et S et que vous forcez par exemple: A à contenir la partie fusionnée la plus petite et la plus grande B dans un ordre décroissant, l’algorithme est plus simple.

Le fait que vous ayez besoin de déplacer certains éléments supérieurs d’une stack à une autre ajoute un facteur constant à la complexité, mais il n’est jamais supérieur à 2. Sinon, la complexité est n * log (n) (vous atteignez un 2n-élément fusionner en fusionnant en fusionnant 2 fusions sortingées en n éléments, et une fusion ne nécessite pas plus de 2n étapes.)

Implémentation en C # (d’autres langages similaires sont évidents)

  void Stacking(Stack sourceStack, Stack mainStack, Stack childStack, int n) { if (n == 0) return; if (n == 1) { mainStack.Push(sourceStack.Pop()); return; } int mainSize = n/2; int childSize = n - n/2; Stacking(sourceStack, mainStack, childStack, mainSize); Stacking(sourceStack, childStack, mainStack, childSize); while (true) { while (mainSize > 0 && mainStack.Peek() >= childStack.Peek()) { sourceStack.Push(mainStack.Pop()); mainSize--; } if (mainSize == 0) break; while (childSize > 0 && childStack.Peek() >= mainStack.Peek()) { sourceStack.Push(childStack.Pop()); childSize--; } if (childSize == 0) break; } while (mainSize > 0) { sourceStack.Push(mainStack.Pop()); mainSize--; } while (childSize > 0) { sourceStack.Push(childStack.Pop()); childSize--; } for (int i = 0; i < n; i++) mainStack.Push(sourceStack.Pop()); } void SortStack(Stack sourceStack) { int n = sourceStack.Count(); // possible optimization: if (n < 2) return; Stack mainStack = new Stack(); Stack childStack = new Stack(); Stacking(sourceStack, mainStack, childStack, n); for (int i = 0; i < n; i++) sourceStack.Push(mainStack.Pop()); } 

Jeu de stacks

La procédure ci-dessus pourrait être simplifiée si vous êtes autorisé à utiliser la plupart des stacks de journaux (n). Ce nombre de stacks ne signifie pas que vous utiliserez jamais un espace supplémentaire supérieur à n. Vous marquez simplement les stacks qui seront utilisées pour fusionner les éléments 1, 2, 4 .... Dans ce cas, vous ne vous souciez pas de l'ordre car la fusion de parties de 2 ^ n sera toujours sortingée dans le même sens. Cependant, cette solution ne fait que contourner le fait que vous êtes limité à l'utilisation des opérations push et pop; autre que cela équivaut à fusionner le sorting dans tous les aspects. En substance, si le nombre de stacks n'est pas limité, vous pouvez également émuler un sorting rapide.

 /* the basic idea is we go on * popping one element (o) from the original stack (s) and we * compare it with the new stack (temp) * if o (the popped element from original stack) * is < the peek element from new stack temp * then we push the new stack element to original stack * and recursively keep calling till temp is not empty * and then push the element at the right place. * else we push the element to the new stack temp * (o >= new temp stack. * * Entire logic is recursive. */ public void sortstk( Stack s ) { Stack temp = new Stack(); while( !s.isEmpty() ) { int s1 = (int) s.pop(); while( !temp.isEmpty() && (temp.peek() > s1) ) { s.push( temp.pop() ); } temp.push( s1 ); } // Print the entire sorted stack from temp stack for( int i = 0; i < temp.size(); i++ ) { System.out.println( temp.elementAt( i ) ); } } 

Je pense que la sorte de bulle pourrait fonctionner sur la stack avec la récursivité.

  void sortStack(stack& st){ bool flag = true; int n = st.size(); for(int i = 1; i <= n - 1 && flag; i++){ flag = false; bubbleSortStack(st, flag, i); } } void bubbleSortStack(stack& st, bool& flag, int endSize){ if(st.size() == endSize) return; int val = st.top(); st.pop(); if(val > st.top()){ flag = true; int tmp = st.top(); st.push(val); val = tmp; } bubbleSortStack(st, flag); st.push(val); }