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

تعداد بازدید ها: 31

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

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

sortStack(stack S)
    if stack is not empty:
        temp = pop(S);  
        sortStack(S); 
        sortedInsert(S, temp);

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)

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
-3    <-- top of the stack
14
18
-5
30

Let given stack be

-3 <-- top of the stack

-5

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

30    <-- top of the stack
18    
-5

30 <-- top of the stack

-5

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

30    <-- top of the stack
18
14    
-5

30 <-- top of the stack

-5

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

30    <-- top of the stack
18
14
-3    
-5

30 <-- top of the stack

-3

-5

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

الگوریتم بازگشتی برای مرتب سازی پشته در زبان 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 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; 
}

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;

}

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

// 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); 
       
    } 
}

// 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

// 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

// 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

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

Stack elements before sorting:
-3 14 18 -5 30 

Stack elements after sorting:
30 18 14 -3 -5

Stack elements before sorting:

-3 14 18 -5 30

Stack elements after sorting:

30 18 14 -3 -5

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

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

به عنوان حامی، استارتاپ، محصول و خدمات خود را در انتهای مطالب مرتبط مجله فرادرس معرفی کنید.

به اشتراک بگذارید:

منبع GeeksforGeeks

الهام حصارکی

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

آیا این مطلب برای شما مفید بود؟

مهندس در وکا (WEKA) ابزاری برای یادگیری ماشین و داده کاوی — راهنمای شروع به کار نوشته است:

متشکر
مجید عوض زاده در اگزرژی (Exergy) در مکانیک — به همراه مثال نوشته است:

با سلام و تشکر بابت بازخورد ارائه شده؛ برای طراحی بهینه یک سیستم، بهتر است آنتروپی تولیدی کل سیستم میبینمم شود؛ در این صورت اگزرژی دریافتی، ماکزیمم بوده و می‌توان به نقطه بهینه طراحی دست یافت.
علیرضا در اگزرژی (Exergy) در مکانیک — به همراه مثال نوشته است:

مقالتون عالی بود فقط سوالی که داشتم چطور میتونم یک سیستم مکانیکی رو از نظر اگزرژی بهینه کنم

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