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

# Solution 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¶

• Our buffer will hold elements in reverse sorted order, smallest at the top
• Store the current top element in a temp variable
• While stack is not empty
• While buffer is not empty or buffer top is > than temp
• Move buffer top to stack
• Move temp to top of buffer
• Return buffer

Complexity:

• Time: O(n^2)
• Space: O(n)

## Code¶

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

In [2]:
class MyStack(Stack):

def sort(self):
buff = MyStack()
while not self.is_empty():
temp = self.pop()
if buff.is_empty() or temp >= buff.peek():
buff.push(temp)
else:
while not buff.is_empty() and temp < buff.peek():
self.push(buff.pop())
buff.push(temp)
return buff


The solution can be further simplified:

In [3]:
class MyStackSimplified(Stack):

def sort(self):
buff = MyStack()
while not self.is_empty():
temp = self.pop()
while not buff.is_empty() and temp < buff.peek():
self.push(buff.pop())
buff.push(temp)
return buff


## Unit Test¶

In [4]:
%%writefile 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, [1])
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())
test.test_sort_stack(MyStackSimplified())

if __name__ == '__main__':
main()

Overwriting test_sort_stack.py

In [5]:
%run -i test_sort_stack.py

Test: Empty stack
Test: One element stack
Test: Two or more element stack (general case)
Success: test_sort_stack
Test: Empty stack
Test: One element stack
Test: Two or more element stack (general case)
Success: test_sort_stack