This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Challenge Notebook¶

## Constraints¶

• When sorted, should the largest element be at the top or bottom?
• Top
• Can you have duplicate values like 5, 5?
• Yes
• Can we assume we already have a stack class that can be used for this problem?
• Yes
• Can we assume this fits memory?
• Yes

## Test Cases¶

• Empty stack -> None
• One element stack
• Two or more element stack (general case)

## Algorithm¶

Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.

## Code¶

In [ ]:
%run ../stack/stack.py

In [ ]:
class MyStack(Stack):

def sort(self):
# TODO: Implement me
pass


## Unit Test¶

The following unit test is expected to fail until you solve the challenge.

In [ ]:
# %load test_sort_stack.py
from random import randint
import unittest

class TestSortStack(unittest.TestCase):

def get_sorted_stack(self, stack, numbers):
for x in numbers:
stack.push(x)
sorted_stack = stack.sort()
return sorted_stack

def test_sort_stack(self, stack):
print('Test: Empty stack')
sorted_stack = self.get_sorted_stack(stack, [])
self.assertEqual(sorted_stack.pop(), None)

print('Test: One element stack')
sorted_stack = self.get_sorted_stack(stack, )
self.assertEqual(sorted_stack.pop(), 1)

print('Test: Two or more element stack (general case)')
num_items = 10
numbers = [randint(0, 10) for x in range(num_items)]
sorted_stack = self.get_sorted_stack(stack, numbers)
sorted_numbers = []
for _ in range(num_items):
sorted_numbers.append(sorted_stack.pop())
self.assertEqual(sorted_numbers, sorted(numbers, reverse=True))

print('Success: test_sort_stack')

def main():
test = TestSortStack()
test.test_sort_stack(MyStack())
try:
test.test_sort_stack(MyStackSimplified())
except NameError:
# Alternate solutions are only defined
# in the solutions file
pass

if __name__ == '__main__':
main()


## Solution Notebook¶

Review the Solution Notebook for a discussion on algorithms and code solutions.