בלאָז סאָרט ניצן צוויי סטאַקס


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַמאַזאָן קאַפּגעמיני דעליווערי מאַק
מענגע סאָרטינג

פּראָבלעם סטאַטעמענט

די פּראָבלעם "בלאָז סאָרט ניצן צוויי סטאַקס" שטאַטן אַז איר האָט געגעבן אַן מענגע אַ [] פון גרייס ען. שאַפֿן אַ פונקציע צו סאָרט די געגעבן מענגע אַ [] ניצן אַ בלאָז סאָרט פּאַראַדיגם מיט צוויי אָנלייגן דאַטן סטראַקטשערז.

בלאָז סאָרט ניצן צוויי סטאַקס

בייַשפּיל

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. יניטיאַליזירן אַן מענגע אַ [] פון גרייס ען.
  2. שאַפֿן די פֿונקציע צו סאָרט די געגעבן מענגע אַ [] ניצן בלאָז סאָרט פּאַראַדיגם מיט צוויי stack דאַטן סטראַקטשערז וואָס אָננעמען אַ מענגע און די גרייס איז די פּאַראַמעטער.
  3. שאַפֿן אַ סטאַק דאַטן סטרוקטור פון ינטעגער טיפּ. פאָרן דורך די געגעבן מענגע און שטופּן אַלע די יסודות פון די מענגע אין דעם אָנלייגן.
  4. סימילאַרלי, שאַפֿן אן אנדער אָנלייגן דאַטן סטרוקטור פון ינטאַדזשער טיפּ.
  5. דערנאָך, אַריבער פון 0 צו N-1. קאָנטראָלירן אויב די קראַנט אינדעקס מאָד 2 איז גלייַך צו 0, דורך ווידער ווען דער ערשטער אָנלייגן איז נישט ליידיק.
  6. שאַפֿן אַ ינטעגער בייַטעוודיק און קנאַל די עלעמענט אין די שפּיץ פון די ערשטער אָנלייגן און סטאָר עס.
  7. קוק אויב די רגע אָנלייגן איז ליידיק, שטופּן / טאָן די ינטעגער בייַטעוודיק אין די רגע אָנלייגן. אַנדערש טשעק אויב די עלעמענט אין די שפּיץ פון די רגע סטאַק איז גרעסער ווי די ינטעגער בייַטעוודיק, מאַכן אַ צייַטווייַליק בייַטעוודיק, קנאַל די עלעמענט אין די שפּיץ פון די רגע סטאַק און קראָם עס אין די צייַטווייַליק בייַטעוודיק. פּוש די ינטאַדזשער בייַטעוודיק אין די רגע אָנלייגן. נאָך דעם, שטופּן די צייַטווייַליק בייַטעוודיק אין די רגע אָנלייגן.
  8. אַנדערש אויב דער עלעמענט אין דער שפּיץ פון די רגע אָנלייגן איז ווייניקער ווי אָדער גלייַך צו די ינטעגער בייַטעוודיק, שטופּן די ינטעגער בייַטעוודיק אין די אָנלייגן.
  9. קנאַל די שפּיץ פון די רגע סטאַק און קראָם עס אין די מענגע אַ [] אין אינדעקס N-1 קראַנט אינדעקס.
  10. אַנדערש אויב די קראַנט אינדעקס מאָד 2 איז גלייַך צו 0, דורך די רגע סטאַק איז נישט ליידיק.
  11. שאַפֿן אַ ינטעגער בייַטעוודיק און קנאַל די עלעמענט אין די שפּיץ פון די רגע סטאַק און סטאָרד עס אין.
  12. טשעק איז דער ערשטער אָנלייגן איז ליידיק, שטופּן / טאָן די ינטאַדזשער בייַטעוודיק אין דער ערשטער אָנלייגן. אַנדערש טשעק אויב די עלעמענט אין דער שפּיץ פון דער ערשטער אָנלייגן איז גרעסער ווי די ינטעגער בייַטעוודיק, מאַכן אַ צייַטווייַליק בייַטעוודיק, קנאַל די עלעמענט אין דער שפּיץ פון דער ערשטער אָנלייגן און קראָם עס אין די צייַטווייַליק בייַטעוודיק. שטופּן די ינטאַדזשער בייַטעוודיק אין דער ערשטער אָנלייגן. נאָך דעם, שטופּן די צייַטווייַליק בייַטעוודיק אין דער ערשטער אָנלייגן.
  13. אַנדערש אויב דער עלעמענט אין דער שפּיץ פון דער ערשטער אָנלייגן איז ווייניקער ווי אָדער גלייַך צו די ינטאַדזשער בייַטעוודיק, שטופּן די ינטעגער בייַטעוודיק אין די אָנלייגן.
  14. פּאָפּ די שפּיץ פון די ערשטער אָנלייגן און סטאָר עס אין די מענגע אַ [] אין אינדעקס N-1 קראַנט אינדעקס.
  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

Java פּראָגראַם צו ינסטרומענט די סאָרט בלאָז ניצן צוויי סטאַקס

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 איז די נומער פון גאַנץ נומערן אין געגעבן מענגע אַ []. דאָס איז די געוויינטלעך צייט קאַמפּלעקסיטי פארלאנגט דורך Bubble Sort.

ספעיס קאַמפּלעקסיטי

אָ (N) ווייַל מיר געוויינט פּלאַץ פֿאַר n עלעמענטן. די סטאָרידזש איז פארלאנגט פֿאַר סטאַקס.