තොග දෙකක් භාවිතා කරමින් බුබුලු වර්ග කිරීම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් Capgemini දිල්ලි 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. වත්මන් දර්ශකය නම් , mod 2 0 ට සමාන වන අතර, දෙවන තොගය හිස් නොවන අතර ගමන් කරන්න.
  11. පූර්ණ සංඛ්‍යා විචල්‍යයක් සාදා දෙවන කොටුවේ ඉහළින් ඇති මූලද්‍රව්‍යය පොප් කර එහි ගබඩා කරන්න.
  12. පළමු තොගය හිස් බව පරීක්ෂා කරන්න, පළමු තොගයේ පූර්ණ සංඛ්‍යා විචල්‍යය තල්ලු කරන්න / ඇතුළු කරන්න. පළමු තොගයේ ඉහළින් ඇති මූලද්‍රව්‍යය පූර්ණ සංඛ්‍යා විචල්‍යයට වඩා වැඩි දැයි පරීක්ෂා කර, තාවකාලික විචල්‍යයක් සාදන්න, පළමු කොටුවේ ඉහළින් ඇති මූලද්‍රව්‍යය පොප් කර තාවකාලික විචල්‍යයේ ගබඩා කරන්න. පළමු අට්ටාලයේ පූර්ණ සංඛ්‍යා විචල්‍යය තල්ලු කරන්න. ඊට පසු, තාවකාලික විචල්‍යය පළමු තොගයේ තල්ලු කරන්න.
  13. පළමු තොගයේ ඉහළින් ඇති මූලද්‍රව්‍යය පූර්ණ සංඛ්‍යා විචල්‍යයට වඩා අඩු හෝ සමාන නම්, පූර්ණ සංඛ්‍යා විචල්‍යය තොගයේ තල්ලු කරන්න.
  14. පළමු අට්ටාලයේ ඉහළට පොප් කර එය අරාවෙහි [] දර්ශකයේ n-1-current දර්ශකයේ ගබඩා කරන්න.
  15. වර්ග කළ අරාව මුද්‍රණය කරන්න.

කේතය

C ++ වැඩසටහන කොටස් දෙකක් භාවිතා කරමින් බුබුලු වර්ග කිරීම ක්‍රියාත්මක කිරීම

#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 යනු දී ඇති අරාවෙහි පූර්ණ සංඛ්‍යා ගණන a []. බබල් වර්ග කිරීම සඳහා අවශ්‍ය වන සුපුරුදු කාල සංකීර්ණතාව මෙයයි.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) අපි n මූලද්‍රව්‍ය සඳහා ඉඩ භාවිතා කළ නිසා. මෙම ගබඩාව තොග සඳහා අවශ්‍ය වේ.