QuickSortForExam.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# QuickSort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import statistics\n",
    "import math\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "def randomquicksort(alist,times):\n",
    "    comp = [0]\n",
    "    randomquicksorthelper(alist,0,len(alist)-1,comp)\n",
    "    times.append(comp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def randomquicksorthelper(alist,first,last,comp):\n",
    "    if first<last:\n",
    "        r = randompartition(alist,first,last)\n",
    "        splitpoint = r[0]\n",
    "        tmp = comp.pop()\n",
    "        comp.append(tmp+r[1])\n",
    "        randomquicksorthelper(alist,first,splitpoint-1,comp)\n",
    "        randomquicksorthelper(alist,splitpoint+1,last,comp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def randompartition(alist,first,last):\n",
    "    indxpiv = random.randint(first,last)\n",
    "    temp = alist[indxpiv]\n",
    "    alist[indxpiv] = alist[first]\n",
    "    alist[first] = temp\n",
    "   \n",
    "    pivotvalue = alist[first]\n",
    "    compspart = 0\n",
    "\n",
    "    leftmark = first+1\n",
    "    rightmark = last\n",
    "\n",
    "    done = False\n",
    "    while not done:\n",
    "\n",
    "        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:\n",
    "            leftmark = leftmark + 1\n",
    "            compspart = compspart + 1\n",
    "            compspart = compspart + 1\n",
    "\n",
    "        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:\n",
    "            rightmark = rightmark -1\n",
    "            compspart = compspart + 1\n",
    "            compspart = compspart + 1\n",
    "\n",
    "        if rightmark < leftmark:\n",
    "            done = True\n",
    "        else:\n",
    "            temp = alist[leftmark]\n",
    "            alist[leftmark] = alist[rightmark]\n",
    "            alist[rightmark] = temp\n",
    "    temp = alist[first]\n",
    "    alist[first] = alist[rightmark]\n",
    "    alist[rightmark] = temp\n",
    "    return rightmark,compspart\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def RandomQuickSortTime(s, r):\n",
    "    # Create an array of 1 .. n\n",
    "    n = s\n",
    "    runs = r\n",
    "    x = []\n",
    "    for i in range(1, n + 1):\n",
    "        x.append(n + 1 - i)\n",
    "\n",
    "        # Run quicksort for each permutation\n",
    "    tlist = []\n",
    "    for p in range(1, runs + 1):\n",
    "        y = list(x)\n",
    "        QuickSort(y, tlist)\n",
    "\n",
    "    count = 0\n",
    "    for i in range(len(tlist)):\n",
    "        if (tlist[i] >= 96):\n",
    "            count += 1\n",
    "\n",
    "    plt.hist(tlist, bins='auto', color='black')\n",
    "    plt.title(\"Number of comparison of Quicksort for all permutaions\")\n",
    "    plt.xlabel(\"Comparisons of elements\")\n",
    "    plt.ylabel(\"Frequency\")\n",
    "    plt.show()\n",
    "\n",
    "    print (\"N:\", n)\n",
    "    print (\"Runs:\", runs)\n",
    "    print (\"Promedio teorico:\", 16 * math.log(16) / math.log(2))\n",
    "    print (\"Promedio experimental:\", statistics.mean(tlist))\n",
    "    print (\"Diferencia entre promedio teorico y experimental:\", statistics.mean(tlist) - 16 * math.log(16) / math.log(2))\n",
    "    print (\"Desviacion estandar:\", statistics.stdev(tlist))\n",
    "    print (\"Probabilidad que se demore 1.5 más que el promedio:\", float(count) / float(len(tlist)))\n",
    "    print (\"Min:\", min(tlist))\n",
    "    print (\"Max:\", max(tlist))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAaEAAAEWCAYAAADPZygPAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAIABJREFUeJzt3XucHFWZ//HPl4T7LQQCYhIJQrwAqxECZL0iIARUgqusIEpEJOqCyq6uBPUnN13BGyyrorhkCSjEgApRwRC56iqXQQNJuGwGCBATIJAQAijX5/fHOS2VtrunZ0zPmTDf9+vVr6l+6lTVU9XV/XRVnalWRGBmZlbCOqUTMDOzwctFyMzMinERMjOzYlyEzMysGBchMzMrxkXIzMyKcREaoCSdJ+nLhZYtSf8jaYWkm0rk0AmSrpA0uXQeNZLeJGmhpCckHdyhZSyQtFcb7ULSjp3IoTckbSPpekmrJH2zH5a3SNK+efgkST/s9DIHAknfk/T/SucBLkJtyzvrQ5I2rsQ+Kunagml1ypuBdwCjImKP0smsKRFxQERML51HxSnAtyNik4i4tFEDSR+WNE/SU5IelPRdSZu3u4CI2Dkirl1TCf898rr8todmU4BHgM0i4jP9kNZLQrWYtiMiPh4Rp3Yyp3a5CPXOUODTpZPoLUlDejnJdsCiiHiyE/n0t3xkNxD39e2ABc1GSvoMcDrw78DmwARgDHClpHX7I8E1RdLQNptuB9weffgv+l4so6i1Jc9+ExF+tPEAFgFTgeXAsBz7KHBtHh4DBDC0Ms21wEfz8IeB/wXOAB4D7gHemOMPAA8DkyvTngd8D5gDrAKuA7arjH9NHrccuAv457ppzwYuB54E9m2wPi8HZuXpu4Gjc/wo4C/A88ATwMlNtsfRwB05t9uBXXP8tXm9HyN9wB5Ul9d3gSvyvP8XeBlwJrACuBN4Q902PyHPfwXwP8AGedwWwC+AZXncL0hHbtVt/5W8jD8DO9a9HjvmbbqS9M37x5Vp3wjcnMfdDLyxbr6n5vmuAq4Etmqx3xydt+/yvL1fnuN3Ay/k3J4A1q+bbrMc/+e6+CbVfSVv0y9Xxu8FLK7bhvvm4SHA5/OyVwG3AKPzuAB2zMNvJu2TbwdE2mcfztvjNmCX3G5z4Pz8GtwHfBFYp8H+vhz4CavvV4812FbnAc8Cz+Q2+wLr5/1jSX6cWdtWtXUFjgceBC5oMM8dgKuBR/Pr/CPy+7fB9jkJ+GGT17G2rM/n+SwCDq+MXx/4BnA/8BDpvbthszwrsc/lbbsUOBg4EPi/vM0+X7dtGr7OeX7VfelzOX5xXt5K4Hpg5xbza7ifVvaNjwMLSe+17wDq6X3U9mdrJz+4X0qP2s4K/LT24tH7IvQccCTpw+DLeYf9Tt6B9yN9MGxS2UlWAW/N4/8T+G0etzHpQ+JI0tHZrnkH2Lky7UrgTaSj3Q0arM91pIKwATCO9EGyTyXX37bYFocAfwJ2J31I7Uj6Brtu3pE/D6wH7J3X4dWVvB4BdsvLvRq4Fziisk2uqdvm84HRwHDSh1pt228JvBfYCNiU9Ia7tG7b3w/snLfRunWvx0XAF2rbB3hzjg8nvdE+lKc7LD/fsjLfu4FXARvm56c12U575/XdNb+G/wVcX79PNZl2Iml/Gdpg3HTgR5Vt2m4R+ndgHvDq/Lq9vrJekV/H/Un71h45vj+pWA3L07wW2DaPOx+4LG//MaQPz6Pq9vdP5u24IT3sV03W5xTgBmBrYATwO+DUyro+RzpaXJ/8oV83vx1Jp5bXz9NfD5zZZPucROsi9BzwrTyvt5G+4NX27TNJH97D8/b4OfDVZnlWYl8i7ZtHk96DF+bpdyYV7Vf29nWuxD6S51Ur5HMbbWd63k+D9CVvGPCKnOfEVu+jXn22dvKD+6X04MUitAvpA34EvS9CCyvj/iG336YSexQYV9lJZlTGbUL6FjkaeD/wm7r8vg+cWJn2/BbrMjrPa9NK7KvAeZVcWxWh2cCnG8TfQvrmtU4ldhFwUiWvH1TGfRK4o26bPFZ5vgj4eOX5gcDdTXIaB6yo2/an1LWpvh7nA+dQOXrK8Q8BN9XFfg98uDKPL1bG/QvwqyY5nQt8re41fBYYU92nmkz7QeDBJuNOA66sbNN2i9BdwKQm8wzSUed9wD9U4nuTisuEutd1CPA0sFMl9jFefD98GLi/bhkt96sm63M3cGDl+f6kU8W1dX2GBl+yWsz/YOCPTbbPSfRchDauxGYC/49UnJ8EdqiM+0fg3mZ55tifgSH5+ab5Ndiz0uYW4ODevs5N8h+W5795/fzoeT8NKsUlr/fUVu+j3jwG4nnyAS0i5pO+FUztw+QPVYb/nOdXH9uk8vyBynKfIB0qv5x01LGnpMdqD+Bw0qmtv5m2gZcDyyNiVSV2HzCyzfUYTfpwaDTfByLihRbzrV/fVusPq6/HfXkZSNpI0vcl3SfpcdI33GF1179abYPPkT48bso9yD5SWYf76trWr8ODleGnGuRcs9q88mv4KO1t50eArZpcP9iW9G20t5q9bjXHATMjYl4tEBFXA98mHbE/JOkcSZsBW5GOdqvbqn47tdr+7ap/Pf66D2TLIuIvzSaWtLWkGZL+lPeTH5Jy74sVsfp10louI0hH5LdU3o+/yvFWeT4aEc/n4T/nvz29H9oiaYik0yTdndd7UR7VaN3b2U+b7fPN3kdtcxHqmxNJh8/VF6m2c25UiVWLQl+Mrg1I2oR0qL+E9Oa+LiKGVR6bRMQnKtNGi/kuAYZL2rQSewXpFFs7HiCda28039F1nQB6M99GRleGX5GXAfAZ0mmlPSNiM9JpS0hviJqm2yAiHoyIoyPi5aRv8N/NXZSXkIp8VV/XYbV55Z6VW7Y5r9+TjjT+qRrM8ziAdDoV0n7X7j7X7HWrOQQ4WNJx1WBEnBURu5FOEb2KdFrvEdK35eq2qt9O9du/1T7ZTP3rUd0H2pnnV3Ob1+X95IOsvo/0xhbV3rGVXB4hFYydK+/HzSOiWkD6su5VPb3O9fP/ADCJdPZmc9KZGmi87n3eT1u8j9rmItQHEdEN/Bj4VCW2jPSifTB/C/kIrd/w7ThQ0pslrUe6GH5jRDxAOhJ7laQPSVo3P3aX9No283+AdG79q5I2kPQ6UoeEH7WZ138Dn5W0W+55tqOk7YAbSW+Wz+Wc9gLeDczozUrXOUbSKEnDSdeafpzjm5Le+I/lcSf2ZqaSDpE0Kj9dQXoTP0/qzPEqSR+QNFTS+4GdSNu8ty4EjpQ0TtL6wH+QXsNFPU0YESuBk4H/kjQxb88xpGtftQvsAHNJ+8lwSS8jHc0089/AqZLG5tftdZK2rIxfAuwDfErSvwDk/WrP3BvvSXLngvwNfibwFUmb5tf/30hHGs08BIzK+3O7LgK+KGmEpK1I11B68788m5I7QkgaSSqgf4+TJa0n6S3Au4CL85H/D4AzJG0NIGmkpP3/zmVV9fQ6PwS8svJ8U9KXmEdJxes/Wsy7z/tpi/dR21yE+u4UUgeBqqNJO/mjpG+Nv/s7l3Eh6cN1Oeli/uEA+TTafsChpA+OB3nxome7DiN9O1oC/Ix0PWlOOxNGxMWknmcXkjoeXAoMj4hngINI39QfIXV8OCIi7uxFXvUuJPVAuyc/av/AeybpAu8jpAvXv+rlfHcHbpT0BOmC8qcj4t6IeJT04fIZ0uv4OeBdEfFIbxOPiKtI1wx+Qur9tAPpNWt3+q+RCu83SNv5XtIHyr6V00IXALeSTrdcyYtFupFvkQrHlcDjpGsBG9Yt835SITpe0kdJvfR+QPqAuY+0Tb6Rm3+SVJjuAX5Leq2mtVj+1aQekw9Kand7fhnoIvXKmwf8gRf3gXacTLrgvhL4JaljUV89SNoOS0hfAj5e2bePJ3XKuSGf/vo16Uh9Tenpdf4qqVg/JumzpGs195G+GN9Oeo809Hfupw3fR21OC7zYzc5swJG0iNSR4NelcxkI8tH1ycCbcrGwfpKP6n8YEaN6amu943+aMltLRMQ0Sc+S/o/JRcheElyEzNYiEXFB6RzM1iSfjjMzs2LcMcHMzIrx6bgebLXVVjFmzJjSaZiZrVVuueWWRyJiRE/tXIR6MGbMGLq6ukqnYWa2VpFUf+eRhnw6zszMinERMjOzYlyEzMysGBchMzMrxkXIzMyKcREyM7NiXITMzKwYFyEzMyvGRcjMzIrxHRNsjRoz9ZfFlr3otHcWW7aZ9Y2PhMzMrBgXITMzK8ZFyMzMinERMjOzYtwx4SWqZAcBM7N2+UjIzMyKcREyM7NiXITMzKwYFyEzMyvGRcjMzIpxETIzs2I6VoQkbSDpJkm3Slog6eQcP0/SvZLm5se4HJeksyR1S7pN0q6VeU2WtDA/Jlfiu0mal6c5S5JyfLikObn9HElb9LQMMzPrf508Enoa2DsiXg+MAyZKmpDH/XtEjMuPuTl2ADA2P6YAZ0MqKMCJwJ7AHsCJtaKS20ypTDcxx6cCV0XEWOCq/LzpMszMrIyOFaFInshP182PaDHJJOD8PN0NwDBJ2wL7A3MiYnlErADmkAratsBmEfH7iAjgfODgyrym5+HpdfFGyzAzswI6ek1I0hBJc4GHSYXkxjzqK/l02BmS1s+xkcADlckX51ir+OIGcYBtImIpQP67dQ/LqM97iqQuSV3Lli3r1TqbmVn7OlqEIuL5iBgHjAL2kLQLcALwGmB3YDhwfG6uRrPoQ7yVtqaJiHMiYnxEjB8xYkQPszQzs77ql95xEfEYcC0wMSKW5tNhTwP/Q7rOA+moZHRlslHAkh7ioxrEAR6qnWbLfx/uYRlmZlZAJ3vHjZA0LA9vCOwL3FkpDiJdq5mfJ5kFHJF7sE0AVuZTabOB/SRtkTsk7AfMzuNWSZqQ53UEcFllXrVedJPr4o2WYWZmBXTyLtrbAtMlDSEVu5kR8QtJV0saQTo1Nhf4eG5/OXAg0A08BRwJEBHLJZ0K3JzbnRIRy/PwJ4DzgA2BK/ID4DRgpqSjgPuBQ1otw8zMyuhYEYqI24A3NIjv3aR9AMc0GTcNmNYg3gXs0iD+KLBPb5ZhZmb9z3dMMDOzYlyEzMysGBchMzMrxkXIzMyKcREyM7NiXITMzKwYFyEzMyvGRcjMzIpxETIzs2JchMzMrBgXITMzK8ZFyMzMinERMjOzYlyEzMysGBchMzMrxkXIzMyKcREyM7NiXITMzKyYjhUhSRtIuknSrZIWSDo5x7eXdKOkhZJ+LGm9HF8/P+/O48dU5nVCjt8laf9KfGKOdUuaWon3ehlmZtb/Onkk9DSwd0S8HhgHTJQ0ATgdOCMixgIrgKNy+6OAFRGxI3BGboeknYBDgZ2BicB3JQ2RNAT4DnAAsBNwWG5Lb5dhZmZldKwIRfJEfrpufgSwN3BJjk8HDs7Dk/Jz8vh9JCnHZ0TE0xFxL9AN7JEf3RFxT0Q8A8wAJuVpersMMzMroKPXhPIRy1zgYWAOcDfwWEQ8l5ssBkbm4ZHAAwB5/Epgy2q8bppm8S37sAwzMyugo0UoIp6PiHHAKNKRy2sbNct/Gx2RxBqMt1rGaiRNkdQlqWvZsmUNJjEzszWhX3rHRcRjwLXABGCYpKF51ChgSR5eDIwGyOM3B5ZX43XTNIs/0odl1Od7TkSMj4jxI0aM6NtKm5lZjzrZO26EpGF5eENgX+AO4BrgfbnZZOCyPDwrPyePvzoiIscPzT3btgfGAjcBNwNjc0+49UidF2blaXq7DDMzK2Boz036bFtgeu7Ftg4wMyJ+Iel2YIakLwN/BM7N7c8FLpDUTTo6ORQgIhZImgncDjwHHBMRzwNIOhaYDQwBpkXEgjyv43uzDDMzK6NjRSgibgPe0CB+D+n6UH38L8AhTeb1FeArDeKXA5eviWWYmVn/8x0TzMysGBchMzMrxkXIzMyKcREyM7NiXITMzKwYFyEzMyvGRcjMzIpxETIzs2JchMzMrBgXITMzK8ZFyMzMinERMjOzYlyEzMysGBchMzMrxkXIzMyKcREyM7NiXITMzKwYFyEzMyvGRcjMzIrpWBGSNFrSNZLukLRA0qdz/CRJf5I0Nz8OrExzgqRuSXdJ2r8Sn5hj3ZKmVuLbS7pR0kJJP5a0Xo6vn5935/FjelqGmZn1v04eCT0HfCYiXgtMAI6RtFMed0ZEjMuPywHyuEOBnYGJwHclDZE0BPgOcACwE3BYZT6n53mNBVYAR+X4UcCKiNgROCO3a7qMzm0CMzNrpWNFKCKWRsQf8vAq4A5gZItJJgEzIuLpiLgX6Ab2yI/uiLgnIp4BZgCTJAnYG7gkTz8dOLgyr+l5+BJgn9y+2TLMzKyAfrkmlE+HvQG4MYeOlXSbpGmStsixkcADlckW51iz+JbAYxHxXF18tXnl8Stz+2bzqs93iqQuSV3Lli3r9fqamVl7Ol6EJG0C/AQ4LiIeB84GdgDGAUuBb9aaNpg8+hDvy7xWD0ScExHjI2L8iBEjGkxiZmZrQkeLkKR1SQXoRxHxU4CIeCgino+IF4Af8OLpsMXA6Mrko4AlLeKPAMMkDa2LrzavPH5zYHmLeZmZWQGd7B0n4Fzgjoj4ViW+baXZe4D5eXgWcGju2bY9MBa4CbgZGJt7wq1H6lgwKyICuAZ4X55+MnBZZV6T8/D7gKtz+2bLMDOzAob23AQk7RIR83tuuZo3AR8C5kmam2OfJ/VuG0c6DbYI+BhARCyQNBO4ndSz7piIeD4v/1hgNjAEmBYRC/L8jgdmSPoy8EdS0SP/vUBSN+kI6NCelmFmZv1P6QChh0bSb4H1gPOACyPisQ7nNWCMHz8+urq6SqfRa2Om/rJ0Cv1u0WnvLJ2CmWWSbomI8T21a+t0XES8GTicdD2lS9KFkt7xd+ZoZmaDXNvXhCJiIfBF0imwtwFnSbpT0j91KjkzM3tpa6sISXqdpDNI/3C6N/DufCeEvUl3JDAzM+u1tjomAN8mdaf+fET8uRaMiCWSvtiRzMzM7CWv3SJ0IPDnSm+1dYANIuKpiLigY9mZmdlLWrvXhH4NbFh5vlGOmZmZ9Vm7RWiDiHii9iQPb9SZlMzMbLBotwg9KWnX2hNJuwF/btHezMysR+1eEzoOuFhS7T5r2wLv70xKZmY2WLRVhCLiZkmvAV5NuhP1nRHxbEczMzOzl7x2j4QAdgfG5GneIImIOL8jWZmZ2aDQ7g1MLyD9BtBcoHbDzwBchMzMrM/aPRIaD+wU7dzt1MzMrE3t9o6bD7ysk4mYmdng0+6R0FbA7ZJuAp6uBSPioI5kZWZmg0K7ReikTiZhZmaDU7tdtK+TtB0wNiJ+LWkj0q+cmpmZ9Vm7P+VwNHAJ8P0cGglc2qmkzMxscGi3Y8IxwJuAx+GvP3C3dasJJI2WdI2kOyQtkPTpHB8uaY6khfnvFjkuSWdJ6pZ0W91tgibn9gslTa7Ed5M0L09zliT1dRlmZtb/2i1CT0fEM7UnkoaS/k+oleeAz+Qfv5sAHCNpJ2AqcFVEjAWuys8BDgDG5scU4Oy8rOHAicCewB7AibWikttMqUw3Mcd7tQwzMyuj3SJ0naTPAxtKegdwMfDzVhNExNKI+EMeXkX6VdaRwCRgem42HTg4D08Czo/kBmCYpG2B/YE5EbE8IlYAc4CJedxmEfH7/P9L59fNqzfLMDOzAtotQlOBZcA84GPA5UDbv6gqaQzwBuBGYJuIWAqpUPHiab2RwAOVyRbnWKv44gZx+rCM+nynSOqS1LVs2bJ2V9PMzHqp3d5xL5B+3vsHvV2ApE2AnwDHRcTj+bJNw6aNFt2HeMt02pkmIs4BzgEYP3687xJhZtYh7d477l4af1i/sofp1iUVoB9FxE9z+CFJ20bE0nwq7OEcXwyMrkw+CliS43vVxa/N8VEN2vdlGWZmVkC7p+PGk+6ivTvwFuAs4IetJsg91c4F7oiIb1VGzQJqPdwmA5dV4kfkHmwTgJX5VNpsYD9JW+QOCfsBs/O4VZIm5GUdUTev3izDzMwKaPd03KN1oTMl/Rb4UovJ3gR8CJgnaW6OfR44DZgp6SjgfuCQPO5y4ECgG3gKODIve7mkU4Gbc7tTImJ5Hv4EcB6wIXBFftDbZZiZWRntno6r/j/NOqQjo01bTRMRv6XxNRiAfRq0D9L/IzWa1zRgWoN4F7BLg/ijvV2GmZn1v3bvHffNyvBzwCLgn9d4NmZmNqi0ezru7Z1OxMzMBp92T8f9W6vxdR0PzMzM2tKbX1bdndS7DODdwPWs/o+fZmZmvdKbH7XbNd9+B0knARdHxEc7lZiZmb30tft/Qq8Anqk8fwYYs8azMTOzQaXdI6ELgJsk/Yx054T3kG4YamZm1mft9o77iqQrSHdLADgyIv7YubTMzGwwaPd0HMBGwOMR8Z/AYknbdygnMzMbJNr9ee8TgeOBE3JoXXq4d5yZmVlP2j0Seg9wEPAkQEQsoYfb9piZmfWk3SL0TL7vWgBI2rhzKZmZ2WDRbhGaKen7pJ/DPhr4NX34gTszM7OqdnvHfUPSO4DHgVcDX4qIOR3NzMzMXvJ6LEKShpB+RG5fwIXHzMzWmB5Px0XE88BTkjbvh3zMzGwQafeOCX8h/ULqHHIPOYCI+FRHsjIzs0Gh3SL0y/wwMzNbY1oWIUmviIj7I2J6fyVkZmaDR0/XhC6tDUj6SW9mLGmapIclza/ETpL0J0lz8+PAyrgTJHVLukvS/pX4xBzrljS1Et9e0o2SFkr6saT1cnz9/Lw7jx/T0zLMzKyMnoqQKsOv7OW8zwMmNoifERHj8uNyAEk7AYcCO+dpvitpSO6Z9x3gAGAn4LDcFuD0PK+xwArgqBw/ClgRETsCZ+R2TZfRy3UyM7M1qKciFE2GexQR1wPL22w+CZgREU9HxL1AN7BHfnRHxD0R8QwwA5gkScDewCV5+unAwZV51U4fXgLsk9s3W4aZmRXSUxF6vaTHJa0CXpeHH5e0StLjfVzmsZJuy6frtsixkaz+U+GLc6xZfEvgsYh4ri6+2rzy+JW5fbN5/Q1JUyR1SepatmxZ39bSzMx61LIIRcSQiNgsIjaNiKF5uPZ8sz4s72xgB2AcsBT4Zo6rQdvoQ7wv8/rbYMQ5ETE+IsaPGDGiURMzM1sDevN7Qn+3iHgoIp6PiBdI956rnQ5bDIyuNB0FLGkRf4R0H7uhdfHV5pXHb046LdhsXmZmVki/FiFJ21aevgeo9ZybBRyae7ZtD4wFbgJuBsbmnnDrkToWzMp39L4GeF+efjJwWWVek/Pw+4Crc/tmyzAzs0La/WfVXpN0EbAXsJWkxcCJwF6SxpFOgy0CPgYQEQskzQRuB54Djsm3C0LSscBsYAgwLSIW5EUcD8yQ9GXgj8C5OX4ucIGkbtIR0KE9LcPMzMpQOkiwZsaPHx9dXV2l0+i1MVMH3w0uFp32ztIpmFkm6ZaIGN9Tu349HWdmZlbVsdNxZv2t1NGfj8DM+s5HQmZmVoyLkJmZFeMiZGZmxbgImZlZMS5CZmZWjIuQmZkV4yJkZmbFuAiZmVkxLkJmZlaMi5CZmRXjImRmZsW4CJmZWTEuQmZmVoyLkJmZFeMiZGZmxbgImZlZMR0rQpKmSXpY0vxKbLikOZIW5r9b5LgknSWpW9JtknatTDM5t18oaXIlvpukeXmasySpr8swM7MyOnkkdB4wsS42FbgqIsYCV+XnAAcAY/NjCnA2pIICnAjsCewBnFgrKrnNlMp0E/uyDDMzK6djRSgirgeW14UnAdPz8HTg4Er8/EhuAIZJ2hbYH5gTEcsjYgUwB5iYx20WEb+PiADOr5tXb5ZhZmaF9Pc1oW0iYilA/rt1jo8EHqi0W5xjreKLG8T7soy/IWmKpC5JXcuWLevVCpqZWfsGSscENYhFH+J9WcbfBiPOiYjxETF+xIgRPczWzMz6qr+L0EO1U2D578M5vhgYXWk3CljSQ3xUg3hflmFmZoX0dxGaBdR6uE0GLqvEj8g92CYAK/OptNnAfpK2yB0S9gNm53GrJE3IveKOqJtXb5ZhZmaFDO3UjCVdBOwFbCVpMamX22nATElHAfcDh+TmlwMHAt3AU8CRABGxXNKpwM253SkRUevs8AlSD7wNgSvyg94uw8zMyulYEYqIw5qM2qdB2wCOaTKfacC0BvEuYJcG8Ud7uwwzMytjoHRMMDOzQchFyMzMinERMjOzYlyEzMysGBchMzMrxkXIzMyKcREyM7NiXITMzKwYFyEzMyvGRcjMzIpxETIzs2JchMzMrBgXITMzK8ZFyMzMiunYTzkYjJn6y9IpmJkNaD4SMjOzYlyEzMysGBchMzMrpkgRkrRI0jxJcyV15dhwSXMkLcx/t8hxSTpLUrek2yTtWpnP5Nx+oaTJlfhuef7deVq1WoaZmZVR8kjo7RExLiLG5+dTgasiYixwVX4OcAAwNj+mAGdDKijAicCewB7AiZWicnZuW5tuYg/LMDOzAgbS6bhJwPQ8PB04uBI/P5IbgGGStgX2B+ZExPKIWAHMASbmcZtFxO8jIoDz6+bVaBlmZlZAqSIUwJWSbpE0Jce2iYilAPnv1jk+EnigMu3iHGsVX9wg3moZq5E0RVKXpK5ly5b1cRXNzKwnpf5P6E0RsUTS1sAcSXe2aKsGsehDvG0RcQ5wDsD48eN7Na2ZmbWvyJFQRCzJfx8Gfka6pvNQPpVG/vtwbr4YGF2ZfBSwpIf4qAZxWizDzMwK6PciJGljSZvWhoH9gPnALKDWw20ycFkengUckXvJTQBW5lNps4H9JG2ROyTsB8zO41ZJmpB7xR1RN69GyzAzswJKnI7bBvhZ7jU9FLgwIn4l6WZgpqSjgPuBQ3L7y4EDgW7gKeBIgIhYLulU4Obc7pSIWJ6HPwGcB2wIXJEfAKc1WYZZn5W8PdOi095ZbNlma0K/F6GIuAd4fYP4o8A+DeIBHNNkXtOAaQ3iXcAu7S7DzMzKGEhdtM3MbJBxETIzs2JchMzMrBgXITMzK8ZFyMzMinERMjOzYlyEzMysGBchMzMrxkXIzMyKcREyM7NiXITMzKwYFyEzMyvGRcjMzIpxETIzs2JchMzMrBgXITMzK8ZFyMxYF1G9AAAKAElEQVTMiinx895mtoaU+mlx/6y4rSk+EjIzs2IGZRGSNFHSXZK6JU0tnY+Z2WA16IqQpCHAd4ADgJ2AwyTtVDYrM7PBaTBeE9oD6I6IewAkzQAmAbcXzcpsLeJrUbamDMYiNBJ4oPJ8MbBntYGkKcCU/PQJSXf1U24AWwGP9OPyemug5wcDP8eBnh8M0Bx1+mpPB2SOFQM9P+hsjtu102gwFiE1iMVqTyLOAc7pn3RWJ6krIsaXWHY7Bnp+MPBzHOj5gXNcEwZ6fjAwchx014RIRz6jK89HAUsK5WJmNqgNxiJ0MzBW0vaS1gMOBWYVzsnMbFAadKfjIuI5SccCs4EhwLSIWFA4raoipwF7YaDnBwM/x4GeHzjHNWGg5wcDIEdFRM+tzMzMOmAwno4zM7MBwkXIzMyKcREqRNKrJc2tPB6XdJyk4ZLmSFqY/25ROM9/lbRA0nxJF0naIHfquDHn+OPcwaNUfp/OuS2QdFyOFd2GkqZJeljS/EqsYU5Kzsq3kLpN0q4Fczwkb8cXJI2va39CzvEuSfsXyu/rku7M2+lnkoaVyq9Fjqfm/OZKulLSy3O831/nRvlVxn1WUkjaqlR+fxURfhR+kDpIPEj6566vAVNzfCpwesG8RgL3Ahvm5zOBD+e/h+bY94BPFMpvF2A+sBGpk82vgbGltyHwVmBXYH4l1jAn4EDgCtL/r00AbiyY42uBVwPXAuMr8Z2AW4H1ge2Bu4EhBfLbDxiah0+vbMN+z69FjptVhj8FfK/U69wovxwfTeqYdR+wVcn9MCJ8JDRA7APcHRH3kW4hND3HpwMHF8sqGQpsKGko6cN+KbA3cEkeXzLH1wI3RMRTEfEccB3wHgpvw4i4HlheF26W0yTg/EhuAIZJ2rZEjhFxR0Q0ujvIJGBGRDwdEfcC3aTbX/V3flfm1xngBtL/+BXJr0WOj1eebsyL/wjf769zk/0Q4Azgc6z+T/pF9kPw6biB4lDgojy8TUQsBch/ty6VVET8CfgGcD+p+KwEbgEeq3wYLCYdMZUwH3irpC0lbUT6NjeaAbQNK5rl1Og2UqW2ZzMDMcePkL65wwDLT9JXJD0AHA58KYcHRI6SDgL+FBG31o0qlp+LUGH5espBwMWlc6mXr1tMIp3ieDnpm90BDZoW6ecfEXeQTsvMAX5FOiXzXMuJBp4ebyM1AAyoHCV9gfQ6/6gWatCsWH4R8YWIGE3K79gcLp5j/qL2BV4sjKuNbhDrl/xchMo7APhDRDyUnz9UOwzOfx8ulhnsC9wbEcsi4lngp8AbSYfqtX90Lnrbo4g4NyJ2jYi3kk49LGRgbcOaZjmtDbeRGjA5SpoMvAs4PPLFDAZQfnUuBN6bhwdCjjuQvlDeKmlRzuEPkl5WMj8XofIO48VTcZBuITQ5D08GLuv3jF50PzBB0kaSRLp2dTtwDfC+3KZojpK2zn9fAfwTaVsOpG1Y0yynWcARuXfSBGBl7bTdADILOFTS+pK2J3X+uKm/k5A0ETgeOCginhpo+eUcx1aeHgTcmYeLv84RMS8ito6IMRExhlR4do2IB4vm1189IPxo2HtlI+BRYPNKbEvgKtI3+quA4YVzPJn0RpoPXEDqgfRK0pu8m3Qacf2C+f2GVBhvBfYZCNuQVAiXAs+S3uhHNcuJdBrkO6QeXfOo9EorkON78vDTwEPA7Er7L+Qc7wIOKJRfN+m6xdz8+F6p/Frk+JP8XrkN+DkwstTr3Ci/uvGLeLF3XJH9MCJ82x4zMyvHp+PMzKwYFyEzMyvGRcjMzIpxETIzs2JchMzMrBgXIVvrSXqZpBmS7pZ0u6TLJb2qdF4Akn5XOoeafBfqBZK+3mb7vST9otN5NVn2GEkfKLFs61+D7ue97aUl/xPtz4DpEXFojo0DtgH+r2BeQyLi+Yh4Y6kcGvgYMCIini6dSBvGAB8g3XXAXsJ8JGRru7cDz0bE92qBiJgbEb/J//39daXfG5on6f3w12/410maKen/JJ0m6XBJN+V2O+R250n6nqTf5HbvyvExOfaH/HhjZb7XSLqQ9A9/SHoi/91W0vX5d2bmS3pLjh+Wlzlf0um1dZD0RL4R5q2SbpC0TY4fktveKun6+o3RYp1nke79d2MtVplmY6XfnrlZ0h8lTWow34ZtJH1Y0qWSfi7pXknHSvq33OYGScNzux0k/UrSLXnbvaayjc+S9DtJ90iq3YnjNOAteXv9q6Sd8+szV+n3bsbW52hrqf76r1g//OjEg/SbLWc0Gfde0s1Nh5COjO4HtgX2Ah7Lw+sDfwJOztN8GjgzD59HujHqOqRbwSwGNiDd6WKD3GYs0JWH9wKeBLav5PBE/vsZ4At5eAiwKemmsPcDI0hnJa4GDs5tAnh3Hv4a8MU8PI8X/wt/WLvrXM2lwTT/AXywNk/SEeTGeX1+0UObD5PuZLBpXo+VwMdzuzOA4/LwVcDYPLwncHVlG1+ct/FOQHdlW/6ikuN/ke4XB7Ae+Teu/Fj7Hz4dZy9lbwYuiojnSTcQvQ7YHXgcuDnyvbEk3Q1cmaeZRzq6qpkZES8ACyXdA7yG9EN/386n/Z4Hqtefbor0mzb1bgamSVoXuDQi5kraG7g2IpblPH5E+iGyS4FngNr1mFuAd+Th/wXOkzSTdEPZdtd5VovttB9wkKTP5ucbAK/oRZtrImIVsErSStLtaiBty9dJ2oR049uL09lTIBX/mkvzNr69dsTXwO+BL0gaBfw0Iha2WB9bi7gI2dpuAS/eTLVeo9vT11Svi7xQef4Cq78v6u9rFcC/ku6t9nrSN/i/VMY/2WhhEXG9pLcC7wQuyJ0DHm/UNns28td+UqEbmufzcUl75vnMlTQuIh6tTNdqnZsR8N6o+0G7uoLQrM2e9Lwt1yH9BtW4JsuvTt8w/4i4UNKNpPWeLemjEXF169WytYGvCdna7mpgfUlH1wKSdpf0NuB64P2ShkgaQTrK6O3dlQ+RtE6+TvRK0g0yNweW5m/vHyKd+mpJ0nbAwxHxA+Bc0s8u3wi8TdJWkoaQ7qh+XQ/z2SEiboyILwGPsPrt96Fv6zwb+KTyYYqkN/SxTUORfm30XkmH5Gkl6fU9TLaKdIqPPM0rgXsi4izSUd3r2l2+DWw+ErK1WkSEpPcAZ0qaSjoqWQQcR/pA/kfSHbYD+FxEPFi7KN6mu0iFYRvStY6/SPou8JP8oXoNTY5+6uwF/LukZ4EngCMiYqmkE/I8BFweET397MTX80V5ka6z1P9C5s9osM49zPNU4EzgtlxkFpF+s6e3bVo5HDhb0heBdYEZDXKvug14TtKtpOtGGwAfzNvvQeCUXizbBjDfRdusCUnnkS6OX1I6F7OXKp+OMzOzYnwkZGZmxfhIyMzMinERMjOzYlyEzMysGBchMzMrxkXIzMyK+f9B2UdsBl+eqQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x17e9ac10>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N: 16\n",
      "Runs: 10000000\n",
      "Promedio teorico: 64.0\n",
      "Promedio experimental: 83.6645058\n",
      "Diferencia entre promedio teorico y experimental: 19.6645058\n",
      "Desviacion estandar: 7.09159948607\n",
      "Probabilidad que se demore 1.5 más que el promedio: 0.0658262\n",
      "Min: 67\n",
      "Max: 142\n"
     ]
    }
   ],
   "source": [
    "RandomQuickSortTime(16,10000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Pruebas            Tiempo \n",
    "10000000           11.38 minutos\n",
    "263620386,6432     5 horas\n"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}