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: Implement quick sort.

Constraints
Test Cases
Algorithm
Code
Pythonic-Code
Unit Test

Constraints

Is a naiive solution sufficient (ie not in-place)?
- Yes

Test Cases

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

Algorithm

Wikipedia's animation:

Set pivot to the middle element in the data
For each element:
- If current element is the pivot, continue
- If the element is less than the pivot, add to left array
- Else, add to right array
Recursively apply quicksort to the left array
Recursively apply quicksort to the right array
Merge the left array + pivot + right array

Complexity:

Time: O(n log(n)) average, best, O(n^2) worst
Space: O(n), n extra space, n recursion depth, generally not stable

Code



In [1]:

    
from __future__ import division


def quick_sort(data):
    if len(data) < 2:
        return data
    left = []
    right = []
    pivot_index = len(data) // 2
    pivot_value = data[pivot_index]

    # Build the left and right partitions
    for i in range(0, len(data)):
        if i == pivot_index:
            continue
        if data[i] < pivot_value:
            left.append(data[i])
        else:
            right.append(data[i])

    # Recursively apply quick_sort
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [pivot_value] + right

Pythonic-Code

The following code from Stack Overflow is very concise, although it might be a little difficult to read:



In [2]:

    
def quick_sort_alt(arr):
    if len(arr) <= 1:
        return arr
    else:
        return quick_sort_alt([x for x in arr[1:] if x < arr[0]]) + [arr[0]] + quick_sort_alt([x for x in arr[1:] if x >= arr[0]])

Unit Test



In [3]:

    
%%writefile test_quick_sort.py
from nose.tools import assert_equal


class TestQuickSort(object):
    def test_quick_sort(self, func):
        print('Empty input')
        data = []
        sorted_data = func(data)
        assert_equal(sorted_data, [])

        print('One element')
        data = [5]
        sorted_data = func(data)
        assert_equal(sorted_data, [5])

        print('Two or more elements')
        data = [5, 1, 7, 2, 6, -3, 5, 7, -1]
        sorted_data = func(data)
        assert_equal(sorted_data, sorted(data))

        print('Success: test_quick_sort\n')


def main():
    test = TestQuickSort()
    test.test_quick_sort(quick_sort)
    try:
        test.test_quick_sort(quick_sort_alt)
    except NameError:
        # Alternate solutions are only defined
        # in the solutions file
        pass


if __name__ == '__main__':
    main()









    



Overwriting test_quick_sort.py



In [4]:

    
%run -i test_quick_sort.py









    



Empty input
One element
Two or more elements
Success: test_quick_sort

Empty input
One element
Two or more elements
Success: test_quick_sort