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
• 3.63k
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)

OR
OR
Register

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

• Hire
• Post Projects

Post Projects

• All at 0 Cost ....
• Post Tech Job
• Select Best Bidder
• Track the Project
• Approve Work and Pay safely
• Browse Nerds
• Work
• Find Projects Find Projects
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
• Manage
• Company Company

Manage Company

• All at 0 Cost ....
• Manage Company and Employee Profiles
• Company wide Employee Productivity Reports
• Knowledge Sharing and Collaboration Tools
• Get Sales Lead and Bid for Tech Projects
• Send Invoices and Receive Payment Safely
• Learn
• Nerd Digest Nerd Digest
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
• Tech Q & A Tech Q & A
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General