ການຈັດຮຽງຟອງໂດຍໃຊ້ສອງ Stacks


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Capgemini ເດລີ MAQ
Array ຮຽງລໍາດັບ

ຖະແຫຼງການບັນຫາ

ບັນຫາ "ການຈັດລຽງຂອງຟອງໂດຍໃຊ້ສອງ Stacks" ລັດທີ່ທ່ານໄດ້ຮັບ array a [] ຂອງຂະ ໜາດ n. ສ້າງ ໜ້າ ທີ່ເພື່ອຈັດຮຽງແຖວ [] ໂດຍ ນຳ ໃຊ້ paradigm sort ຟອງທີ່ມີສອງໂຄງສ້າງຂໍ້ມູນ.

ການຈັດຮຽງຟອງໂດຍໃຊ້ສອງ Stacks

ຍົກຕົວຢ່າງ

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. ເລີ່ມຕົ້ນເປັນ array a [] ຂອງຂະ ໜາດ n.
  2. ສ້າງ ໜ້າ ທີ່ໃຫ້ ການຈັດລຽງ ອາເລທີ່ໃຫ້ເປັນ [] ໂດຍໃຊ້ ການຈັດລຽງຟອງ paradigm ກັບສອງ stack ໂຄງສ້າງຂໍ້ມູນທີ່ຍອມຮັບເອົາອາເລແລະມັນມີຂະ ໜາດ ທີ່ມັນເປັນພາລາມິເຕີ.
  3. ສ້າງໂຄງປະກອບຂໍ້ມູນຂອງ integer ປະເພດ. ຂ້າມຜ່ານອາເລທີ່ມອບໃຫ້ແລະຍູ້ສ່ວນປະກອບທັງ ໝົດ ຂອງອາເລໃນ ລຳ ລຽງ.
  4. ເຊັ່ນດຽວກັນ, ສ້າງໂຄງສ້າງຂໍ້ມູນ stack ອີກອັນ ໜຶ່ງ ຂອງປະເພດເລກເຕັມ.
  5. ຫລັງຈາກນັ້ນ, ຂ້າມຈາກ 0 ເຖິງ n-1. ກວດເບິ່ງວ່າດັດຊະນີດັດຊະນີປັດຈຸບັນ 2 ເທົ່າກັບ 0, ຂ້າມອີກໃນຂະນະທີ່ຂັ້ນຕອນ ທຳ ອິດບໍ່ຫວ່າງ.
  6. ສ້າງຕົວແປເຕັມແລະປ້ອນອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ທຳ ອິດແລະເກັບມັນໄວ້.
  7. ກວດເບິ່ງວ່າຊັ້ນທີສອງແມ່ນຫວ່າງບໍ່, ໃຫ້ກົດ / ໃສ່ຕົວແປຕົວແປໃນແຖວທີສອງ. ກວດເບິ່ງອີກວ່າອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ສອງແມ່ນໃຫຍ່ກວ່າຕົວເລກ integer, ສ້າງຕົວແປຊົ່ວຄາວ, ປ້ອນອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ສອງແລະເກັບມັນໄວ້ໃນຕົວປ່ຽນຊົ່ວຄາວ. ຍູ້ຕົວແປຕົວເລກໃນແຖວສອງ. ຫຼັງຈາກນັ້ນ, ຍູ້ຕົວແປຊົ່ວຄາວໃນຊັ້ນທີສອງ.
  8. ອື່ນຖ້າວ່າອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ທີສອງແມ່ນຫນ້ອຍກ່ວາຫຼືເທົ່າກັບຕົວແປ integer, ຍູ້ຕົວແປຕົວເລກໃນຊັ້ນ.
  9. Pop ເທິງສຸດຂອງ stack ທີສອງແລະເກັບມັນໄວ້ໃນ array a [] ທີ່ດັດຊະນີ n-1-index.
  10. ອື່ນຖ້າດັດສະນີປັດຈຸບັນ ຕ້ານ 2 ເທົ່າກັບ 0, ລ້າໆໃນຂະນະທີ່ຂັ້ນສອງບໍ່ແມ່ນວ່າງ.
  11. ສ້າງຕົວແປເຕັມແລະປ້ອນອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ທີສອງແລະເກັບໄວ້ໃນນັ້ນ.
  12. ເຊັກແມ່ນ stack ທຳ ອິດແມ່ນຫວ່າງ, ຍູ້ / ໃສ່ຕົວແປເລກເຕັມໃນ ລຳ ດັບ ທຳ ອິດ. ກວດເບິ່ງອີກວ່າອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ທຳ ອິດສູງກວ່າຕົວເລກ integer, ສ້າງຕົວແປຊົ່ວຄາວ, ປ້ອນອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ທຳ ອິດແລະເກັບມັນໄວ້ໃນຕົວປ່ຽນຊົ່ວຄາວ. ຍູ້ຕົວແປຕົວເລກໃນ ລຳ ດັບ ທຳ ອິດ. ຫລັງຈາກນັ້ນ, ຍູ້ຕົວແປຊົ່ວຄາວໃນຊັ້ນ ທຳ ອິດ.
  13. ອື່ນຖ້າວ່າອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ທຳ ອິດມີ ໜ້ອຍ ກວ່າຫລືເທົ່າກັບຕົວແປ integer, ຍູ້ຕົວແປຕົວເລກໃນ stack.
  14. Pop ເທິງສຸດຂອງ stack ຄັ້ງທໍາອິດແລະເກັບມັນໄວ້ໃນ array a [] ທີ່ດັດຊະນີ n-1-index.
  15. ພິມແຖວທີ່ຈັດຮຽງ.

ລະຫັດ

ໂປຣແກຣມ C ++ ເພື່ອຈັດຕັ້ງປະເພດຟອງໂດຍໃຊ້ສອງ Stacks

#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 Program ເພື່ອປະຕິບັດການຈັດຟອງໂດຍໃຊ້ສອງ Stacks

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]. ນີ້ແມ່ນຄວາມສັບສົນທີ່ໃຊ້ເວລາປົກກະຕິທີ່ຕ້ອງການໂດຍ Bubble Sort.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ເນື່ອງຈາກວ່າພວກເຮົາໃຊ້ພື້ນທີ່ ສຳ ລັບອົງປະກອບ n. ບ່ອນເກັບມ້ຽນນີ້ແມ່ນ ຈຳ ເປັນ ສຳ ລັບບັນຈຸ.