{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation of Quick Sort\n",
    "\n",
    "A quick sort first selects a value, which is called the pivot value. Although there are many different ways to choose the pivot value, we will simply use the first item in the list. The role of the pivot value is to assist with splitting the list. The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Resources for Review\n",
    "\n",
    "Check out the resources below for a review of Insertion sort!\n",
    "\n",
    "* [Wikipedia](https://en.wikipedia.org/wiki/Quicksort)\n",
    "* [Visual Algo](http://visualgo.net/sorting.html)\n",
    "* [Sorting Algorithms Animcation with Pseudocode](http://www.sorting-algorithms.com/quick-sort)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def quick_sort(arr):\n",
    "    \n",
    "    quick_sort_help(arr,0,len(arr)-1)\n",
    "\n",
    "def quick_sort_help(arr,first,last):\n",
    "    \n",
    "    if first<last:\n",
    "        \n",
    "\n",
    "        splitpoint = partition(arr,first,last)\n",
    "\n",
    "        quick_sort_help(arr,first,splitpoint-1)\n",
    "        quick_sort_help(arr,splitpoint+1,last)\n",
    "\n",
    "\n",
    "def partition(arr,first,last):\n",
    "    \n",
    "    pivotvalue = arr[first]\n",
    "\n",
    "    leftmark = first+1\n",
    "    rightmark = last\n",
    "\n",
    "    done = False\n",
    "    while not done:\n",
    "\n",
    "        while leftmark <= rightmark and arr[leftmark] <= pivotvalue:\n",
    "            leftmark = leftmark + 1\n",
    "\n",
    "        while arr[rightmark] >= pivotvalue and rightmark >= leftmark:\n",
    "            rightmark = rightmark -1\n",
    "\n",
    "        if rightmark < leftmark:\n",
    "            done = True\n",
    "        else:\n",
    "            temp = arr[leftmark]\n",
    "            arr[leftmark] = arr[rightmark]\n",
    "            arr[rightmark] = temp\n",
    "\n",
    "    temp = arr[first]\n",
    "    arr[first] = arr[rightmark]\n",
    "    arr[rightmark] = temp\n",
    "\n",
    "\n",
    "    return rightmark"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 4, 5, 6, 7, 11, 12]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [2,5,4,6,7,3,1,4,12,11]\n",
    "quick_sort(arr)\n",
    "arr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}