차례
문제 정책
"두 스택을 사용하는 버블 정렬"문제는 정렬 크기 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
암호알고리즘
- 초기화 정렬 크기 n의 a [].
- 함수 만들기 종류 주어진 배열 a [] 사용 버블 정렬 두 패러다임 스택 배열과 그 크기를 매개 변수로 받아들이는 데이터 구조.
- 스택 데이터 구조 만들기 정수 유형. 주어진 배열을 가로 질러 스택에있는 배열의 모든 요소를 푸시합니다.
- 마찬가지로 정수 유형의 다른 스택 데이터 구조를 만듭니다.
- 그 후 0에서 n-1로 이동합니다. 현재 인덱스 mod 2가 0인지 확인하고 첫 번째 스택이 비어 있지 않은 동안 다시 트래버스합니다.
- 정수 변수를 만들고 첫 번째 스택의 맨 위에 요소를 팝하고 저장합니다.
- 두 번째 스택이 비어 있는지 확인하고 두 번째 스택에 정수 변수를 푸시 / 삽입합니다. 그렇지 않으면 두 번째 스택의 맨 위에있는 요소가 정수 변수보다 큰지 확인하고 임시 변수를 만들고 두 번째 스택의 맨 위에있는 요소를 팝하고 임시 변수에 저장합니다. 두 번째 스택에서 정수 변수를 푸시합니다. 그런 다음 두 번째 스택에서 임시 변수를 푸시합니다.
- 그렇지 않으면 두 번째 스택의 맨 위에있는 요소가 정수 변수보다 작거나 같으면 스택에서 정수 변수를 푸시합니다.
- 두 번째 스택의 상단을 팝하고 인덱스 n-1-current 인덱스의 배열 a []에 저장합니다.
- 현재 인덱스가 모드 2는 0과 같으며 두 번째 스택이 비어 있지 않은 동안 트래버스합니다.
- 정수 변수를 만들고 두 번째 스택의 맨 위에 요소를 팝하고 그 안에 저장합니다.
- 첫 번째 스택이 비어 있는지 확인하고 첫 번째 스택에 정수 변수를 푸시 / 삽입합니다. 그렇지 않으면 첫 번째 스택의 맨 위에있는 요소가 정수 변수보다 큰지 확인하고 임시 변수를 만들고 첫 번째 스택의 맨 위에있는 요소를 팝한 다음 임시 변수에 저장합니다. 첫 번째 스택에서 정수 변수를 푸시합니다. 그런 다음 첫 번째 스택에서 임시 변수를 푸시합니다.
- 그렇지 않으면 첫 번째 스택의 맨 위에있는 요소가 정수 변수보다 작거나 같으면 스택에서 정수 변수를 푸시합니다.
- 첫 번째 스택의 상단을 팝하고 인덱스 n-1- 현재 인덱스의 배열 a []에 저장합니다.
- 정렬 된 배열을 인쇄합니다.
암호
두 스택을 사용하여 버블 정렬을 구현하는 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 개의 요소에 공간을 사용했기 때문입니다. 이 스토리지는 스택에 필요합니다.
