Table of Contents
Problem Statement
The problem “Bubble sort using two Stacks” states that you are given an array a[ ] of size n. Create a function to sort the given array a[ ] using a bubble sort paradigm with two stack data structures.
Example
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
Algorithm
- Initialize an array a[ ] of size n.
- Create the function to sort the given array a[ ] using bubble sort paradigm with two stack data structures which accept an array and it’s size as it’s parameter.
- Create a stack data structure of integer type. Traverse through the given array and push all the elements of the array in the stack.
- Similarly, create another stack data structure of integer type.
- After that, traverse from 0 to n-1. Check if the current index mod 2 is equal to 0, traverse again while the first stack is not empty.
- Create an integer variable and pop the element at the top of the first stack and store it.
- Check if the second stack is empty, push/insert the integer variable in the second stack. Else check if the element at the top of the second stack is greater than the integer variable, create a temporary variable, pop the element at the top of the second stack and store it in the temporary variable. Push the integer variable in the second stack. After that, push the temporary variable in the second stack.
- Else if the element at the top of the second stack is less than or equal to the integer variable, push the integer variable in the stack.
- Pop the top of the second stack and store it in the array a[ ] at index n-1-current index.
- Else if the current index mod 2 is equal to 0, traverse while the second stack is not empty.
- Create an integer variable and pop the element at the top of the second stack and store in it in.
- Check is the first stack is empty, push/insert the integer variable in the first stack. Else check if the element at the top of the first stack is greater than the integer variable, create a temporary variable, pop the element at the top of the first stack and store it in the temporary variable. Push the integer variable in the first stack. After that, push the temporary variable in the first stack.
- Else if the element at the top of the first stack is less than or equal to the integer variable, push the integer variable in the stack.
- Pop the top of the first stack and store it in the array a[ ] at index n-1-current index.
- Print the sorted array.
Code
C++ Program to implement bubble sort using two 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 to implement bubble sort using two 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
Complexity Analysis
Time Complexity
O(n^2) where n is the number of integers in given array a[ ]. This is the usual time complexity required by Bubble Sort.
Space Complexity
O(n) because we used space for n elements. This storage is required for stacks.