Sort a Stack using another stack

ghz 10months ago ⋅ 99 views

To sort a stack using another stack, you can follow these steps:

  1. Create an auxiliary stack.
  2. While the input stack is not empty:
    • Pop the top element from the input stack.
    • If the auxiliary stack is empty or the top element of the auxiliary stack is greater than or equal to the popped element, push the popped element onto the auxiliary stack.
    • Otherwise, keep popping elements from the auxiliary stack and pushing them onto the input stack until you find the correct position for the popped element.
  3. Repeat step 2 until the input stack is empty.
  4. The auxiliary stack now contains the sorted elements in ascending order.

Here's the Python code to implement this algorithm:

def sort_stack(stack):
    aux_stack = []

    while stack:
        # Pop the top element from the input stack
        temp = stack.pop()

        # Move elements from auxiliary stack to input stack until correct position for temp is found
        while aux_stack and aux_stack[-1] > temp:
            stack.append(aux_stack.pop())

        # Place temp in the correct position in the auxiliary stack
        aux_stack.append(temp)

    return aux_stack

# Example usage:
stack = [4, 2, 5, 1, 3]
sorted_stack = sort_stack(stack)
print("Sorted stack:", sorted_stack)  # Output: [1, 2, 3, 4, 5]

This algorithm has a time complexity of O(n^2), where n is the number of elements in the stack. This is because, in the worst case, each element may need to be moved from the input stack to the auxiliary stack and back again. However, the average case performance is better, especially for partially sorted input stacks.

#algorithm