در این مطلب، روش مرتب سازی پشته با الگوریتم بازگشتی مورد بررسی قرار گرفته و سپس، قطعه کدهای مربوط به آن در زبان‌های برنامه‌نویسی گوناگون شامل 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
۱۴
۱۸
-۵
۳۰
Output: 30 <--- Top
۱۸
۱۴
-۳
-۵این مساله، نوعی از مسائل معکوس کردن پشته است. ایده اصلی برای حل این مساله، آن است که همه مقادیر تا هنگامی که پشته خالی شود، در «پشته فراخوانی تابع» (Function Call Stack) نگه داشته شوند. هنگامی که پشته خالی شد، همه عناصر نگه داشته شده باید یکی یکی به صورت مرتب شده قرار بگیرند. در اینجا، مرتب بودن حائز اهمیت است.
مرتب سازی پشته با الگوریتم بازگشتی
می‌توان از الگوریتم زیر برای مرتب‌سازی عناصر پشته استفاده کرد.
|
۱ ۲ ۳ ۴ ۵ |
sortStack(stack S) if stack is not empty: temp = pop(S); sortStack(S); sortedInsert(S, temp); |
الگوریتم زیر برای قرار دادن عناصر به صورت مرتب شده است.
|
۱ ۲ ۳ ۴ ۵ ۶ ۷ |
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) |
نمایش بصری:
|
۱ ۲ ۳ ۴ ۵ ۶ |
Let given stack be -۳ <-- top of the stack ۱۴ ۱۸ -۵ ۳۰ |
در ادامه، مرتب‌سازی پشته با استفاده از داده‌های مثال ارائه شده در بالا، انجام خواهد شد. ابتدا، باید همه عناصر را از پشته حذف و عناصر حذف شده را در متغیر 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» فراخوانی می‌شود و ۳۰ را در پایین پشته (از فریم پشته ۵#) درج می‌کند. اکنون، پشته به صورت زیر است.
۳۰ <-- top of the stack
اکنون، عنصر بعدی یعنی ۵- (از فریم پشته ۴#) انتخاب می‌شود. از آنجا که ۳۰ > ۵- است، ۵- در پایین پشته درج می‌شود. اکنون، پشته به صورت زیر خواهد بود:
۳۰ <-- top of the stack -۵
در ادامه، ۱۸ (از فریم پشته ۳#) انتخاب می‌شود. به دلیل آنکه ۳۰ > ۱۸ است، ۱۸ قبل از ۳۰ قرار می‌گیرد. اکنون پشته به صورت زیر خواهد بود.
|
۱ ۲ ۳ |
۳۰ <-- top of the stack ۱۸ -۵ |
سپس، ۱۴ (از فریم پشته ۲#) انتخاب می‌شود. با توجه به آنکه ۳۰ > ۱۴ و ۱۸ > ۱۴، زیر ۱۸ درج می‌شود. اکنون پشته به صورت زیر خواهد بود.
|
۱ ۲ ۳ ۴ |
۳۰ <-- top of the stack ۱۸ ۱۴ -۵ |
اکنون، ۳- (از فریم پشته ۱#) انتخاب می‌شود. به دلیل آنکه ۳۰ > ۳ و ۱۸ > ۳-، زیر ۱۴ قرار می‌گیرد. اکنون، پشته به صورت زیر خواهد بود.
|
۱ ۲ ۳ ۴ ۵ |
۳۰ <-- top of the stack ۱۸ ۱۴ -۳ -۵ |
در ادامه، پیاده‌سازی الگوریتم بالا در چند زبان برنامه‌نویسی ارائه شده است.
الگوریتم بازگشتی برای مرتب سازی پشته در زبان C
|
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ ۲۶ ۲۷ ۲۸ ۲۹ ۳۰ ۳۱ ۳۲ ۳۳ ۳۴ ۳۵ ۳۶ ۳۷ ۳۸ ۳۹ ۴۰ ۴۱ ۴۲ ۴۳ ۴۴ ۴۵ ۴۶ ۴۷ ۴۸ ۴۹ ۵۰ ۵۱ ۵۲ ۵۳ ۵۴ ۵۵ ۵۶ ۵۷ ۵۸ ۵۹ ۶۰ ۶۱ ۶۲ ۶۳ ۶۴ ۶۵ ۶۶ ۶۷ ۶۸ ۶۹ ۷۰ ۷۱ ۷۲ ۷۳ ۷۴ ۷۵ ۷۶ ۷۷ ۷۸ ۷۹ ۸۰ ۸۱ ۸۲ ۸۳ ۸۴ ۸۵ ۸۶ ۸۷ ۸۸ ۸۹ ۹۰ ۹۱ ۹۲ ۹۳ ۹۴ ۹۵ ۹۶ ۹۷ ۹۸ ۹۹ ۱۰۰ ۱۰۱ ۱۰۲ ۱۰۳ ۱۰۴ ۱۰۵ ۱۰۶ ۱۰۷ ۱۰۸ ۱۰۹ ۱۱۰ ۱۱۱ ۱۱۲ ۱۱۳ ۱۱۴ ۱۱۵ ۱۱۶ ۱۱۷ ۱۱۸ ۱۱۹ ۱۲۰ ۱۲۱ ۱۲۲ ۱۲۳ ۱۲۴ ۱۲۵ ۱۲۶ ۱۲۷ ۱۲۸ ۱۲۹ ۱۳۰ ۱۳۱ |
// 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 ۱; return ۰; } // 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, ۳۰); push(&top, -۵); push(&top, ۱۸); push(&top, ۱۴); push(&top, -۳); printf("Stack elements before sorting:\n"); printStack(top); sortStack(&top); printf("\n\n"); printf("Stack elements after sorting:\n"); printStack(top); return ۰; } |
الگوریتم بازگشتی برای مرتب سازی پشته در زبان جاوا
|
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ ۲۶ ۲۷ ۲۸ ۲۹ ۳۰ ۳۱ ۳۲ ۳۳ ۳۴ ۳۵ ۳۶ ۳۷ ۳۸ ۳۹ ۴۰ ۴۱ ۴۲ ۴۳ ۴۴ ۴۵ ۴۶ ۴۷ ۴۸ ۴۹ ۵۰ ۵۱ ۵۲ ۵۳ ۵۴ ۵۵ ۵۶ ۵۷ ۵۸ ۵۹ ۶۰ ۶۱ ۶۲ ۶۳ ۶۴ ۶۵ ۶۶ ۶۷ ۶۸ ۶۹ ۷۰ ۷۱ ۷۲ ۷۳ ۷۴ ۷۵ ۷۶ ۷۷ ۷۸ ۷۹ |
// 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(۳۰); s.push(-۵); s.push(۱۸); s.push(۱۴); s.push(-۳); System.out.println("Stack elements before sorting: "); printStack(s); sortStack(s); System.out.println(" \n\nStack elements after sorting:"); printStack(s); } } |
الگوریتم بازگشتی برای مرتب سازی پشته در زبان #C
|
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ ۲۶ ۲۷ ۲۸ ۲۹ ۳۰ ۳۱ ۳۲ ۳۳ ۳۴ ۳۵ ۳۶ ۳۷ ۳۸ ۳۹ ۴۰ ۴۱ ۴۲ ۴۳ ۴۴ ۴۵ ۴۶ ۴۷ ۴۸ ۴۹ ۵۰ ۵۱ ۵۲ ۵۳ ۵۴ ۵۵ ۵۶ ۵۷ ۵۸ ۵۹ ۶۰ ۶۱ ۶۲ ۶۳ ۶۴ ۶۵ ۶۶ ۶۷ ۶۸ ۶۹ ۷۰ ۷۱ ۷۲ ۷۳ ۷۴ ۷۵ ۷۶ ۷۷ ۷۸ ۷۹ |
// 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 == ۰ || 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 > ۰) { // 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(۳۰); s.Push(-۵); s.Push(۱۸); s.Push(۱۴); s.Push(-۳); 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 |
|
۱ ۲ ۳ ۴ ۵ |
Stack elements before sorting: -۳ ۱۴ ۱۸ -۵ ۳۰ Stack elements after sorting: ۳۰ ۱۸ ۱۴ -۳ -۵ |
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان داده‌ها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
^^
