Quicksort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Very Naive Quicksort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an example of **quicksort** in Haskell. \n",
    "\n",
    "This is a popular demo snippet, demonstrating the basic syntax of Haskell; *however*, it's not a real quicksort, so it's somewhat misleading.\n",
    "\n",
    "First, let's define a partition function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "partition :: Ord a => a -> [a] -> ([a], [a])\n",
    "partition pivot xs = (filter (< pivot) xs, filter (>= pivot) xs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's verify that it works by testing it on a few inputs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "partition 3 [0, 1, 2, 3, 4, 5] == ([0, 1, 2], [3, 4, 5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "partition 10 [] == ([], [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "partition 'c' \"abcd\" == (\"ab\", \"cd\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's build our fake quicksort based on this partition:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "quicksort :: Ord a => [a] -> [a]\n",
    "quicksort [] = []\n",
    "quicksort (x:xs) = quicksort start ++ [x] ++ quicksort end\n",
    "  where\n",
    "    (start, end) = partition x xs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can verify that it works using QuickCheck:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "+++ OK, passed 100 tests."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import Test.QuickCheck\n",
    "import Data.List (sort)\n",
    "\n",
    "prop_sorting :: [Int] -> Bool\n",
    "prop_sorting xs = sort xs == quicksort xs\n",
    "\n",
    "quickCheck prop_sorting"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "version": "7.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}