{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solution Notebook" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem: Implement quick sort.\n", "\n", "* [Constraints](#Constraints)\n", "* [Test Cases](#Test-Cases)\n", "* [Algorithm](#Algorithm)\n", "* [Code](#Code)\n", "* [Pythonic-Code](#Pythonic-Code)\n", "* [Unit Test](#Unit-Test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Constraints\n", "\n", "* Is a naive solution sufficient (ie not in-place)?\n", " * Yes\n", "* Are duplicates allowed?\n", " * Yes\n", "* Can we assume the input is valid?\n", " * No\n", "* Can we assume this fits memory?\n", " * Yes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Test Cases\n", "\n", "* None -> Exception\n", "* Empty input -> []\n", "* One element -> [element]\n", "* Two or more elements" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm\n", "\n", "Wikipedia's animation:\n", "![alt text](http://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif)\n", "\n", "* Set pivot to the middle element in the data\n", "* For each element:\n", " * If current element is the pivot, continue\n", " * If the element is less than the pivot, add to left array\n", " * Else, add to right array\n", "* Recursively apply quicksort to the left array\n", "* Recursively apply quicksort to the right array\n", "* Merge the left array + pivot + right array\n", "\n", "Complexity:\n", "* Time: O(n log(n)) average, best, O(n^2) worst\n", "* Space: O(n)\n", "\n", "Misc:\n", "\n", "* More sophisticated implementations are in-place, although they still take up recursion depth space\n", "* Most implementations are not stable\n", "\n", "See [Quicksort on wikipedia](https://en.wikipedia.org/wiki/Quicksort):\n", "\n", "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.\n", "\n", "See: [Quicksort vs merge sort](http://stackoverflow.com/questions/70402/why-is-quicksort-better-than-mergesort)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Code" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from __future__ import division\n", "\n", "\n", "class QuickSort(object):\n", "\n", " def sort(self, data):\n", " if data is None:\n", " raise TypeError('data cannot be None')\n", " return self._sort(data)\n", "\n", " def _sort(self, data):\n", " if len(data) < 2:\n", " return data\n", " equal = []\n", " left = []\n", " right = []\n", " pivot_index = len(data) // 2\n", " pivot_value = data[pivot_index]\n", " # Build the left and right partitions\n", " for item in data:\n", " if item == pivot_value:\n", " equal.append(item)\n", " elif item < pivot_value:\n", " left.append(item)\n", " else:\n", " right.append(item)\n", " # Recursively apply quick_sort\n", " left_ = self._sort(left)\n", " right_ = self._sort(right)\n", " return left_ + equal + right_" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Unit Test\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting test_quick_sort.py\n" ] } ], "source": [ "%%writefile test_quick_sort.py\n", "import unittest\n", "\n", "\n", "class TestQuickSort(unittest.TestCase):\n", "\n", " def test_quick_sort(self):\n", " quick_sort = QuickSort()\n", "\n", " print('None input')\n", " self.assertRaises(TypeError, quick_sort.sort, None)\n", "\n", " print('Empty input')\n", " self.assertEqual(quick_sort.sort([]), [])\n", "\n", " print('One element')\n", " self.assertEqual(quick_sort.sort([5]), [5])\n", "\n", " print('Two or more elements')\n", " data = [5, 1, 7, 2, 6, -3, 5, 7, -1]\n", " self.assertEqual(quick_sort.sort(data), sorted(data))\n", "\n", " print('Success: test_quick_sort\\n')\n", "\n", "\n", "def main():\n", " test = TestQuickSort()\n", " test.test_quick_sort()\n", "\n", "\n", "if __name__ == '__main__':\n", " main()" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "None input\n", "Empty input\n", "One element\n", "Two or more elements\n", "Success: test_quick_sort\n", "\n" ] } ], "source": [ "%run -i test_quick_sort.py" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.2" } }, "nbformat": 4, "nbformat_minor": 1 }