day 57 - quicksort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def swap(data, i, j):\n",
    "    data[i], data[j] = data[j], data[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def qsort3(data, left, right):\n",
    "    # sorted\n",
    "    if left >= right:\n",
    "        return\n",
    "\n",
    "    # select pivot\n",
    "    i = np.random.randint(left, right + 1)\n",
    "    swap(data, left, i)\n",
    "    pivot = data[left]\n",
    "\n",
    "    # i ~ points behind left partition\n",
    "    # j ~ points ahead of right partition\n",
    "    # k ~ current element\n",
    "    i, j, k = left, right, left + 1\n",
    "\n",
    "    # split to [left] + [pivot] + [right]\n",
    "    while k <= j:\n",
    "        if data[k] < pivot:\n",
    "            swap(data, i, k)\n",
    "            i += 1\n",
    "        elif data[k] > pivot:\n",
    "            swap(data, j, k)\n",
    "            j -= 1\n",
    "            k -= 1\n",
    "        k += 1\n",
    "\n",
    "    # recursion\n",
    "    qsort3(data, left, i - 1)\n",
    "    qsort3(data, j + 1, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def qsort(data):\n",
    "    qsort3(data, 0, len(data) - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[6 1 7 9 9 9 9 8 7 6 9 9 6 3 5 4 1 8 1 7 0 1 9 3 1 0 3 2 4 3 1 7 6 0 2 7 0\n",
      " 7 9 1 0 4 9 2 3 4 5 9 5 8 9 1 8 2 0 5 4 9 5 3 1 0 1 1 2 3 8 1 4 2 2 4 7 9\n",
      " 3 0 0 4 9 3 0 7 0 8 5 8 3 5 9 6 7 6 5 9 3 4 0 1 0 7]\n"
     ]
    }
   ],
   "source": [
    "data = np.random.randint(0, 10, 100)\n",
    "print(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3\n",
      " 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7\n",
      " 7 7 7 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9]\n"
     ]
    }
   ],
   "source": [
    "qsort(data)\n",
    "print(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}