{
 "metadata": {
  "name": "",
  "signature": "sha256:5bf0d0467aaa6624c2fa9d0d73f2a53eb1b4364af2ab2f3f3b2f06849d609400"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sorting import bubble_sort, insertion_sort, merge_sort, quicksort\n",
      "from time import time\n",
      "from random import randint\n",
      "import matplotlib.pyplot as plt\n",
      "\n",
      "# generate array of random integers\n",
      "xs = [randint(0, 1e6) for i in range(100000)]\n",
      "\n",
      "# sort using different methods\n",
      "times = []\n",
      "# 1. bubble sort\n",
      "start = time()\n",
      "bubble_sort(xs.copy())\n",
      "stop = time()\n",
      "times += [stop - start]\n",
      "\n",
      "# 2. insertion sort\n",
      "start = time()\n",
      "insertion_sort(xs.copy())\n",
      "stop = time()\n",
      "times += [stop - start]\n",
      "\n",
      "# 3. merge sort\n",
      "start = time()\n",
      "merge_sort(xs)\n",
      "stop = time()\n",
      "times += [stop - start]\n",
      "\n",
      "# 4. quicksort\n",
      "start = time()\n",
      "quicksort(xs)\n",
      "stop = time()\n",
      "times += [stop - start]\n",
      "\n",
      "# plot results\n",
      "plt.figure(figsize=(10,6))\n",
      "labels = ['bubble', 'insertion', 'merge', 'quicksort']\n",
      "x = [1,2,3,4]\n",
      "plt.plot(x, times, 'ro')\n",
      "_ = plt.xticks(x, labels, rotation=45)\n",
      "plt.ylabel('Execution time, [sec]')\n",
      "plt.grid()\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}