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

# Challenge Notebook¶

## Constraints¶

• Is a naive solution sufficient?
• Yes
• Are duplicates allowed?
• Yes
• Can we assume the input is valid?
• No
• Can we assume this fits memory?
• Yes

## Test Cases¶

• None -> Exception
• Empty input -> []
• One element -> [element]
• Two or more elements

## 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 [ ]:
class InsertionSort(object):

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


## Unit Test¶

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

In [ ]:
# %load test_insertion_sort.py
import unittest

class TestInsertionSort(unittest.TestCase):

def test_insertion_sort(self):
insertion_sort = InsertionSort()

print('None input')
self.assertRaises(TypeError, insertion_sort.sort, None)

print('Empty input')
self.assertEqual(insertion_sort.sort([]), [])

print('One element')
self.assertEqual(insertion_sort.sort([5]), [5])

print('Two or more elements')
data = [5, 1, 7, 2, 6, -3, 5, 7, -1]
self.assertEqual(insertion_sort.sort(data), sorted(data))

print('Success: test_insertion_sort')

def main():
test = TestInsertionSort()
test.test_insertion_sort()

if __name__ == '__main__':
main()


## Solution Notebook¶

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