Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Sort a stack using recursion in C?

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 1.33k
    Comment on it

    Sort a stack using recursion in C

    Sort a stack means inserting elements in Stack in sorted order.The sorting is to be implemented using recursion. In this first a stack is created by pushing elements into it then by popping elements from it,sortedInsert is performed on each element.

    C implementation of sorting a stack:

    //LinkedList is used to represent Stack:
    
    struct stack
    {
        int info;
        struct stack *next;
    };
    
    //Function to initialize stack:
    
    void initializeStack(struct stack **start)
    {
        *start = NULL;
    }
    
    //Function to check stack is empty:
    
    int isEmpty(struct stack *start)
    {
        if (start == NULL)
            return 1;
        return 0;
    } 
    
    //Function to push an item into stack
    
    void push(struct stack **start, int a)
    {
        struct stack *p = (struct stack *)malloc(sizeof(*p));
    
        if (p == NULL)
        {
            printf(stderr, "Memory allocation failed.\n");
            return;
        }
    
        p->info = a;
        p->next = *start;
        *start = p;
    }
    
    //Function to remove an item from stack
    
    int pop(struct stack **start)
    {
        int a;
        struct stack *temp;
    
        a = (*start)->info;
        temp = *start;
        (*start) = (*start)->next;
        free(temp);
    
        return a;
    }
    
    // Function to find top item
    
    int top(struct stack *start)
    {
        return (start->info);
    }
    
    void printingStack(struct stack *start)
    {
        while (start)
        {
            printf("%d ", start->info);
            start = start->next;
        }
        printf("\n");
    }
    
    // Recursive function to insert an item a in sorted way
    
    void sortedInsert(struct stack **start, int a)
    {
        if (isEmpty(*start) || a > top(*start))
        {
            push(start, a);
            return;
        }
        int temp = pop(start);
        sortedInsert(start, a);
    
        push(start, temp);
    }
    
    // Function to sort stack
    
    void sortStack(struct stack **start)
    {
        if (!isEmpty(*start))
        {
            int a = pop(start);
            sortStack(start);
            sortedInsert(start, x);
        }
    }
    
    int main(void)
    {
        struct stack *top;
    
        initializeStack(&top);
        push(&top, 20);
        push(&top, -5);
        push(&top, 19);
        push(&top, 15);
        push(&top, -3);
    
        printf("Stack elements before sorting:\n");
        printingStack(top);
    
        sortStack(&top);
        printf("\n\n");
    
        printf("Stack elements after sorting:\n");
        printingStack(top);
    
        return 0;
    }
    

    Output:

    Stack elements before sorting: -3 15 19 -5 20

    Stack elements after sorting: 30 19 15 -3 -5

    Explanation of above program:

    In main a stack top is initialized to NULL by calling initializeStack function.Five elements are pushed into the stack by calling push function. Since stack follows LIFO functionality, last inserted element will be at the top. When sortStack function is called, address of top is passed to it. In sortStack function, elements are popped one by one till stack is empty and in turn sortedInsert function is called from inside the sortStack passing address of start and element as parameter. Since sortStack function calls itself, the line sortedInsert(start, x) will internally be stored in another stack and when all the elements will be popped then internal stack will pop and perform sortedInsert(start, x) in LIFO manner. In sortedInsert function first Base case is checked i.e either stack is empty or newly inserted item is greater than top (more than all existing) if true then element will be inserted in stack and returns from there but if false then top element is popped out and sortedInsert function will be called recursively and finally pushing elements in sorted manner.

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: