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

Solution Notebook

Constraints

  • Is a naive solution sufficient (ie not in-place)?
    • 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

Wikipedia's animation: alt text

  • 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)

Misc:

  • More sophisticated implementations are in-place, although they still take up recursion depth space
  • Most implementations are not stable

See Quicksort on wikipedia:

Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures [presumably because it has good cache locality], and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time.

See: Quicksort vs merge sort

Code

In [1]:
from __future__ import division


class QuickSort(object):

    def sort(self, data):
        if data is None:
            raise TypeError('data cannot be None')
        return self._sort(data)

    def _sort(self, data):
        if len(data) < 2:
            return data
        equal = []
        left = []
        right = []
        pivot_index = len(data) // 2
        pivot_value = data[pivot_index]
        # Build the left and right partitions
        for item in data:
            if item == pivot_value:
                equal.append(item)
            elif item < pivot_value:
                left.append(item)
            else:
                right.append(item)
        # Recursively apply quick_sort
        left_ = self._sort(left)
        right_ = self._sort(right)
        return left_ + equal + right_

Unit Test

In [2]:
%%writefile test_quick_sort.py
import unittest


class TestQuickSort(unittest.TestCase):

    def test_quick_sort(self):
        quick_sort = QuickSort()

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

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

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

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

        print('Success: test_quick_sort\n')


def main():
    test = TestQuickSort()
    test.test_quick_sort()


if __name__ == '__main__':
    main()
Overwriting test_quick_sort.py
In [3]:
%run -i test_quick_sort.py
None input
Empty input
One element
Two or more elements
Success: test_quick_sort