In this article, we have explored the algorithm to perform Bubble Sorting Algorithm using Two Stacks and sort a given array.

Table of contents:

1. Problem statement
2. Algorithm: Bubble Sort using Two Stacks
3. Step by Step example
4. Implementation
5. Time & Space Complexity

Problem statement

A sorting algorithm is used to rearrange items in a particular order. In this article, we explore the process behind sorting an array (say) 'ar' in ascending order using two stacks 's1' and 's2'.

A stack has only three permitted operations:

• Push: Insert new elements at the top of stack
• Pop: Delete element at the top of stack
• Peep: Get the element at the top of stack

Stack is a FIFO (First in First out) data structure. We need to use 2 stacks to sort an array. We can use Bubble sort and implement in using 2 stacks.

Algorithm: Bubble Sort using Two Stacks

Bubble Sort is the simplest sorting algorithm that sorts by comparing adjacent elements. A stack is a data structure in which insertion & deletion of elements occur from one end only. As a result, the element inserted into the stack last is the topmost element and vice-versa (LIFO: Last In, First Out).

The steps followed by this algorithm are as follows:

1. Push all elements of the array into s1.
2. While s1 is not empty, the steps below take place:
   2.a. A temporary variable 'temp' is initialized to make it easier to swap elements. temp = the element popped (i.e the topmost element) from s1
   2.b. If s2 is empty or the topmost element of s2 >= temp, then temp is pushed onto s2. Otherwise, the elements from s2 are popped and pushed onto s1 till the above condition is true, after which temp is pushed in s2.
3. Once s1 is empty, the elements are removed one-by-one from s2, therefore returning the elements in a sorted order.

• To sort the elements in a descending order, the condition in Step 2.b is modified as topmost element <= temp*

Step by Step example

Let's consider a simple example where an array 'ar' containing the numbers 10, 75, 3, 1, 19, 4, 16 is to be sorted using the above method. For demonstration purposes, assume the leftmost number to be the bottom of the stack and the rightmost number to represent the top of the stack.

Initially, s1 = 10, 75, 3, 1, 19, 4, 16 & s2 = - (empty)
The first element (16) is popped from s1 and stored in temp and pushed in s2, since it is empty.
s1 = 10, 75, 3, 1, 19, 4
s2 = 16

Now, temp = 4 (being removed from s1) and compared with the topmost element of s2 (16). As 4 < 16, it is pushed onto s2.
s1 = 10, 75, 3, 1, 19
s2 = 16, 4

Then, temp = 19. Since 4 < 19, it is removed from s2 and pushed to s1
s1 = 10, 75, 3, 1, 19, 4
s2 = 16
16 < 19, so it is also popped from s2 and pushed to s1
s1 = 10, 75, 3, 1, 19, 4, 16
s2 = -

Now that s2 is empty, 19 is pushed to s2.
s1 = 10, 75, 3, 1, 19, 4, 16
s2 = 19

This process continues till s1 is empty. The final stack s2 = 75, 19, 16, 4, 3, 1
Thus, the elements from s2 when popped return the numbers in an ascending order giving 1, 3, 4, 16, 19, 75 as the output.

Implementation

An implementation of the methods used in the above code can be found below in Java. It makes use of the predefined methods in Java's Stack Collection class.

private static void sort(MyStack<Integer> a) throws Exception {
      MyStack<Integer> s2 = new MyStack<>();
      while(!s1.isEmpty()) {
        int temp = s1.pop();
        while(!s2.isEmpty() && s2.peek() < temp) {
          s1.push(s2.pop());
        }
        s2.push(temp);
      }
      while(!s2.isEmpty()) {
        s1.push(s2.pop());
      }
   }

Time & Space Complexity

Time Complexity: O(N^2)
as Bubble sort is being used.

Space Complexity: O(N)
as two stacks are being used.

The time and space complexity of this algorithm is the same as that of bubble sort: O(N^2).

Hope this article at OpenGenus proved useful in helping you understand how to bubble sort with 2 stacks!