Some sorting algorithms

sorting.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "distrs = [\n",
    "    [random.randint(0, 100) for i in range(1000)],\n",
    "    [int(random.uniform(0, 100)) for i in range(1000)],\n",
    "    [int(random.normalvariate(50, 12.5)) for i in range(1000)],\n",
    "    [int(random.triangular(0, 100)) for i in range(1000)],\n",
    "]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pprint import pprint\n",
    "#pprint(distrs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEACAYAAAC9Gb03AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X2wHFWZx/HvhYQbEnNTIUDA4iUYorwGwSKyUOCFyIvo\nUiCwibwqFKSWEijEoKCYZLeoXXTB0i0od7MEcMlWlICCi4BFkpEgLmFRDBIISUgo1hWQt+SShfDi\n7B9Pj9N37ryec3r6ZX6fqqk7t2f6dN+Zp8/tPn3Oc0BERERERERERERERERERERERERERAI4BHgm\n9lgHrAB2Ah4A1gL3AxPT2kERR4ptKZy+QOVcBOwPTAD+C1gIXAwcCFweaBsiaVBsiwCjsDOfDwOb\ngPHR8gHsbEgkrxTbIpEvAT+Ing/VvPZal/dFJCTFtgiwPbAG2Cf6/c2a12sPDpG8UGxLYWznuf5s\n4AlgY/T7ZmBc9HwC8HrtClOnTi0DeuiR1GM9YSi29cjaI1Rsd2Q74PfAAbFltwIXRM/nALfUWa+c\nlnnz5vXUdtPcdlrbxQ6InoptxVdvbNsntn3O6E/HbkitiS2bC8zCuqCdBlzlUb5IWhTbUiijPNa9\nM3rEvQqc6FGmSBYotqVQfNvoc2VwcLCntpvmttP8m3uN4qt3tu0q1ICpTkTNTSLh9fX1QTpxDYpt\nSZBPbPfUGb2ISC9SRS8iUnCq6EVECk4VvYhIwflU9GOBm7D+xi9gowUnkdNUrgMDO9HX19fwMTCw\nU9q72DNafRd9fTs0fC2AzMW1T2wqrgX8eifcArwIzI8tWwT8muapXDPZM8EqiWb71UcW97uI2vku\nGr/u3evGNa4hodj2iU3FdXH49LpxPSB2Ax4CDmZ4FG2Klg1hqVyfAKbVrKuKXppKsaL3iWtQRS8J\nSqN75UFY9CwHngXuwBI+TaKa1W8LNiuPSF4orqWQXFMg7Ao8h2X4+wD4DjAveh63Q72V58+f/5fn\ng4ODuRxpJllRih5BeMU1KLbzbmBgJ4aG3qj72vjxE9myZUTS0sSUSiVKpVKQslwvcU8CzgLOi34/\nGkv6NB1rv9yK3cRaDexds66abqSpFJtufOIa1HSTe80/r3Q/qzSabh4FjqEa7CcDj2GTKM+Kls3G\n2jtF8kJxXXCteiFlcb9C9Izy+ctmAjcAo7ED5BLsbGcxMAWbsOFsRk65pjP6nPC5jG22bqv1U+51\n4xrXoDP6zPONraQ+q3auJNLodeNDFX0X+VTWPpexSVdOCVb0PlTRZ1yvVvQ++eglB6ySrx9AQ0Pp\nXaqKSPcoBYKISMGpoheRQml2Y7NXqelGRAqlWXNlerdv0pVKRb9s2bK6y/v6+jjyyCMZM2ZMIttt\n1RMkj/z+plE9fZYj0it8jvIS1t/4nej3fwf+BeuGtg/wPDb4pLYWKk+YcFzdAt95ZzVLlizk1FNP\n9ditxlrd2c5j7wT/HirJ9EDIea+bEo6xrV436fM9ztXrZrgycDrwm9iyRcBdVLP8zadOlr/Nm+uf\n0Q8MnM4HH9SONhfpOufYFski35uxtf9djgOWRM+XYCMLRfJIsd2Cz7wBzV9TnvzQfCr6MrAUy/J3\nI7A9yvInxaDYbkP1pmejx3uOr5UZGhrSP4GAfJpuPgNsA3YEbscuY9vO8ieSYc6xPX78rnUL/PjH\nD2PlygcC7mLRvY8G+oXjU9Fvi36+DfwM+CSwGcvfXcny12B8/fzY88HoYc4550ucccYZddfqdppQ\nyYMSAdMUVzjH9ltvnR/77UjgKGATa9fODr2PUnglKrEdT3/twvVfYz/wV9FejAZ+hF3qHg+sxG5c\nzQFmABfWrFtu9J96YOB0tmy5m6TueqvXTSevtV63oL1uEojt59lll0/zyivPO+1QVnvd5DP2erPX\njWsbfR+wAMvktxpYD/wHlrt7FjaJ8mnAVY7l54rvBMxJpyjNplFZHb2o2BYnWT6OXZtu3gE+VWf5\nq8CJ7ruTT81H4rVuU+zNxGON22BTHr2o2BYnWT6OletGRKTgVNGLZIAScUmSlNRMJAOUiEuSpDN6\nEZGC0xm9OFLmy068+uof9HnlXn5jXhW9OGrWawbU3DBcufwu+rzyLr8xH6LpZi7wVPR8EvAA1tf4\nfmBigPILoHGf8byeIfSAHonr5rGZdv9vCcO3oj8K+ALVf3PfwVK5fgz4CcNzHfSwyplAo4dkTA/F\ndfPYLNpEPb3Kp6LfGcvsN4fqNYtSuUreKa6lcFzb6PuA27DL21diy5XKVfIsp3Gd35uEvSPd78i1\nor8CeBR4GJgSW95mmuL5seeDxLNXZpcOpmwqETB7pWdcQzqxndl0EvIXLjdyS6SdvfL7wAnYno8G\n9gBWAXsBB1JN5boam3szLrfZK5NZt3XZvlki8/g3p5S90ieuoUn2SpjaZJ8ru5zN7ym5LKP5y16Z\n5t+bRvbKy4D9gP2BmcA64BhgBZbhD2A28JBj+SJpUFyPkNkso9KBEP3o4/+K5gKLga9haV7PDlC+\nSBoU10A2m4XUjNqpEBX9JmB69FypXKUoNqG4zqj8DlxKi3LdiIgUXKEq+lYzPYmI9KJC5bppNdOT\nLulEpBcV6oxeRERGytkZve62i4h0yueM/g7gWeA5YCkwlsSz/Ck5mHRFCrEtkhyfiv7fsMElHwW2\nAWdS6Cx/0kMU21IoPhV9Kfo5DtgFeAZl+UuActmnoBT9VGxLIfjejL0A+CPwJPA4mc/yl0dqrkqJ\nYlsKw7eiX4S1VU4GzqejLH8imabYlsII0evmAyzJ0wxgM3a5W8ny93r9VebHng+SjzTFkk0lAqYp\nrqXYlhSVSDtN8UQs+B/E0rkuAe7FonoldjY0J3rPhTXreqUpzm5q3CzuV5JlZ3m/vEbGJRDb+U5T\nnL396r1100pTDNVMfk9HP2/HsvzNwrqgnQZc5VG+SFoU21Iork03b2C9EGopy5/knWJbCkcpEERE\nCk4VvYhIwamiFxEpOFX0IiIFp4peRKTgVNGLiBSca0Xfj40YXI/1K746Wq5UrpJ3im0pHJ8z+uuA\nfYHp2ECSQ1AqVykGxbYUimtFvw1YEXu+Hkv+pFSukneKbSmcEG30k4EjgMdQKlcpFsW2FIJv9sox\nwJ3ANVh2vzZTuc6PPR9EGf7EXYmEslcqtiVlJdLOXgl20+ouLKPf9dGyF4ADqKZyXQ3sXbOeslcW\nouws75dXXEPw2Fb2Sq2bz+yVY7HUrQ9TPRAAlmM3rwBmY70XRPJEsS2F49p0MwP4FLAX8KVo2d1Y\nKtfFVNO8nu27gyJdptiWwnGt6EtYG2Y9SuUqeVZCsS0Fo5GxIiIFp4peRKTgVNGLiBScKnoRkYJT\nRS8iUnC+Ff1hwO9ivyvDnxSB4loKxaeivwH4BcNHainDn+Sd4loKx6eivxL4BMMPCGX4k7xTXEvh\n+Dbd1OZdUIY/KQLFtRRK6JuxbWb4E8kVxbXkmm+a4lqbgXFUM/y9Xv9t82PPB1EqV3FXIqE0xXFt\nxjUotiWcEqHSFPuaAjwV+/1W4ILo+RzgljrrlKFc9zEw8Plys9ebv+b7elrr5rXsLO9XKnHdJLY3\n6HvSul7rlsuV97jxabpZANwDfAR4HDgay/A3C+uGdhpwlUf5ImlQXEvh+E7Q4KLc6B+TJh7JU9lZ\n3q9U4hoaxrYmHtG6+Zx4REREckIVvYhIwamiFxEpOFX0IiIFp4peRKTgVNGLiBRcEhX9ydhgk2eB\nqxMoXyQtiu0RSj223bS37SZ0RT8OuBmYCRwIfAY4NPA2RNKg2K6r1GPbTXvbbkJX9DOA3wCvYImg\nlqKUrlIMim3JrdBJzT6MHQgVfwKmjXzbjXVX3rZtXeDdEQnGI7ZfS2aPRNoUuqIv0zql6wa4cmq9\nlbdtqzxrNsq31Qhgn9fTWjevZWdyvza0WNGVV2ybIn5PC6KHy7p53G7ltUbbTma7UfoD59gOXdG/\nBOwS+31X4I8179k38DZFukGxLRL5ELAROyBGAQ9j2f9E8k6xLRLzWeD3WErXb6a8LyIhKbZFRERE\nujXgpB94CFiPnX1VtjUJeCBadj8wMcF9mEt1lqJubXcscBOwDngBm/auG9s+H/tb1wJ3Yn3Ok9zu\nYcDvYr8329Y3sHh7Cjgp4D7EdXMgVS/GdlpxDYrtjo0DNmE3sbbH2jiTGnDSDxwbe/4kcAiwCLgo\nWn4x8L2Etn8U1ud6dfR7t7Z7C8MnLe3GtidjvQHGRb/fBHw9we3eALxK9bOlybaOAVZi3Rl2ww6W\n0B0QuhnX0JuxnUZcg2LbybHA3bHfL8P+I3XDUuAE7IAcHy0bwM4QQtsZeAw4nOpZTze2uxvWflzb\nRyvpbe+J9UjZLfr9WuArCW93b4bP6Rrf1oTYthYAl8bedzdWUYWUZlxD8WM7rbiGAsV2N5Oa1Rtw\nsluD94Y0GTgCC9BJwFC0fAuwU+Bt9QG3YZe28b816e0CHIT19V6OXc7dQfUyM8ltvwh8F3gGWIhV\nAjcnvN3agz6+rc2xbe2OxVlFEjGXVlxDb8R2WnENBYrtblb07Qw4CW0M1q52DfYhJb39K4BHscv3\n+BfWjb97V+A57OzuAOBlYF4Xtj0BOAWrcB4E9sHywXTzu262raT3I424ht6J7bTiGgoU291s02ln\nwElI/dhl7X3AD6Nlm7Gzga3Yl/h64G1OwQLyXGA0sAd2YLyZ8HaJytwKvBf9/lPs7CvpbR+PnfGs\njR5vAV/uwnbjGn2vtTG3C+FjrttxDb0V22nFNRQotrt5Rr8Ku/SpDDg5HViW0LbGAvdigXh9bPly\nYFb0fDbWeyGky4D9gP2x//zrsJsmKxLeLtjZ1jFYGx9YT5DHurDtDdjAoUpvgMOxgyPpzzqu0baW\nAWdicb471qNhVeBtdzOuofdiO624BsW2s24NOBkE3sG+lMrjOuxm0oPR9h/A2r+SMoXq3fNubXcm\n1gvjaaxNcXSXtn1pVP4aYDF2BpLUdhdg3c+2Ao9jB2KzbV2Lte0+TXLZJrs5kGqQ3ovttOIaFNsi\nIiIiIiIiIpK+2iG5FVOxO8KHxZZlckiuSAO5H24uEkK9Iblg3btWYnelKxV9ZofkitRRiOHmIqHU\nDskF+AFwDtbFqVLRd2O4uUhIWUqlIJKYdvrR1w7JPSta746a5d0Ybi4SUpZSKYgkptPLz72AS4BP\nx5Z1NBx66tSp5Q0bkprWU4QNuE/p5zXcXLEtCXOO7U5Hxu6JDX3+LTZQYwaWb+Mo2hySu2HDBsrl\ncpDHvHnzVJbKGvbAOgm4qgw3B4fh5iFjO63PLy/b7sW/2Se2O63of4WNits/eqwCzoiWZ3pIrkgb\ncjncXKSVVhX9AuAe4CPYkNxjmrz3l9iBsgY7QC4B/i/APookoTa2j8aSZc3CetWcBlwVvVexLbnW\nqo1+XvRo5Nia3/8+enTF4OCgylJZrhrF9okN3t/V2O5ESp9fqtvuxb/ZR22vg24oR+1NIsH19fVB\nOnENim1JkE9sdzNNsdQxMLATfX19dR8DA0lMmiMivUZn9Cmz/9KNPo8+9Fl1Rmf0UlQ6oxcRkYZU\n0YtI5qhJM6x2KvraDH9fxXKAPAP8HJsBpUIZ/oIapWCX3PKprIeG3sCaNEc+7DXpRKuK/gbgFwxv\nF3oCOBgbMLUSm4UerI/9SdHy47HMf8rw5+V9FOySV6qss6NVRX8l8AmGV/QrsDkrwebJrCR3mgn8\nGPsmX8LmMfxksD0VEREnLtkr486hOkxcGf5ERDLIp2nlEmwGnltjy1pm+BMRqdx/ku5wrejPA87G\n2uQrHYfbyvAHMH/+/L88HxwczOWQYsmGUqlEqVRKezekY5X7T43on0BI7XyaU4CfYTdgwaZYOxf4\nHJbWteJTwHysrX4y8GvgAEYmf9KgkphWA6Y0mKozAQZMnY/1LNsBm2bwi8AYYDGwD/A8NvlOvbuJ\niu0Y99hu9Xpvxr5PbLdaaQFwKjANu/H6VeB27BvYFr2njFXoANdiZ/ofYJkAf16nTB0MMarow/Ks\n6CcDjwLTga3ATcCLwEexE5eF2InOgcDlddZXbMeoog8ryYo+CToYYlTRh+VZ0e+JpSz+ONYUeS1W\n4V+GXdEOAQNYF+NpddZXbMeoog9LKRBEwngR+C42GHAhcDhwM8Pnkt1CdS5ZkVxQRS9SNQE4BTgC\neBBrk59JD/cmUyqCYtDIVZGq47Gz+bXR4y3gy8Cb2FyyWxk+l+wIRetRVh3dWu819YxJUsgeZWqj\nT5na6MPybKM/FFiCndG/gbXRD2BNN48Ai4A5wAzgwjrrFy62m8fnaKybZDNqow9FN2NzTBV9WAG6\nV16KncV/APwW62WzI9a9cgqwEetZ9lqddQsX20neUFVF3xlV9Dmmij4sTTwSlir67Ei6101tmuJJ\nwANYG+b9WBqECqUpFhHJGJc0xd8B7gI+BvwEGw0LSlMsIpJJLmmKj8NuWAH8CDg5eq40xSIiGeSS\npjg+eGQz1cEjSlMsIpJBLk0rzQaPtDWwpGh9jVsZGNhJM+okRNkrRVpzyV75ApbErDJ4ZDWwN/B3\nWJPNzdH77ga+D5Rqyitcz4RWfHrWqOdBZ9TrJiz1usmObue6WQ7Mip7PpjrD1DLgzKjM3bHeOqtc\ndkra0XjicA1Pl2JT7Heq3TTF+wJrgK9gQ8QbDR5RmuI6kjqjb3VG1GufM+iMPrSsntH3YuxrwFTG\nqaLvHlX0Yamizw6lKRYRJ82yU2pO1+LQgCaRHtYsO6VRZV8EOqMXESk4VfSF1bhngnolNDUWmyt2\nHdaVeALN8zuJZJ4q+sJ6H7skH/nQ4K2m/hkb1T0NGx+ymcb5nURywacB7nzgq9jo19XAF4ExWNfL\nfYDngbOwCRziCtczoZW0et304oATz143u2HjQg5m+Ie3iYJODt48NiHNnjPqdTNcGr1uJgPfwmbi\n+RjwCjZhg858JM8OwmqQ5Vi67TuwKQQ1Objkmmuvmx2wA2A8lgrhJeBdLLPl5dF7lmBnPpfXK0Ak\ng3YFnsNGfH+AnbjMo4PJwXstj5MkJytzxn4N+DqwFDvD/xusbXN87D2vYWdDcbm7vPWlppvu8Wy6\nOQlrbjwv+v1obIT3dOBARuZ3qpW72FbTTX6k0XQzATgFa7p5EGuTn0kHZz4iGfQoNoFOpRI/GXgM\nWEH9/E6Z0GzQk3pYCbg33RyP5bxZGz3ewiZUfhNr0qmc+bxeb2Vd3koogdMUbwEuBO4BRmMV/7ew\nWF6MXcVW8jtlRrNBT0NDGvAk7pe4h2Jt8EdgvWquxXojTAIeARYBc4AZ2IETl7vL23a0zjmvpptu\n6MVcN62aBpvtk5pu8iOtpGaXYmfxHwC/BS4GdqRxZsuKQlb03W+HV0Vfjyr6Ea+qoi8IZa/MAFX0\n2aCKfsSrqugLQtkrRUSkIWWvFCm0UUo3LKroRYqtkvOoEf0T6AVquhGRgnHP3Np8IpYdcjtXrW7G\nBqKbsdmgm7EjXm3ymu/r+VzX/eZ0ujeBdTNWREQa8qnoNUGDiEgO+FT0PTdBQ7P2OxGRrEpjgobc\nttFnqx1ebfT1qI1+xKtNXvN9PZ/rqo2+fZqgQYpuLvBU9FxNkpJrrv3ovSZoUPZKCSVw9sqKo4Av\nUD19qzRJLsRyOs1HE+pIjqQxQYOabhJ/rfW6ef0OWgnQdLMzcB+WsG8R1hS5iQzPGaumm87WVdNN\n+3I5QUM7euOGq/uAkoLrA27DTlpeiS1Xk6TkmmvTTS4naGhHs0kcijNcvPGw+B6fqOIKLJYfxlJt\nV2jO2MLIT+6frMwZ6yrTTTf5aZ5J6tI33806nk033wdOwD6c0cAewCpgLzI8Z6yabrKzbtGabkSK\n6DJgP2B/bA7kdVgTZe6bJKW3qaIXqS9++jYXq+jXAqcBV6W1UyIu1HRTQ003Pd104yuR2G49HzGo\n6SYb62a16Ub56EUyrnkHAShOJwFJippuREQKLkRFr6HihaI+9iJF41vRNxoqXsjslb2h0sd+5KN1\nO7GIZJFPRb8zcCMwh2oj4XHAkuj5EmzErIiIpMi1otdQcRGRnHCt6ONDxeO3/NseKi4iIt3h2r1y\nCjZU/FyqQ8UfBt7E8tJXhoq/Xm9l5QORUBJKUyxSKCE64O4N/CeWxvVWYCWW3nUOMANLfhaX+oCp\n1gNQsjLwKZ0BU3keTJXXAVPuMQnJxUmSZRdz3awOmApxQEwB7sVy0e+MZa+cQjV75Ws170+9oi/G\n6FdV9PXktaJPLjGZKvpurlvkir5TqugTfy25bab93bWiij7kukmWXcx1s1rRa2SsyHD9WHbK9djA\nv6uj5RoMKLmlil5kpOuAfbHmyFnAIXgOBmw2c1leJsKQ/FJFLzLcNiz/fOX5emAynoMBq4nJGj1E\nkqOKXqSxycAR2HzIGgwouaWKXqS+McCdwDXAZjQYUHJM+ehFRuoHlgL3AT+Mlm1GgwGli7IwOXg/\ndhBMwc50bgP+Abu8XQzsAzwPnAXUjgJR98rEX0tum2l/d60E6F45FrvZugz4dmy512DA5jEH2exO\nmNX9yuq6o7HsryONHz+RLVvqnhu0LY1+9P3AkdhNq36sDfN84HLg18BC4GLgwGhZXOIVfXJTr+Xl\ntaTKTTaQQwhQ0Q9i3Sg3xpbdDXwXj8GAqui1rm+9l4UBU0uBf40eB2M3rQaAJ4BpNe9NvKJP7qDK\ny2vp7E8WzvazOmBKFb3WTbOiD3EzVj0TREQyzPdmrFPPBN2wklCUvVKkNZ9L3H5spOBK4Ppo2QvA\nAVR7JqzGslvGqekm8dfS2R813ajpRut2fn8L2rvHlUbTzVgsY+XDVCt5gOXYkHGA2VjOEBGRHtd4\nLmZIfj5m1zOfQRLomdCJdPJ35+W1NLaZjR45OqMPuW5W96uY67aqF7PQ66YTQSr6dNK65uW1rO1P\n95p1VNGHXDer+1XMdZOs6JUCQUSk4JQCQSSgKVMOSXsXREZQ000hX8va/nSv/T7tpht4ss7i/wE+\nR1abDPK3X0Vct/Ux4hPbOqOXLqj0OBhpaCitOjkp9c7ox3d9LyRvkj1G1EYvIlJwSZzRn4z1rR8N\n3I5ltazr5Zdf5pFHHmlY0PTp05k2rTZVjhTLqKZT6WUlWVqk7dgWKbJxwCZgV2B7bEDVoTXvKVdc\nd9115f7+j5YHBj4/4rHjjoeXR43asfEIAyjDijKU6zxosLzZ6yvaWLfd12r3y6fMXv4b7fVO0Lwh\n1EdbsV3/b9jg+H35fNch1vX/7oq33Xqxn/x2fWM7dNPNDOA3wCtY3pulNJlbs1wu8+67Z7Bly10j\nHm+/fQXvv/82NKznAUoBd11lFaOsxHQU272j1GPbTXvbbkJX9B/GDoSKPwG7Bd6G9BRr2qn3GBjo\nanJUxbbkVug2+jIdzK253XbbscMOP6K/f/WI19577w+8/XbgvZMcykyPnbZie2Dgr0es+Oc/b+Wt\ntxLaK5EUHAf8OPb75cD8mvesp3F7jB56+D7WkwzFth5pP5KK7Y59CEtmtgt2tfAwcHSqeyQShmJb\nJOazwO+BtcA3U94XkZAU2yIiItKbDgN+F/t9EpbLfi1wPzCxzXL6sYlM1kfrXu1Z3h3As8BzWFe5\nsR5lAcwFnvLcJ7C+WxuBZ6LHNR7ljQVuAtZhs39NcCzrkNj+PBOVtwKbE9hlv87HPqu12FSU4xz3\nC+ArwNPAGuDKaJnP5+/iZOzveZZqXCYl9HHgIlSstytUHLsIGavt6KS+/AYWc08BJwXch47dALyK\nTSlYsQi4KHp+MfC9NsvqB46NPX8Sq4BcyxuMPV+MfaGuZR2F9bGu/J2u5YBVoIfVLHMt7xZG3jD0\n2beKi4Abo/I7LWsysAE7YMAO4K877tcx2D/G0dj8xb8CPulYlqt2BlKFFPo46FTIWG9XUnHcSshY\nbUcn9eUx2DSufVg337WknLtsb6r//cEOikqWpwHsv7SLpcAJAcobB/wCGxDjUtbOwGPA4VT/Tp99\nWgF8omaZS3m7Ye3JtX0QffYNLJiewfqVu5S1J/AS1T7o12Jn5S5lXcnwtvILgX90LMvVsdjsahWX\nYWda3RLqOGhH6FhvR1Jx3I6QsdquZvXlhNi2FgCXxt53N/ZPuK5uJDWr/YImAUPR8y3Y5X+nJgNH\nYEHnU94FwB+xs6LHHcrqA27DLmXjg2l89qmMHbzPYmfN2zuWd1BU1vKorDuoXnb6fP7nAr8E/tex\nrBexKSefARZilcbNjmWtAU7ELu37sIpoomNZrtIcSBXqOGhHErHejqTiuB0hY7VdzerLzbFt7Y7F\nWkXTuEsje2XbA6oaGIO1lV2D/eE+5S3CKobJWNNNp2VdATyKXa7HvyCfffoMsA92+b8H1l/bpbxd\nsfsPJwAHAC8D8zz3bXvsQK9MCO9S1gTgFKyCehD7W2c6lnU/1n75BLAKOB47A/ONsU6Uu7y9ipDH\nQTuSiPV2JBHH7QoZq66abav9wanBdqd9m6m2eU0AOklN2I+d7d4H/DBAeWAf1kNYc0mnZU0BzsP+\n4z8ETMMOhDc99mlb9PNt4GfARxz2i+g9W4H3gD8DPwX289y32VilujH63WW/jsc+r7XYdzkX+FuP\n/boO2B8729qIXZ35xkQnXsL61lfsil0lJimJ46CVKYSP9XYkEcftCh2rLhp9r7VxtwtN4i6Nin45\nMCt6PhsLmnaMBe7Fguv62HKX8iZil/xgN/JOBf7boazLsKDbH/tPvw67SbLCYZ/ADuDB2H6dhp1F\nufyNj0b7snf0+8nYJb7rvm2H9fCIp+Z12a8N2ECjSu+Bw7GDyTUuKjF8Anaf5R6Pslyswv6GykCq\n04FlCW4v5HHQidCx3q7QcdyJ0LHqotG2lgFnYvG/O9aBY1WC+9HUAqyr0FasDfxorB31Qey/5ANY\nG1Q7BoF3GN7N7zrH8iZiH+BG7LLwn6LlrvsGdsZTuVvuWs4YrP270r3y257lzcTOcJ/G2hhHe5R1\nJvCTmmWuZV0arbMG6/E0zqOs5Vilcw/VysDne3TRzYFUg4Q7DlxNwT/WOxEyjjsVMlZb6bS+vBa7\nb/E0yqSZBoFeAAAAIklEQVQqIiIiIiIiIiIiIiIiIiIiIiIiIiIiIiIiIr3i/wE+5SFw+hGS4AAA\nAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0xaff2a8cc>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "for i, d in enumerate(distrs, 1):\n",
    "    plt.subplot(2, 2, i)\n",
    "    plt.hist(d, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def insertsort(values):\n",
    "    for i, vi in enumerate(values):\n",
    "        for j, vj in enumerate(values):\n",
    "            if vi < vj:\n",
    "                values[i], values[j] = vj, vi\n",
    "                vi = values[i]\n",
    "    return values\n",
    "\n",
    "def selectsort(values):\n",
    "    result = []\n",
    "    while values:\n",
    "        m = min(enumerate(values), key=lambda x: x[1])\n",
    "        del values[m[0]]\n",
    "        result.append(m[1])\n",
    "    return result\n",
    "\n",
    "def bubblesort(values):\n",
    "    n = len(values)\n",
    "    for i in range(n, 0, -1):\n",
    "        for j in range(n-i-1, 0, -1):\n",
    "            if values[j] > values[j+1]:\n",
    "                values[j], values[j+1] = values[j+1], values[j]\n",
    "    return values\n",
    "\n",
    "def quicksort(values):\n",
    "    if not values:\n",
    "        return values\n",
    "    center = len(values)//2\n",
    "    vcenter = values[center]\n",
    "    left, right = [], []\n",
    "    for i, v in enumerate(values):\n",
    "        if i == center:\n",
    "            continue\n",
    "        if v < vcenter:\n",
    "            left.append(v)\n",
    "        else:\n",
    "            right.append(v)\n",
    "    return quicksort(left)+[vcenter]+quicksort(right)\n",
    "\n",
    "import heapq\n",
    "def heapsort(values):\n",
    "    heapq.heapify(values)\n",
    "    result = []\n",
    "    while values:\n",
    "        result.append(heapq.heappop(values))\n",
    "    return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "sorted:\n",
      "10000 loops, best of 3: 128 µs per loop\n",
      "\n",
      "insertsort:\n",
      "1 loop, best of 3: 493 ms per loop\n",
      "\n",
      "selectsort:\n",
      "1 loop, best of 3: 617 ms per loop\n",
      "\n",
      "bubblesort:\n",
      "1 loop, best of 3: 404 ms per loop\n",
      "\n",
      "quicksort:\n",
      "10 loops, best of 3: 23.7 ms per loop\n",
      "\n",
      "heapsort:\n",
      "100 loops, best of 3: 2.72 ms per loop\n"
     ]
    }
   ],
   "source": [
    "algos = [sorted, insertsort, selectsort, bubblesort, quicksort, heapsort]\n",
    "\n",
    "for f in algos:\n",
    "    for d in distrs:\n",
    "        assert sorted(d) == f(d.copy()), f.__name__ + ' wrong!'\n",
    "\n",
    "for f in algos:\n",
    "    print('\\n'+f.__name__+':')\n",
    "    %timeit [f(d.copy()) for d in distrs]"
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}