Scribd
Upload
6 views1 page

Recursive Stack Sorting Function

The document outlines a challenge assignment for sorting a stack using recursion without additional data structures. It provides a step-by-step algorithm for implementing the function sortAStack() in a header file, emphasizing the use of stack operations. The assignment includes two phases of automated testing, with the first phase focusing on integer values and the second on templates for various data types.

Uploaded by

niusha.habibi04
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views1 page

Recursive Stack Sorting Function

The document outlines a challenge assignment for sorting a stack using recursion without additional data structures. It provides a step-by-step algorithm for implementing the function sortAStack() in a header file, emphasizing the use of stack operations. The assignment includes two phases of automated testing, with the first phase focusing on integer values and the second on templates for various data types.

Uploaded by

niusha.habibi04
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Sorting a stack

Challenge assignment for Computer Programming, week 4

Write a function sortAStack() that uses recursion to sort the elements on a


stack “in place”. This means, the values must not be copied in or out another
container data structure like a vector, an array, or another stack. Write the
function according to the following algorithm:

● If the number of elements on the stack is smaller than 2, return. (Any


stack with less than 2 elements is sorted by definition.)
● If not, store the top element of the stack in a variable and remove it
from the stack.
● Repeat the following steps until done:
○ Recursively sort the remaining stack.
○ If the separately stored element is smaller or equal than
the current top element of the stack, put the stored
element on the stack and you are done.
○ If not, exchange the current top element and the
separately stored element and continue.

For this assignment, you are using the container class stack, just like you have
been using vector before. From stack, you need the functions push, pop, top,
size. You can find its description on the c++ reference site.

You implement your function in a header file sortastack.h. In the CodeGrade


environment, there are two .cpp files that include your header file, and test it.
Do not modify the .cpp files, they will not be used when executing the
automated tests!

The automated tests run in two phases. In phase one, your function will be
tested with int values. You can get 8 points if your function passes the tests of
phase 1. In phase 2, your function must be a template that accepts and sorts
stacks with any base type. (We will test it both with strings and with doubles.)
Phase 2 gives you another 2 points.

Once done, show your code within the 90 minutes lab session to your TA for
approval. For technical reasons, the grades will only be published to Canvas
after the deadline.

You might also like