இரண்டு அடுக்குகளைப் பயன்படுத்தி குமிழி வரிசைப்படுத்துதல்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் கேப்ஜெமினி Delhivery 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-current குறியீட்டில் ஒரு [] வரிசையில் சேமிக்கவும்.
  10. தற்போதைய குறியீட்டு என்றால் வேறு மோட் 2 என்பது 0 க்கு சமம், இரண்டாவது அடுக்கு காலியாக இல்லாதபோது பயணிக்கவும்.
  11. ஒரு முழு எண் மாறியை உருவாக்கி, இரண்டாவது அடுக்கின் மேற்புறத்தில் உள்ள உறுப்பை பாப் செய்து அதில் சேமிக்கவும்.
  12. காசோலை முதல் அடுக்கு காலியாக உள்ளது, முதல் அடுக்கில் முழு எண் மாறியை தள்ள / செருகவும். முதல் அடுக்கின் மேலே உள்ள உறுப்பு முழு எண் மாறியை விட அதிகமாக இருக்கிறதா என்று சரிபார்க்கவும், ஒரு தற்காலிக மாறியை உருவாக்கவும், முதல் அடுக்கின் மேற்புறத்தில் உள்ள உறுப்பை பாப் செய்து தற்காலிக மாறியில் சேமிக்கவும். முதல் அடுக்கில் முழு எண் மாறியை அழுத்தவும். அதன் பிறகு, முதல் அடுக்கில் தற்காலிக மாறியை தள்ளுங்கள்.
  13. முதல் அடுக்கின் மேற்புறத்தில் உள்ள உறுப்பு முழு எண் மாறியை விட குறைவாகவோ அல்லது சமமாகவோ இருந்தால், அடுக்கில் உள்ள முழு மாறியை தள்ளுங்கள்.
  14. முதல் அடுக்கின் மேற்புறத்தை பாப் செய்து, குறியீட்டு n-1-current குறியீட்டில் ஒரு [] வரிசையில் சேமிக்கவும்.
  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 என்பது கொடுக்கப்பட்ட வரிசையில் உள்ள முழு எண்களின் எண்ணிக்கை []. இது குமிழி வரிசைக்குத் தேவையான வழக்கமான நேர சிக்கலாகும்.

விண்வெளி சிக்கலானது

ஓ (n) ஏனென்றால் n உறுப்புகளுக்கு இடத்தைப் பயன்படுத்தினோம். அடுக்குகளுக்கு இந்த சேமிப்பு தேவை.