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

۵۳۰ بازدید
آخرین به‌روزرسانی: ۰۸ خرداد ۱۴۰۳
زمان مطالعه: ۶ دقیقه
مرتب سازی پشته با الگوریتم بازگشتی — به زبان ساده

در این مطلب، روش مرتب سازی پشته با الگوریتم بازگشتی مورد بررسی قرار گرفته و سپس، قطعه کدهای مربوط به آن در زبان‌های برنامه‌نویسی گوناگون شامل C، «جاوا» (Java) و «سی‌شارپ» (#C) ارائه شده است. فرض می‌شود که یک پشته (Stack) به عنوان ورودی داده شده و هدف مرتب کردن آن با استفاده از روش بازگشتی است. فرض می شود در صورت سوال نیز گفته شده که امکان استفاده از هر ساختار حلقه‌ای، مانند for ،while و دیگر موارد وجود ندارد. تنها می‌توان از توابع «نوع داده انتزاعی» (Abstract Data Type | ADT)، شامل مواردی که در ادامه آمده است، روی پشته استفاده کرد.

997696
is_empty(S) : Tests whether stack is empty or not.
push(S) : Adds new element to the stack.
pop(S) : Removes top element from the stack.
top(S) : Returns value of the top element. Note that this
function does not remove element from the stack.

مثال:

Input:  -3  <--- Top
        14 
        18 
        -5 
        30 

Output: 30  <--- Top
        18 
        14 
        -3 
        -5

این مساله، نوعی از مسائل معکوس کردن پشته است. ایده اصلی برای حل این مساله، آن است که همه مقادیر تا هنگامی که پشته خالی شود، در «پشته فراخوانی تابع» (Function Call Stack) نگه داشته شوند. هنگامی که پشته خالی شد، همه عناصر نگه داشته شده باید یکی یکی به صورت مرتب شده قرار بگیرند. در اینجا، مرتب بودن حائز اهمیت است.

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

می‌توان از الگوریتم زیر برای مرتب‌سازی عناصر پشته استفاده کرد.

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

در ادامه، مرتب‌سازی پشته با استفاده از داده‌های مثال ارائه شده در بالا، انجام خواهد شد. ابتدا، باید همه عناصر را از پشته حذف و عناصر حذف شده را در متغیر temp ذخیره کرد. پس از حذف کردن همه عناصر، فریم پشته تابع به صورت زیر خواهد بود:

temp = -3 --> stack frame #1
temp = 14 --> stack frame #2
temp = 18 --> stack frame #3
temp = -5 --> stack frame #4
temp = 30 --> stack frame #5

اکنون، پشته خالی است و تابع «()insert_in_sorted_order» فراخوانی می‌شود و ۳۰ را در پایین پشته (از فریم پشته 5#) درج می‌کند. اکنون، پشته به صورت زیر است.

30 <-- top of the stack

اکنون، عنصر بعدی یعنی ۵- (از فریم پشته 4#) انتخاب می‌شود. از آنجا که ۳۰ > ۵- است، ۵- در پایین پشته درج می‌شود. اکنون، پشته به صورت زیر خواهد بود:

30 <-- top of the stack
-5

در ادامه، ۱۸ (از فریم پشته 3#) انتخاب می‌شود. به دلیل آنکه ۳۰ > ۱۸ است، ۱۸ قبل از ۳۰ قرار می‌گیرد. اکنون پشته به صورت زیر خواهد بود.

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

سپس، ۱۴ (از فریم پشته 2#) انتخاب می‌شود. با توجه به آنکه ۳۰ > ۱۴ و ۱۸ > ۱۴، زیر ۱۸ درج می‌شود. اکنون پشته به صورت زیر خواهد بود.

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

اکنون، ۳- (از فریم پشته 1#) انتخاب می‌شود. به دلیل آنکه ۳۰ > ۳ و ۱۸ > ۳-، زیر ۱۴ قرار می‌گیرد. اکنون، پشته به صورت زیر خواهد بود.

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

در ادامه، پیاده‌سازی الگوریتم بالا در چند زبان برنامه‌نویسی ارائه شده است.

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

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} 

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

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

می‌توان با انجام دادن تغییرات کوچکی در قطعه کدهای بالا، کاری کرد که پشته به صورت نزولی مرتب شود.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *