스택을 사용하여 배열 정렬

난이도 중급
자주 묻는 질문 아마존 골드만 삭스 IBM 쿨리 자 Yahoo
정렬 스택조회수 42

문제 설명

"스택을 사용하여 배열 정렬"문제는 데이터 구조가 제공됨을 나타냅니다. 정렬 크기 n의 a []. 종류 주어진 배열의 요소 스택 데이터 구조.

스택을 사용하여 배열 정렬

2 30 -5 43 100
-5 2 30 43 100

설명 : 요소는 오름차순으로 정렬됩니다.

2 3 1 8 6
1 2 3 6 8

스택을 사용하여 배열을 정렬하는 방법

주어진 입력 배열 a []의 모든 요소를 ​​저장할 스택 데이터 구조를 만듭니다. 그런 다음 원본을 정렬하기 위해 다른 임시 스택을 만듭니다. 원래 스택을 반복하고 각 요소에 대해 상단을 팝하고 임시 변수에 저장합니다. 마찬가지로 임시 스택의 맨 위에있는 요소가 원래 스택의 팝된 맨 위에있는 요소보다 작은 동안 임시 스택을 반복합니다. 임시 스택의 맨 위 요소를 원래 스택에 삽입하고 임시 스택에서 제거합니다. 임시 스택에서 원래 스택의 튀어 나온 상단을 밉니다. 결국 임시 스택에는 정렬 된 순서로 요소가 포함됩니다. 이 문제는 정렬보다 약간의 수정입니다. 임시 스택을 사용하여 스택.

암호알고리즘

  1. n 크기의 배열 a []를 초기화합니다.
  2. 스택 데이터 구조를 만듭니다. 배열 a []를 가로 질러 스택에있는 배열 a []의 모든 요소를 ​​밀어 넣습니다.
  3. 마찬가지로 다른 임시 스택을 만듭니다.
  4. 원래 스택의 크기가 0이 아닌 동안 트래버스합니다. 변수 tmp를 만들고 원래 스택의 맨 위에 요소를 저장하고 원래 스택에서 팝합니다.
  5. 임시 스택이 비어 있지 않은 동안 다시 트래버스하고 변수 tmp보다 적을 때까지 임시 스택의 맨 위에있는 요소를 팝합니다. 임시 스택에서 튀어 나오는 동안 원래 스택에서 임시 스택의 맨 위 요소를 푸시합니다.
  6. 임시 스택에 변수 tmp를 푸시합니다.
  7. 0에서 n-1로 이동하고 임시 스택의 최상위 요소를 현재 인덱스의 배열 a []에 저장하고 임시 스택에서 요소를 팝 / 삭제합니다.
  8. 마지막으로 0에서 n-1로 이동하고 a [] 배열을 인쇄합니다.

암호

스택을 사용한 배열 정렬을위한 C ++ 프로그램

#include <iostream>
#include <stack> 
using namespace std; 
  
stack<int> sortStack(stack<int> input){ 
    stack<int> tmpStack; 
    while(!input.empty()){ 
        int tmp = input.top(); 
        input.pop(); 
  
        while (!tmpStack.empty() && tmpStack.top() < tmp){ 
            input.push(tmpStack.top()); 
            tmpStack.pop(); 
        } 
  
        tmpStack.push(tmp); 
    } 
  
    return tmpStack; 
} 
  
void sortUsingStack(int arr[], int n){ 
     
    stack<int> input; 
    for(int i=0; i<n; i++){ 
       input.push(arr[i]); 
    }
  
    stack<int> tmpStack = sortStack(input); 
  
    for(int i=0; i<n; i++){ 
        arr[i] = tmpStack.top(); 
        tmpStack.pop(); 
    } 
} 
  
int main(){ 
    int a[] = {2, 30, -5, 43, 100}; 
    int n = sizeof(a)/sizeof(a[0]); 
  
    sortUsingStack(a, n); 
  
    for(int i=0; i<n; i++) 
       cout << a[i] << " "; 
  
    return 0; 
}
-5 2 30 43 100

스택을 사용한 배열 정렬을위한 Java 프로그램

import java.io.*; 
import java.util.*; 
  
class SortArrayWithStack{ 
    
    static Stack<Integer> sortStack(Stack<Integer> input){ 
        Stack<Integer> tmpStack = new Stack<Integer>(); 
      
        while(!input.empty()){ 
            int tmp = input.peek(); 
            input.pop(); 
      
            while(!tmpStack.empty() && tmpStack.peek() < tmp){ 
                input.push(tmpStack.peek()); 
                tmpStack.pop(); 
            } 
      
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    static void sortUsingStack(int []arr, int n){ 
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        for(int i = 0; i < n; i++){ 
            input.push(arr[i]); 
        }
      
        Stack<Integer> tmpStack = sortStack(input); 
      
        for(int i = 0; i < n; i++){ 
            arr[i] = tmpStack.peek(); 
            tmpStack.pop(); 
        } 
    } 
      
    public static void main(String args[]){
        
        int []a = {2, 30, -5, 43, 100};
        int n = a.length; 
      
        sortUsingStack(a, n); 
      
        for(int i = 0; i < n; i++){ 
            System.out.print(a[i] + " "); 
        }    
    } 
}
-5 2 30 43 100

복잡성 분석

시간 복잡성

O (n ^ 2) 여기서 n은 스택의 요소 수입니다. 임시 스택의 맨 위가 푸시 할 요소보다 작은 경우 임시 스택에서 원래 스택으로 요소를 다시 푸시하기 때문입니다. 더 나은 이해를 위해 내림차순 순서를 고려하고 알고리즘을 실행 해보십시오.

공간 복잡성

O (N) n 개의 요소에 임시 스택 공간을 사용했기 때문입니다. 원래 스택에서 사용한 공간은 알고리즘에 포함되지 않습니다.

Translate »