બે સ્ટેક્સનો ઉપયોગ કરીને બબલ સ sortર્ટ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન કેપજેમિની દિલ્હીવારી MAQ
અરે સોર્ટિંગ

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

સમસ્યા "બે સ્ટેક્સનો ઉપયોગ કરીને બબલ સ sortર્ટ" કહે છે કે તમને એક એરે a [] કદ n. આપેલા એરેને સ sortર્ટ કરવા માટે એક ફંક્શન બનાવો []] બે સ્ટેક ડેટા સ્ટ્રક્ચર્સ સાથે બબલ સ sortર્ટ નમૂનાનો ઉપયોગ કરીને.

બે સ્ટેક્સનો ઉપયોગ કરીને બબલ સ sortર્ટ

ઉદાહરણ

a[ ] = {15, 12, 44, 2, 5, 10}
2 5 10 12 15 44
a[ ] = {5, 6, 4, 2, 3, 1}
1 2 3 4 5 6

અલ્ગોરિધમ

  1. પ્રારંભ એક એરે a [] કદ n.
  2. આ કાર્ય બનાવો સૉર્ટ કરો આપેલ એરે a [] નો ઉપયોગ કરીને બબલ સૉર્ટ બે સાથે દાખલો સ્ટેક ડેટા સ્ટ્રક્ચર્સ જે કોઈ એરે સ્વીકારે છે અને તેનું પરિમાણ હોવાથી તેનું કદ.
  3. નું સ્ટેક ડેટા સ્ટ્રક્ચર બનાવો પૂર્ણાંક પ્રકાર. આપેલ એરેથી પસાર થવું અને એરેના બધા ઘટકોને સ્ટackકમાં દબાણ કરો.
  4. એ જ રીતે, પૂર્ણાંક પ્રકારનું બીજું સ્ટેક ડેટા સ્ટ્રક્ચર બનાવો.
  5. તે પછી, 0 થી n-1 સુધીનો માર્ગ પસાર કરો. વર્તમાન ઇન્ડેક્સ મોડ 2 0 ની બરાબર છે કે નહીં તે તપાસો, પ્રથમ સ્ટેક ખાલી ન હોય ત્યારે ફરીથી ટ્રverseવર્સ કરો.
  6. પૂર્ણાંક ચલ બનાવો અને પ્રથમ સ્ટેકની ટોચ પર તત્વ પ popપ કરો અને તેને સંગ્રહિત કરો.
  7. બીજું સ્ટેક ખાલી છે કે નહીં તે તપાસો, બીજા સ્ટેકમાં પૂર્ણાંક ચલ દબાણ / દાખલ કરો. બાકી તપાસો કે બીજા સ્ટેકની ટોચ પરનું તત્વ પૂર્ણાંક ચલ કરતા વધારે છે, એક અસ્થાયી ચલ બનાવો, બીજા સ્ટેકની ટોચ પર તત્વને પ popપ કરો અને તેને અસ્થાયી ચલમાં સ્ટોર કરો. બીજા સ્ટેકમાં પૂર્ણાંક ચલ દબાણ કરો. તે પછી, બીજા સ્ટેકમાં અસ્થાયી ચલને દબાણ કરો.
  8. બાકી જો બીજા સ્ટેકની ટોચ પરનું તત્વ પૂર્ણાંક ચલ કરતા ઓછું અથવા તેના બરાબર હોય, તો સ્ટેકમાં પૂર્ણાંક ચલને દબાણ કરો.
  9. બીજા સ્ટેકની ટોચ પર પ Popપ કરો અને તેને એરે [a] માં અનુક્રમણિકા એન -1-વર્તમાન અનુક્રમણિકામાં સ્ટોર કરો.
  10. બાકી જો વર્તમાન અનુક્રમણિકા ફેરફારની 2, 0 ની બરાબર છે, જ્યારે બીજા સ્ટેક ખાલી નથી.
  11. પૂર્ણાંક ચલ બનાવો અને બીજા સ્ટેકની ટોચ પર તત્વ પ popપ કરો અને તેમાં સ્ટોર કરો.
  12. પ્રથમ સ્ટેક ખાલી છે તે તપાસો, પ્રથમ સ્ટેકમાં પૂર્ણાંક ચલ દબાણ / દાખલ કરો. બાકી તપાસો કે શું પ્રથમ સ્ટેકની ટોચ પરનું તત્વ પૂર્ણાંક ચલ કરતા વધારે છે, એક અસ્થાયી ચલ બનાવો, પ્રથમ સ્ટેકની ટોચ પર તત્વને પ popપ કરો અને તેને અસ્થાયી ચલમાં સ્ટોર કરો. પ્રથમ સ્ટેકમાં પૂર્ણાંક ચલ દબાણ કરો. તે પછી, પ્રથમ સ્ટેકમાં અસ્થાયી ચલને દબાણ કરો.
  13. બાકી જો પ્રથમ સ્ટેકની ટોચ પરનું તત્વ પૂર્ણાંક ચલ કરતા ઓછું અથવા તેના બરાબર હોય, તો સ્ટેકમાં પૂર્ણાંક ચલને દબાણ કરો.
  14. પ્રથમ સ્ટેકની ટોચ પર પ Popપ કરો અને એરે [a] માં અનુક્રમણિકા એન -1-વર્તમાન અનુક્રમણિકામાં સ્ટોર કરો.
  15. સ theર્ટ કરેલ એરે છાપો.

કોડ

સી ++ પ્રોગ્રામ બે સ્ટેક્સનો ઉપયોગ કરીને બબલ સ sortર્ટ લાગુ કરવા

#include <bits/stdc++.h>
using namespace std;

void bubbleSortStack(int a[], int n){ 
    stack<int> s1;
      
    for(int i = 0; i < n; i++){ 
        s1.push(a[i]);
    }
      
    stack<int> s2;
      
    for(int i = 0; i < n; i++){ 
        
        if(i % 2 == 0){ 
            while (!s1.empty()){ 
                int t = s1.top();
                s1.pop(); 
                  
                if(s2.empty()){ 
                    s2.push(t);  
                }
                
                else{ 
                    
                    if(s2.top() > t){ 
                        int temp = s2.top(); 
                        s2.pop(); 
                        s2.push(t); 
                        s2.push(temp); 
                    } 
                    
                    else{ 
                        s2.push(t); 
                    } 
                } 
            } 
            a[n-1-i] = s2.top();
            s2.pop(); 
        }     
        
        else{
            
            while(!s2.empty()){ 
                int t = s2.top();
                s2.pop();
                  
                if (s1.empty()){ 
                    s1.push(t); 
                }
                  
                else{ 
                    
                    if (s1.top() > t){ 
                        int temp = s1.top();
                        s1.pop(); 
                          
                        s1.push(t); 
                        s1.push(temp); 
                    } 
                    
                    else{
                        s1.push(t); 
                    }
                } 
            } 
              
            a[n-1-i] = s1.top();
            s1.pop(); 
        } 
    }
    
    for(int i = 0; i < n; i++){
        cout<< a[i] << " "; 
    }
} 
  
int main() {
  int a[] = {15, 12, 44, 2, 5, 10};
  int n = sizeof(a)/sizeof(a[0]);
    
  bubbleSortStack(a, n); 
    
  return 0;
}
2 5 10 12 15 44

જાવા પ્રોગ્રામ બે સ્ટેક્સનો ઉપયોગ કરીને બબલ સ sortર્ટ લાગુ કરવા

import java.util.Arrays; 
import java.util.Stack; 
  
class Sort{ 
    
    static void bubbleSortStack(int a[], int n){ 
        Stack<Integer> s1 = new Stack<>(); 
          
        for(int num : a){ 
            s1.push(num);
        }
          
        Stack<Integer> s2 = new Stack<>(); 
          
        for(int i = 0; i < n; i++){ 
            
            if(i % 2 == 0){ 
                while (!s1.isEmpty()){ 
                    int t = s1.pop(); 
                      
                    if(s2.isEmpty()){ 
                        s2.push(t);  
                    }
                    
                    else{ 
                        
                        if(s2.peek() > t){ 
                            int temp = s2.pop(); 
                            s2.push(t); 
                            s2.push(temp); 
                        } 
                        
                        else{ 
                            s2.push(t); 
                        } 
                    } 
                } 
                a[n-1-i] = s2.pop(); 
            }     
            
            else{
                
                while(!s2.isEmpty()){ 
                    int t = s2.pop(); 
                      
                    if (s1.isEmpty()){ 
                        s1.push(t); 
                    }
                      
                    else{ 
                        
                        if (s1.peek() > t){ 
                            int temp = s1.pop(); 
                              
                            s1.push(t); 
                            s1.push(temp); 
                        } 
                        
                        else{
                            s1.push(t); 
                        }
                    } 
                } 
                  
                a[n-1-i] = s1.pop(); 
            } 
        }
        
        for(int i = 0; i < n; i++){
            System.out.print(a[i]+" "); 
        }
    } 
      
    public static void main(String[] args){
        
        int a[] = {15, 12, 44, 2, 5, 10};
        
        bubbleSortStack(a, a.length); 
    } 
}
2 5 10 12 15 44

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

સમય જટિલતા

ઓ (n ^ 2) જ્યાં n આપેલ એરેમાં પૂર્ણાંકોની સંખ્યા છે a []. બબલ સortર્ટ દ્વારા આવશ્યક આ સમયની જટિલતા છે.

અવકાશ જટિલતા

ઓ (એન) કારણ કે આપણે n તત્વો માટે જગ્યા વાપરી છે. આ સંગ્રહને સ્ટેક્સ માટે જરૂરી છે.