પુનરાવર્તનનો ઉપયોગ કરીને સ્ટેકને સ Sર્ટ કરો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન ગોલ્ડમૅન સૅશ IBM કુલીઝા યાહૂ
રિકર્ઝન સ્ટેક

સમસ્યા નિવેદન

સમસ્યા "રિકર્ઝનનો ઉપયોગ કરીને સ્ટેકને સ Sર્ટ કરો" કહે છે કે તમને એ સ્ટેક ડેટા સ્ટ્રક્ચર. સૉર્ટ રિકર્ઝનનો ઉપયોગ કરીને તેના તત્વો. સ્ટેકની ફક્ત નીચે સૂચિબદ્ધ કાર્યોનો ઉપયોગ કરી શકાય છે -

  • દબાણ (તત્વ) - સ્ટેકમાં તત્વ દાખલ કરવા માટે.
  • પ (પ () - પ popપ () - આપેલ સ્ટેકની ટોચ પર તત્વને દૂર કરવા / કા deleteી નાખવા.
  • isEmpty () - સ્ટેકમાં કોઈ તત્વ છે કે નહીં તે તપાસો.
  • ટોપ () - આપેલ સ્ટેકની ટોચ પર તત્વ ડોકિયું / જોવા માટે.

પુનરાવર્તનનો ઉપયોગ કરીને સ્ટેકને સ Sર્ટ કરો

ઉદાહરણ

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

સમજૂતી: સ્ટેક ચડતા ક્રમમાં ગોઠવેલ હોવાથી. મહત્તમ તત્વ ટોચ પર આવે છે. સ્ટેક એ LIFO ડેટા સ્ટ્રક્ચર હોવાથી, આઉટપુટ ઉતરતા ક્રમમાં હોય તેવું લાગે છે.

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

અલ્ગોરિધમ

  1. પ્રારંભ કરો એ સ્ટેક અને તેમાં તત્વોને દબાણ કરો.
  2. સ્ટેકમાં સ elementsર્ટ ક્રમમાં તત્વો શામેલ કરવા માટે એક ફંક્શન બનાવો જે સ્ટેક અને પરિમાણ તરીકે તત્વને સ્વીકારે છે. તપાસો કે સ્ટેક ખાલી છે અથવા આપેલ તત્વ સ્ટેકની ટોચ પરના તત્વ કરતા વધારે છે, તત્વને સ્ટેકમાં દબાણ કરો અને પાછા ફરો.
  3. એક અસ્થાયી ચલ બનાવો અને તેમાં સ્ટેકની ટોચ સ્ટોર કરો. સ્ટેકની ટોચ પર તત્વ પ Popપ કરો અને ફંકશનમાં જ રિકરિવ ક callલ કરો. સ્ટેકમાં અસ્થાયી ચલ દબાણ કરો.
  4. એ જ રીતે, ફંકશન સ sortર્ટ બનાવો () જે પેરામીટર તરીકે સ્ટેકને સ્વીકારે છે. સ્ટેક ખાલી નથી કે નહીં તે તપાસો, ચલ x બનાવો અને તેમાં સ્ટેકની ટોચ સ્ટોર કરો. સ્ટેકની ટોચ પર તત્વ પ Popપ કરો. ફંક્શનમાં જ એક રિકરિવ ક callલ કરો. સ્ટેકમાં સ elementsર્ટ ક્રમમાં તત્વો શામેલ કરવા માટે ફંક્શનને ક Callલ કરો.
  5. મુખ્ય () માં સ sortર્ટ ફંક્શનને ક Callલ કરો.
  6. સortedર્ટ કરેલા સ્ટેકને છાપવા માટે એક કાર્ય બનાવો જે પેરામીટર તરીકે સ્ટેકને સ્વીકારે છે. જ્યારે સ્ટેક ખાલી ન હોય ત્યારે આડે વળવું, સ્ટેકનો ડેટા છાપો અને પછીના તત્વ પર જાઓ.

કોડ

રિકર્ઝનનો ઉપયોગ કરીને સ્ટેકને સ sortર્ટ કરવા માટે સી ++ પ્રોગ્રામ

#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

રિકર્ઝનનો ઉપયોગ કરીને સ્ટેકને સ sortર્ટ કરવા માટે જાવા પ્રોગ્રામ

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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન ^ 2) જ્યાં n એ સ્ટેકમાં તત્વોની સંખ્યા છે. કારણ કે જ્યારે આપણે સ્ટ elementકમાં તત્વને દબાણ કરીએ છીએ ત્યારે આપણે તે બધા તત્વોને સમાપ્ત કરી શકીએ છીએ જે હાલમાં સ્ટેકમાં હાજર છે અને પછી તેને શામેલ કરી શકીએ છીએ. આ ઇનપુટ ઘટતા ક્રમમાં હોય તો થાય છે.

અવકાશ જટિલતા

ઓ (એન) કારણ કે આપણે n તત્વો માટે સ્ટેક સ્પેસનો ઉપયોગ કર્યો છે. અમારા વર્તમાન તત્વને મૂકવા તત્વોને દૂર કરતી વખતે. અમારે દૂર કરેલા તત્વો સંગ્રહવા પડ્યાં, જે આપણને રેખીય અવકાશ જટિલતા આપે છે.