Implement Quick 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 Quick Sort Algorithm.

When you’re ready, create a new branch for your data-structures repository and add a module to implement the sorting algorithm. 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. So, for example, if you were writing the “Bogo Sort” algorithm:

$ 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.