sortingrecursionstack

sorting stack in ascending order using recursion (colsed)


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;
}

Solution

  • 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 popped 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
    }