This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Solution Notebook

Problem: Sort a stack. You can use another stack as a buffer.

Constraints
Test Cases
Algorithm
Code
Unit Test

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

Test Cases

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

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
%load ../stack/stack.py



In [2]:

    
class MyStack(Stack):

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

Unit Test



In [3]:

    
%%writefile test_sort_stack.py
from random import randint
from nose.tools import assert_equal


class TestSortStack(object):

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

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

        print('Test: One element stack')
        sorted_stack = self.get_sorted_stack([1])
        assert_equal(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(numbers)
        sorted_numbers = []
        for _ in range(num_items):
            sorted_numbers.append(sorted_stack.pop())
        assert_equal(sorted_numbers, sorted(numbers, reverse=True))

        print('Success: test_sort_stack')


def main():
    test = TestSortStack()
    test.test_sort_stack()


if __name__ == '__main__':
    main()









    



Overwriting test_sort_stack.py



In [4]:

    
%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