recursion သုံးပြီး stack Sort


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Goldman Sachs IBM က Kuliza Yahoo က
နေ့တိုင်းပြန်လည်စတင်မည် စုပုံထား

ပြProbleနာဖော်ပြချက်

ပြrecနာက“ နည်းလမ်းတစ်ခုကိုအသုံးပြုပြီးစာသားကိုစီပါ” ကသင့်အားပေးသည်ဟုဖော်ပြထားသည် စုပုံထား ဒေတာဖွဲ့စည်းပုံ။ စီ recursion သုံးပြီး၎င်း၏ဒြပ်စင်။ အောက်ဖော်ပြပါစာရင်း၏လုပ်ဆောင်ချက်များကိုသာအသုံးပြုနိုင်သည် -

  • push (element) - element ထဲကိုထည့်လိုက်မယ်။
  • pop () - pop () - ပေးထားသော stack ထိပ်ရှိ element ကိုဖယ်ရှား / ဖျက်ရန်။
  • isEmpty () - stack ထဲတွင်မည်သည့် element ရှိသလဲဆိုလျှင်စစ်ဆေးရန်။
  • top () - ပေးထားတဲ့ stack ရဲ့ထိပ်မှာ element ကိုကြည့်ဖို့ / ကြည့်ဖို့။

recursion သုံးပြီး stack Sort

နမူနာ

9 4 2 -1 6 20
20 9 6 4 2 -1

ရှင်းလင်းချက်။ ။ stack ကိုအစဉ်လိုက်စီထားတာ။ အများဆုံးဒြပ်စင်ထိပ်မှာလာသည်။ အဘယ်ကြောင့်ဆိုသော် stack သည် LIFO ၏ဒေတာဖွဲ့စည်းတည်ဆောက်ပုံဖြစ်သည်။

2 1 4 3 6 5
6 5 4 3 2 1

algorithm

  1. ကန ဦး စတင်သည် စုပုံထား နှင့်ဒြပ်စင်တွန်း။
  2. Stack တစ်ခုနှင့် element တစ်ခုကို parameter အဖြစ်လက်ခံသော stack ထဲတွင် element များကို sorted order ဖြင့်ထည့်ရန် function တစ်ခုကိုဖန်တီးပါ။ stack ဗလာလားဒါမှမဟုတ်ပေးထားတဲ့ element က stack ရဲ့ထိပ်မှာရှိတဲ့ element ထက်ကြီးလားဆိုတာစစ်ဆေးပါ၊ stack ထဲက element ကိုတွန်းပြီးပြန်လာပါ။
  3. ယာယီ variable တစ်ခုကိုဖန်တီးပြီး၎င်းရဲ့ထိပ်ကိုသိုထားပါ။ element ကို stack ရဲ့ထိပ်မှာ pop နဲ့ function ကိုသူ့ဟာသူမှ recursive ခေါ်ဆိုခပါစေ။ stack အတွင်းရှိယာယီ variable ကိုတွန်းပါ။
  4. အလားတူစွာ stack ကို parameter တစ်ခုအဖြစ်လက်ခံသော function sort () ကိုဖန်တီးပါ။ stack ဗလာမဟုတ်ကိုစစ်ဆေးပါ၊ x ကို variable တစ်ခုဖန်တီးပါ။ element ကို stack ရဲ့ထိပ်မှာ pop ။ လုပ်ဆောင်ချက်ကိုသူ့ဟာသူမှပြန်လည်ထူထောင်ခေါ်ဆိုမှုလုပ်ပါ။ Stack ထဲတွင် element များကို sorted order ဖြင့်ထည့်ရန် function ကိုခေါ်ပါ။
  5. အဓိက () တွင် sort function ကိုခေါ်ပါ။
  6. stack ကို parameter အဖြစ်လက်ခံသော sorted stack ကို print ထုတ်ရန် function တစ်ခုကိုဖန်တီးပါ။ stack အချည်းနှီးဖြစ်နေစဉ် Travers, stack ၏ဒေတာများကို print ထုတ်ခြင်းနှင့်နောက်ဒြပ်စင်သို့ရွှေ့။

ကုဒ်

Recursion ကိုအသုံးပြု။ stack sort ဖို့ C ++ အစီအစဉ်

#include <iostream> 
using namespace std; 
  
struct stack{  
    int data;  
    struct stack *next;  
};  
  
void initStack(struct stack **s){  
    *s = NULL;  
}  
  
int isEmpty(struct stack *s){  
    if(s == NULL){  
        return 1;  
    }    
    return 0;  
}  
  
void push(struct stack **s, int x){
    
    struct stack *p = (struct stack *)malloc(sizeof(*p));  
  
    if(p == NULL){  
        return;  
    }  
  
    p->data = x;  
    p->next = *s;  
    *s = p;  
}  
  
int pop(struct stack **s){  
    int x;  
    struct stack *temp;  
  
    x = (*s)->data;  
    temp = *s;  
    (*s) = (*s)->next;  
    free(temp);  
  
    return x;  
}  
  
int top(struct stack *s){  
    return (s->data);  
}  
  
void InsertWithSort(struct stack **s, int x){  
    
    if(isEmpty(*s) or x > top(*s)){  
        push(s, x);  
        return;  
    }  
  
    int temp = pop(s);  
    InsertWithSort(s, x);  
  
    push(s, temp);  
}  
  
void sort(struct stack **s){  
    
    if(!isEmpty(*s)){  
        int x = pop(s);  
  
        sort(s);  
  
        InsertWithSort(s, x);  
    }  
}  
  
void print(struct stack *s){  
    while(s){  
        cout<<s->data<<" "; 
        s = s->next;  
    }  
}  
  
int main(){  
    struct stack *top;  
  
    initStack(&top);
    
    push(&top, 9);  
    push(&top, 4);  
    push(&top, 2);  
    push(&top, -1);  
    push(&top, 6);
    push(&top, 20);
  
    sort(&top);  
    
    print(top);  
  
    return 0;  
}
20 9 6 4 2 -1

Recursion ကိုအသုံးပြု။ stack sort ဖို့ Java ကိုအစီအစဉ်

import java.util.ListIterator; 
import java.util.Stack; 
  
class SortStack{ 
    
    static void InsertWithSort(Stack<Integer> s, int x){ 
        if (s.isEmpty() || x > s.peek()){ 
            s.push(x); 
            return; 
        } 
       
        int temp = s.pop(); 
        InsertWithSort(s, x); 
       
        s.push(temp); 
    } 
       
    static void sort(Stack<Integer> s){ 
        if(!s.isEmpty()){ 
            int x = s.pop(); 
       
            sort(s); 
       
            InsertWithSort(s, x); 
        } 
    } 
      
    static void print(Stack<Integer> s){ 
       ListIterator<Integer> lt = s.listIterator(); 
         
        while(lt.hasNext()){ 
            lt.next(); 
        }       
         
        while(lt.hasPrevious()){ 
           System.out.print(lt.previous()+" ");
        }   
    } 
    
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>(); 
        
        s.push(9);  
        s.push(4);  
        s.push(2);  
        s.push(-1);  
        s.push(6);
        s.push(20); 
       
        sort(s); 
       
        print(s); 
       
    } 
}
20 9 6 4 2 -1

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N ^ 2) ဘယ်မှာ n က stack ထဲက element အရေအတွက်ဖြစ်တယ်။ ဘာလို့လဲဆိုတော့ element ကို stack ထဲမှာတွန်းလိုက်ရင် stack ထဲမှာရှိနေတဲ့ element အားလုံးကိုဖယ်ထုတ်ပြီးထည့်လိုက်တာနဲ့အဆုံးသတ်သွားမှာပါ။ အကယ်၍ သွင်းအားစုသည်အစီအစဉ်ကျဆင်းနေလျှင်ဤကိစ္စကိုဖြစ်ပေါ်စေသည်။

အာကာသရှုပ်ထွေးမှု

အို (N) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာ n element တွေအတွက် stack space ကိုသုံးခဲ့တဲ့အတွက်။ ကျွန်တော်တို့ရဲ့လက်ရှိဒြပ်စင်ထားရန်ဒြပ်စင်ကိုဖယ်ရှားနေစဉ်။ ဖယ်ရှားလိုက်သောဒြပ်စင်များကိုကျွန်ုပ်တို့သိုလှောင်ထားရပြီး၎င်းသည်ကျွန်ုပ်တို့အား linear space ရှုပ်ထွေးစေသည်။