두 개의 스택을 사용한 버블 정렬

난이도 쉽게
자주 묻는 질문 아마존 캡 제미니 배달 MAQ
배열 정렬조회수 81

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

"두 스택을 사용하는 버블 정렬"문제는 정렬 크기 n의 a []. 두 개의 스택 데이터 구조가있는 버블 정렬 패러다임을 사용하여 주어진 배열 a []를 정렬하는 함수를 만듭니다.

두 개의 스택을 사용한 버블 정렬

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. 초기화 정렬 크기 n의 a [].
  2. 함수 만들기 종류 주어진 배열 a [] 사용 버블 정렬 두 패러다임 스택 배열과 그 크기를 매개 변수로 받아들이는 데이터 구조.
  3. 스택 데이터 구조 만들기 정수 유형. 주어진 배열을 가로 질러 스택에있는 배열의 모든 요소를 ​​푸시합니다.
  4. 마찬가지로 정수 유형의 다른 스택 데이터 구조를 만듭니다.
  5. 그 후 0에서 n-1로 이동합니다. 현재 인덱스 mod 2가 0인지 확인하고 첫 번째 스택이 비어 있지 않은 동안 다시 트래버스합니다.
  6. 정수 변수를 만들고 첫 번째 스택의 맨 위에 요소를 팝하고 저장합니다.
  7. 두 번째 스택이 비어 있는지 확인하고 두 번째 스택에 정수 변수를 푸시 / 삽입합니다. 그렇지 않으면 두 번째 스택의 맨 위에있는 요소가 정수 변수보다 큰지 확인하고 임시 변수를 만들고 두 번째 스택의 맨 위에있는 요소를 팝하고 임시 변수에 저장합니다. 두 번째 스택에서 정수 변수를 푸시합니다. 그런 다음 두 번째 스택에서 임시 변수를 푸시합니다.
  8. 그렇지 않으면 두 번째 스택의 맨 위에있는 요소가 정수 변수보다 작거나 같으면 스택에서 정수 변수를 푸시합니다.
  9. 두 번째 스택의 상단을 팝하고 인덱스 n-1-current 인덱스의 배열 a []에 저장합니다.
  10. 현재 인덱스가 모드 2는 0과 같으며 두 번째 스택이 비어 있지 않은 동안 트래버스합니다.
  11. 정수 변수를 만들고 두 번째 스택의 맨 위에 요소를 팝하고 그 안에 저장합니다.
  12. 첫 번째 스택이 비어 있는지 확인하고 첫 번째 스택에 정수 변수를 푸시 / 삽입합니다. 그렇지 않으면 첫 번째 스택의 맨 위에있는 요소가 정수 변수보다 큰지 확인하고 임시 변수를 만들고 첫 번째 스택의 맨 위에있는 요소를 팝한 다음 임시 변수에 저장합니다. 첫 번째 스택에서 정수 변수를 푸시합니다. 그런 다음 첫 번째 스택에서 임시 변수를 푸시합니다.
  13. 그렇지 않으면 첫 번째 스택의 맨 위에있는 요소가 정수 변수보다 작거나 같으면 스택에서 정수 변수를 푸시합니다.
  14. 첫 번째 스택의 상단을 팝하고 인덱스 n-1- 현재 인덱스의 배열 a []에 저장합니다.
  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

복잡성 분석

시간 복잡성

O (n ^ 2) 여기서 n은 주어진 배열 a []에있는 정수의 수입니다. 이것은 버블 정렬에 필요한 일반적인 시간 복잡도입니다.

공간 복잡성

O (N) n 개의 요소에 공간을 사용했기 때문입니다. 이 스토리지는 스택에 필요합니다.

균열 시스템 설계 인터뷰
Translate »