Implement Bubble Sort

In this assignment series we will explore a number of sorting algorithms. Your goal is to understand both the implementation of the algorithm, and the circumstances under which it is a good choice.

Tasks

Read about the Bubble Sort Algorithm.

Then create a new branch and implement the algorithm in a new file in your data-structures repository. Your sorting function should only take in a list of values and return a sorted list of those same values. Otherwise, the implementation details are up to you.

Include tests that demonstrate that your sort works correctly.

Include an “if __name__ == ‘__main__’:” block at the end of your module that demonstrates the performance characteristics of this sort. Cover a variety of lengths of input in the best-case, worst-case, and average-case scenarios. Executing your module should print informative output about the performance of your sort to the terminal:

$ python bogosort.py

The bogosort randomly shuffles the items in a list until the list is sorted.
It performs best for very short lists

Input: [2, 1]
    number of runs: 500
    average time: 2.0e-4 seconds

Input: [randint(0, 1000000) for i in range(10000)]
    number of runs: 500
    average time: 2345.6 seconds

Add tests to demonstrate that the sorting algorithm works in both Python 2 and Python 3.

Add information about your implementation to your README.md file, including any sources and collaborations used in creating it.

Include the time complexity of your implementation of this sort algorithm in your README.

Submitting Your Work

When your work is complete and your tests are passing, create a pull request from your working branch back to master. Submit the URL of your pull request. When you’ve done this, you may merge your pull request, but do not delete your branch until your work has been graded.

Use the comment feature to add any questions, comments or reflections on your work.