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

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

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) نگه داشته شوند. هنگامی که پشته خالی شد، همه عناصر نگه داشته شده باید یکی یکی به صورت مرتب شده قرار بگیرند. در اینجا، مرتب بودن حائز اهمیت است.

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

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

الگوریتم زیر برای قرار دادن عناصر به صورت مرتب شده است.

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

نمایش بصری:

1
2
3
4
5
6
Let given stack be
-3    <-- top of the stack
14
18
-5
30

در ادامه، مرتب‌سازی پشته با استفاده از داده‌های مثال ارائه شده در بالا، انجام خواهد شد. ابتدا، باید همه عناصر را از پشته حذف و عناصر حذف شده را در متغیر 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#) انتخاب می‌شود. به دلیل آنکه ۳۰ > ۱۸ است، ۱۸ قبل از ۳۰ قرار می‌گیرد. اکنون پشته به صورت زیر خواهد بود.

1
2
3
30    <-- top of the stack
18    
-5

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

1
2
3
4
30    <-- top of the stack
18
14    
-5

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

1
2
3
4
5
30    <-- top of the stack
18
14
-3    
-5

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

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

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

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

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

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

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

خروجی قطعه کدهای بالا، به صورت زیر است.

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

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

منبع: فرادرس

مشاوره یکشنبه 30 تیر 1398 ساعت 16:21

طراحی سایت و برنامه نویسی

طراحی سایت و برنامه نویسی