I am interested to know how i can sort a stack in ascending order using recursion
I already sort an stack in descending order using recursion but can't find a logic for ascending order.
Please tell me some logic for it .
Thanks in advance
edit:
my code of sort function and insert function for sort the stack in descending order
void sort(stack<int>&st)
{
if(st.size()==1)
return;
int ele=st.top();
st.pop();
sort(st);
insert(st,ele);
return;
}
void insert(stack<int>&st,int ele)
{
int x=st.size(),y=st.top();
if(x==0||y<=ele)
{
st.push(ele);
return;
}
int t=st.top();
st.pop();
insert(st,ele);
st.push(t);
return;
}
First write insert
that takes a sorted stack, s
, and a value to be inserted, v
. This function will ensure v
will be inserted in order and maintains the ascending sort of s
-
function insert(s, v)
{ if (s.length == 0) return push(s, v)
const r = []
while (s.length)
if (peek(s) < v) break
else move1(s, r)
push(s, v)
move(r, s)
}
If we start with an empty stack, s = []
, we can insert
values one at a time to get a stack sorted in ascending order -
const s = []
insert(s, 7)
insert(s, 2)
insert(s, 9)
insert(s, 4)
console.log(s)
[2,4,7,9]
Our insert
function depends on other convenient stack operations we need to write. Such as move1
that moves one item from q
to p
-
function move1(q, p)
{ push(p, pop(q)) }
And move
that moves all of q
to p
-
function move(q, p)
{ while (q.length) move1(q, p) }
Now if we start with an unsorted stack, s
, to sort descending
, we create a new stack, r
, and insert
each pop
ped value from s
. The temporary r
will be in ascending order, but the goal is to sort s
! Simply move
all r
to s
and now s
is in descending order -
function descending(s)
{ const r = []
while(s.length)
insert(r, pop(s))
move(r, s)
}
const q = [7,1,6,5,4,9,3]
descending(q)
console.log(q)
[1,3,4,5,6,7,9]
To sort ascending
, we first sort by descending
then simply reverse
-
function ascending(s)
{ descending(s)
reverse(s)
}
function reverse(s)
{ const q = [], p = []
move(s, q)
move(q, p)
move(p, s)
}
const q = [7,1,6,5,4,9,3]
ascending(q)
console.log(JSON.stringify(q))
[9,7,6,5,4,3,1]
Finally implement these other basic stack operations, pop
, push
, and peek
-
function pop(s)
{ return s.pop() }
function push(s, v)
{ s.push(v) }
function peek(s)
{ const v = pop(s)
push(s, v)
return v
}