مرتب سازی پشته با الگوریتم بازگشتی — به زبان ساده

1sortStack(stack S)
2    if stack is not empty:
3        temp = pop(S);  
4        sortStack(S); 
5        sortedInsert(S, temp);

1sortedInsert(Stack S, element)
2    if stack is empty OR element > top element
3        push(S, elem)
4    else
5        temp = pop(S)
6        sortedInsert(S, element)
7        push(S, temp)

1Let given stack be
2-3    <-- top of the stack
314
418
5-5
630

130    <-- top of the stack
218    
3-5

130    <-- top of the stack
218
314    
4-5

130    <-- top of the stack
218
314
4-3    
5-5

1// C program to sort a stack using recursion 
2#include <stdio.h> 
3#include <stdlib.h> 
4  
5// Stack is represented using linked list 
6struct stack 
7{ 
8    int data; 
9    struct stack *next; 
10}; 
11  
12// Utility function to initialize stack 
13void initStack(struct stack **s) 
14{ 
15    *s = NULL; 
16} 
17  
18// Utility function to chcek if stack is empty 
19int isEmpty(struct stack *s) 
20{ 
21    if (s == NULL) 
22        return 1; 
23    return 0; 
24} 
25  
26// Utility function to push an item to stack 
27void push(struct stack **s, int x) 
28{ 
29    struct stack *p = (struct stack *)malloc(sizeof(*p)); 
30  
31    if (p == NULL) 
32    { 
33        fprintf(stderr, "Memory allocation failed.\n"); 
34        return; 
35    } 
36  
37    p->data = x; 
38    p->next = *s; 
39    *s = p; 
40} 
41  
42// Utility function to remove an item from stack 
43int pop(struct stack **s) 
44{ 
45    int x; 
46    struct stack *temp; 
47  
48    x = (*s)->data; 
49    temp = *s; 
50    (*s) = (*s)->next; 
51    free(temp); 
52  
53    return x; 
54} 
55  
56// Function to find top item 
57int top(struct stack *s) 
58{ 
59    return (s->data); 
60} 
61  
62// Recursive function to insert an item x in sorted way 
63void sortedInsert(struct stack **s, int x) 
64{ 
65    // Base case: Either stack is empty or newly inserted 
66    // item is greater than top (more than all existing) 
67    if (isEmpty(*s) || x > top(*s)) 
68    { 
69        push(s, x); 
70        return; 
71    } 
72  
73    // If top is greater, remove the top item and recur 
74    int temp = pop(s); 
75    sortedInsert(s, x); 
76  
77    // Put back the top item removed earlier 
78    push(s, temp); 
79} 
80  
81// Function to sort stack 
82void sortStack(struct stack **s) 
83{ 
84    // If stack is not empty 
85    if (!isEmpty(*s)) 
86    { 
87        // Remove the top item 
88        int x = pop(s); 
89  
90        // Sort remaining stack 
91        sortStack(s); 
92  
93        // Push the top item back in sorted stack 
94        sortedInsert(s, x); 
95    } 
96} 
97  
98// Utility function to print contents of stack 
99void printStack(struct stack *s) 
100{ 
101    while (s) 
102    { 
103        printf("%d ", s->data); 
104        s = s->next; 
105    } 
106    printf("\n"); 
107} 
108  
109// Driver Program 
110int main(void) 
111{ 
112    struct stack *top; 
113  
114    initStack(&top); 
115    push(&top, 30); 
116    push(&top, -5); 
117    push(&top, 18); 
118    push(&top, 14); 
119    push(&top, -3); 
120  
121    printf("Stack elements before sorting:\n"); 
122    printStack(top); 
123  
124    sortStack(&top); 
125    printf("\n\n"); 
126  
127    printf("Stack elements after sorting:\n"); 
128    printStack(top); 
129  
130    return 0; 
131}

1// Java program to sort a Stack using recursion 
2// Note that here predefined Stack class is used 
3// for stack operation 
4  
5import java.util.ListIterator; 
6import java.util.Stack; 
7  
8class Test 
9{ 
10    // Recursive Method to insert an item x in sorted way 
11    static void sortedInsert(Stack<Integer> s, int x) 
12    { 
13        // Base case: Either stack is empty or newly inserted 
14        // item is greater than top (more than all existing) 
15        if (s.isEmpty() || x > s.peek()) 
16        { 
17            s.push(x); 
18            return; 
19        } 
20       
21        // If top is greater, remove the top item and recur 
22        int temp = s.pop(); 
23        sortedInsert(s, x); 
24       
25        // Put back the top item removed earlier 
26        s.push(temp); 
27    } 
28       
29    // Method to sort stack 
30    static void sortStack(Stack<Integer> s) 
31    { 
32        // If stack is not empty 
33        if (!s.isEmpty()) 
34        { 
35            // Remove the top item 
36            int x = s.pop(); 
37       
38            // Sort remaining stack 
39            sortStack(s); 
40       
41            // Push the top item back in sorted stack 
42            sortedInsert(s, x); 
43        } 
44    } 
45      
46    // Utility Method to print contents of stack 
47    static void printStack(Stack<Integer> s) 
48    { 
49       ListIterator<Integer> lt = s.listIterator(); 
50         
51       // forwarding 
52       while(lt.hasNext()) 
53           lt.next(); 
54         
55       // printing from top to bottom 
56       while(lt.hasPrevious()) 
57           System.out.print(lt.previous()+" "); 
58    } 
59    
60    // Driver method  
61    public static void main(String[] args)  
62    { 
63        Stack<Integer> s = new Stack<>(); 
64        s.push(30); 
65        s.push(-5); 
66        s.push(18); 
67        s.push(14); 
68        s.push(-3); 
69       
70        System.out.println("Stack elements before sorting: "); 
71        printStack(s); 
72       
73        sortStack(s); 
74       
75        System.out.println(" \n\nStack elements after sorting:"); 
76        printStack(s); 
77       
78    } 
79} 

1// C# program to sort a Stack using recursion  
2// Note that here predefined Stack class is used  
3// for stack operation  
4using System; 
5using System.Collections; 
6  
7public class GFG  
8{  
9    // Recursive Method to insert an item x in sorted way  
10    static void sortedInsert(Stack s, int x)  
11    {  
12        // Base case: Either stack is empty or   
13        // newly inserted item is greater than top  
14        // (more than all existing)  
15        if (s.Count == 0 || x > (int)s.Peek())  
16        {  
17            s.Push(x);  
18            return;  
19        }  
20      
21        // If top is greater, remove  
22        // the top item and recur  
23        int temp = (int) s.Peek(); 
24        s.Pop(); 
25        sortedInsert(s, x);  
26      
27        // Put back the top item removed earlier  
28        s.Push(temp);  
29    }  
30      
31    // Method to sort stack  
32    static void sortStack(Stack s)  
33    {  
34        // If stack is not empty  
35        if (s.Count > 0)  
36        {  
37            // Remove the top item  
38            int x = (int)s.Peek(); 
39            s.Pop();  
40      
41            // Sort remaining stack  
42            sortStack(s);  
43      
44            // Push the top item back in sorted stack  
45            sortedInsert(s, x);  
46        }  
47    }  
48      
49    // Utility Method to print contents of stack  
50    static void printStack(Stack s)  
51    {  
52        foreach (int c in s)  
53        { 
54            Console.Write(c + " "); 
55        }  
56    }  
57      
58    // Driver method  
59    public static void Main(String[] args)  
60    {  
61        Stack s = new Stack();  
62        s.Push(30);  
63        s.Push(-5);  
64        s.Push(18);  
65        s.Push(14);  
66        s.Push(-3);  
67      
68        Console.WriteLine("Stack elements before sorting: ");  
69        printStack(s);  
70      
71        sortStack(s);  
72      
73        Console.WriteLine(" \n\nStack elements after sorting:");  
74        printStack(s);  
75      
76    }  
77} 
78  
79// This code is Contibuted by Arnab Kundu

1Stack elements before sorting:
2-3 14 18 -5 30 
3
4Stack elements after sorting:
530 18 14 -3 -5