How to sort a stack using bubble sort? Can use another stack if necessary.

  • 1
    $\begingroup$ How did you approach to solve this problem? Did you think how you might utilize other stacks? $\endgroup$
    – sunnytheit
    Apr 4 '18 at 7:47

You must need an extra stack to sort an stack. With the help of two stacks this problem can be solved.

So, suppose you have n elements in the stack. and you have an other stack, which is empty.

Now, in bubble sort, after each iteration highest element reaches to its final position. So, to implement this algorithm, we can make use of that second stack.

For the first Iteration:
There are n elements in the stack, pop each element one by one in the empty(second stack) stack and keep track of highest element at each stage. After the first stack is completely empty, you will have the highest element of the stack. Now push that highest element in the first stack and then pop all the elements from the second stack and push them in first stack. So, after this iteration, highest element is set to its position. and we now have n-1 unsorted elements. Be alert to not to push highest element again in the first stack.

for example, elements are 5,10,7,2,15. So, after first iteration stack content is 15,5,10,7,2.

For the next Iterations:
So, after 1st iteration highest element is set, and we are remaining with n-1 unsorted elements in first stack, while the second stack is empty. So, during this iteration, instead of n elements, pop only n-1 elements to the second stack and keep track of maximum. After n-1 elements are pushed to second stack we have highest element among those n-1 elements, which second highest element of original stack. Push that element in the first stack, above the highest element already there. And then push all the elements back in the first stack from second stack.

So, after first iteration stack content is 15,10,5,7,2.

Then reduce the size to n-2 and follow same method.

Complexity of this method is same as bubble sort, which is $O(n^2)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.