How to sort a Stack

 Category: Data Structure And Algorithms Tags:

Suppose a stack is given having values:

`15`
`-8`
`1`
`-5`
`10`

I want to sort it so sorted stack should look like:

`15`
`10`
`1`
`-5`
`-8`

 Like 0 People
 Nikhil Joshi Ceo & Founder at Dotnetlovers Atricles: 158 Questions: 16 Given Best Solutions: 16 *

Using recursion:
Sorting stack is similar to sort an array using insertion sort, in insertion sort we do insert elements at their correct position. But in stack we cannot move elements like we can in array so first we have to pop all the elements then we can start inserting them back one by one.

When we insert elements back one by one we check if peek element is smaller than current element or not, if yes we simply push the element else we pop the top element from stack and compare next top element with element we are trying to insert, we do same until we find correct position of the element.

The stack is: 15 (top), -8, 1, -5, 10 (bottom) and suppose now all elements are popped out and we will insert them back one by one (in stack last popped out element will be inserted back first so 10 will be inserted first and then -5 and so on):

10 -> 10

-5, 10 -> 10, -5

1, 10, -5 -> 10, 1, -5

-8, 10,1,-5 -> 10, 1, -5, -8

15, 10, 1, -5, -8 -> 15, 10, 1, -5, -8

Go through below implementation:

```class Program
{
static void Main(string[] args)
{
Stack<int> stack = new Stack<int>();
stack.Push(10);
stack.Push(-5);
stack.Push(1);
stack.Push(-8);
stack.Push(15);

//Sort
Sort(stack);

//Item
Console.WriteLine("Sorted stack:");
while (stack.Count > 0)
{
Console.WriteLine(stack.Pop());
}

}

static void Sort(Stack<int> stack)
{
//No elements left in stack
if (stack.Count == 0)
return;

int element = stack.Pop();
//Recursion
Sort(stack);
RearrangeAndInsert(stack, element);
}

static void RearrangeAndInsert(Stack<int> stack, int element)
{
//Insert if no elements present in stack or peek element is smaller than current element
if (stack.Count == 0 || element >= stack.Peek())
stack.Push(element);
else
{
int temp = stack.Pop();
RearrangeAndInsert(stack, element);
stack.Push(temp);
}
}
}```

Output:

Sorted stack:
15
10
1
-5
-8

Using temporary stack:

Same concept is used of insertion sort only temporary stack is used instead of recursion.

```class Program
{
static void Main(string[] args)
{
Stack<int> stack = new Stack<int>();
stack.Push(10);
stack.Push(-5);
stack.Push(1);
stack.Push(-8);
stack.Push(15);

stack = Sort(stack);

//Item
Console.WriteLine("Sorted stack:");
while (stack.Count > 0)
{
Console.WriteLine(stack.Pop());
}

}

static Stack<int> Sort(Stack<int> stack)
{
Stack<int> temp = new Stack<int>();
//Until all elements are moved
while (stack.Count > 0)
{
var element = stack.Pop();

//If peek element in temp stack is grater than item we want to insert
//Pop elements from temp and push in stack until we have correct position for element
while (temp.Count > 0 && element < temp.Peek())
{
stack.Push(temp.Pop());
}
//Push element at its right position
temp.Push(element);
}
return temp;
}
}```

Sorted stack:
15
10
1
-5
-8

Like 0 People on 3 May 2020