രണ്ട് സ്റ്റാക്കുകൾ ഉപയോഗിച്ച് ബബിൾ അടുക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ കാപ്ജെമിനിയും ദില്ലി MAQ
അറേ ക്രമപ്പെടുത്തൽ

പ്രശ്നം പ്രസ്താവന

“രണ്ട് സ്റ്റാക്കുകൾ ഉപയോഗിച്ചുള്ള ബബിൾ സോർട്ട്” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ശ്രേണി a [] വലുപ്പം n. രണ്ട് സ്റ്റാക്ക് ഡാറ്റ ഘടനകളുള്ള ബബിൾ സോർട്ട് പാരഡൈം ഉപയോഗിച്ച് തന്നിരിക്കുന്ന അറേയെ ഒരു [] അടുക്കുന്നതിന് ഒരു ഫംഗ്ഷൻ സൃഷ്ടിക്കുക.

രണ്ട് സ്റ്റാക്കുകൾ ഉപയോഗിച്ച് ബബിൾ അടുക്കുക

ഉദാഹരണം

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. എന്നതിലേക്ക് പ്രവർത്തനം സൃഷ്ടിക്കുക അടുക്കുക നൽകിയ അറേ ഒരു [] ഉപയോഗിക്കുന്നു ബബിൾ സോർട്ട് രണ്ട് ഉള്ള മാതൃക സ്റ്റാക്ക് ഒരു ശ്രേണി സ്വീകരിക്കുന്ന ഡാറ്റ ഘടനകൾ, അതിന്റെ പാരാമീറ്റർ പോലെ അതിന്റെ വലുപ്പം.
  3. ന്റെ ഒരു സ്റ്റാക്ക് ഡാറ്റ ഘടന സൃഷ്ടിക്കുക പൂർണ്ണസംഖ്യ ടൈപ്പ് ചെയ്യുക. തന്നിരിക്കുന്ന അറേയിലൂടെ സഞ്ചരിച്ച് അറേയുടെ എല്ലാ ഘടകങ്ങളും സ്റ്റാക്കിൽ തള്ളുക.
  4. അതുപോലെ, പൂർണ്ണസംഖ്യയുടെ മറ്റൊരു സ്റ്റാക്ക് ഡാറ്റ ഘടന സൃഷ്ടിക്കുക.
  5. അതിനുശേഷം, 0 മുതൽ n-1 വരെ സഞ്ചരിക്കുക. നിലവിലെ സൂചിക മോഡ് 2 0 ന് തുല്യമാണോയെന്ന് പരിശോധിക്കുക, ആദ്യത്തെ സ്റ്റാക്ക് ശൂന്യമല്ലാത്തപ്പോൾ വീണ്ടും സഞ്ചരിക്കുക.
  6. ഒരു പൂർണ്ണസംഖ്യ വേരിയബിൾ സൃഷ്‌ടിച്ച് ആദ്യ സ്റ്റാക്കിന്റെ മുകളിൽ ഘടകം പോപ്പ് ചെയ്ത് സംഭരിക്കുക.
  7. രണ്ടാമത്തെ സ്റ്റാക്ക് ശൂന്യമാണോയെന്ന് പരിശോധിക്കുക, രണ്ടാമത്തെ സ്റ്റാക്കിൽ ഇൻറിജർ വേരിയബിൾ പുഷ് / തിരുകുക. രണ്ടാമത്തെ സ്റ്റാക്കിന്റെ മുകളിലുള്ള മൂലകം പൂർണ്ണസംഖ്യ വേരിയബിളിനേക്കാൾ വലുതാണോയെന്ന് പരിശോധിക്കുക, ഒരു താൽക്കാലിക വേരിയബിൾ സൃഷ്ടിക്കുക, രണ്ടാമത്തെ സ്റ്റാക്കിന്റെ മുകളിൽ ഘടകം പോപ്പ് ചെയ്ത് താൽക്കാലിക വേരിയബിളിൽ സംഭരിക്കുക. രണ്ടാമത്തെ സ്റ്റാക്കിൽ ഇൻറിജർ വേരിയബിൾ പുഷ് ചെയ്യുക. അതിനുശേഷം, രണ്ടാമത്തെ സ്റ്റാക്കിൽ താൽക്കാലിക വേരിയബിൾ പുഷ് ചെയ്യുക.
  8. രണ്ടാമത്തെ സ്റ്റാക്കിന്റെ മുകളിലുള്ള മൂലകം പൂർണ്ണസംഖ്യ വേരിയബിളിനേക്കാൾ കുറവോ തുല്യമോ ആണെങ്കിൽ, സ്റ്റാക്കിലെ ഇൻറിജർ വേരിയബിളിനെ പുഷ് ചെയ്യുക.
  9. രണ്ടാമത്തെ സ്റ്റാക്കിന്റെ മുകളിൽ പോപ്പ് ചെയ്ത് ഇൻഡെക്സ് n-1- നിലവിലെ സൂചികയിൽ a [] അറേയിൽ സംഭരിക്കുക.
  10. നിലവിലെ സൂചികയാണെങ്കിൽ മറ്റൊന്ന് എതിരായി 2 എന്നത് 0 ന് തുല്യമാണ്, രണ്ടാമത്തെ സ്റ്റാക്ക് ശൂന്യമല്ല.
  11. ഒരു പൂർണ്ണസംഖ്യ വേരിയബിൾ സൃഷ്‌ടിച്ച് രണ്ടാമത്തെ സ്റ്റാക്കിന് മുകളിൽ ഘടകം പോപ്പ് ചെയ്‌ത് അതിൽ സംഭരിക്കുക.
  12. ആദ്യ സ്റ്റാക്ക് ശൂന്യമാണോയെന്ന് പരിശോധിക്കുക, ആദ്യ സ്റ്റാക്കിൽ ഇൻറിജർ വേരിയബിൾ പുഷ് / തിരുകുക. ആദ്യ സ്റ്റാക്കിന്റെ മുകളിലുള്ള ഘടകം പൂർണ്ണസംഖ്യ വേരിയബിളിനേക്കാൾ വലുതാണോയെന്ന് പരിശോധിക്കുക, ഒരു താൽക്കാലിക വേരിയബിൾ സൃഷ്ടിക്കുക, ആദ്യ സ്റ്റാക്കിന്റെ മുകളിൽ ഘടകം പോപ്പ് ചെയ്ത് താൽക്കാലിക വേരിയബിളിൽ സംഭരിക്കുക. ആദ്യ സ്റ്റാക്കിൽ ഇൻറിജർ വേരിയബിൾ പുഷ് ചെയ്യുക. അതിനുശേഷം, ആദ്യത്തെ സ്റ്റാക്കിൽ താൽക്കാലിക വേരിയബിൾ പുഷ് ചെയ്യുക.
  13. അല്ലാത്തപക്ഷം ആദ്യത്തെ സ്റ്റാക്കിന്റെ മുകളിലുള്ള മൂലകം പൂർണ്ണസംഖ്യ വേരിയബിളിനേക്കാൾ കുറവോ തുല്യമോ ആണെങ്കിൽ, സ്റ്റാക്കിലെ ഇൻറിജർ വേരിയബിളിനെ പുഷ് ചെയ്യുക.
  14. ആദ്യ സ്റ്റാക്കിന്റെ മുകളിൽ പോപ്പ് ചെയ്ത് സൂചിക n-1- നിലവിലെ സൂചികയിൽ ഒരു [] അറേയിൽ സംഭരിക്കുക.
  15. അടുക്കിയ അറേ പ്രിന്റുചെയ്യുക.

കോഡ്

രണ്ട് സ്റ്റാക്കുകൾ ഉപയോഗിച്ച് ബബിൾ സോർട്ട് നടപ്പിലാക്കുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

#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

രണ്ട് സ്റ്റാക്കുകൾ ഉപയോഗിച്ച് ബബിൾ സോർട്ട് നടപ്പിലാക്കുന്നതിനുള്ള ജാവ പ്രോഗ്രാം

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n ^ 2) ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന അറേയിലെ പൂർണ്ണസംഖ്യകളുടെ എണ്ണം []. ബബിൾ അടുക്കുന്നതിന് ആവശ്യമായ സാധാരണ സമയ സങ്കീർണ്ണതയാണിത്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) കാരണം n ഘടകങ്ങൾക്ക് ഞങ്ങൾ ഇടം ഉപയോഗിച്ചു. ഈ സംഭരണം സ്റ്റാക്കുകൾക്ക് ആവശ്യമാണ്.