bogo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from random import choices\n",
    "from collections import Counter\n",
    "import numpy as np\n",
    "from math import factorial\n",
    "from random import shuffle\n",
    "\n",
    "plt.style.use('_mpl-gallery')\n",
    "\n",
    "TRIALS = 50\n",
    "MAX_LENGTH = 8\n",
    "\n",
    "def bogosort(data):\n",
    "    i = 1\n",
    "    while not all(a <= b for a, b in zip(data, data[1:])):\n",
    "        shuffle(data)\n",
    "        i+=1\n",
    "    return data, i\n",
    "\n",
    "\n",
    "y = {}\n",
    "\n",
    "for length in range(2,MAX_LENGTH+1):\n",
    "    y[str(length)] = []\n",
    "    for j in range(TRIALS):\n",
    "        array = []\n",
    "        for n in range(length):\n",
    "            array.append(n+1)\n",
    "\n",
    "        shuffle(array)\n",
    "\n",
    "        sorted, iters = bogosort(array)\n",
    "        y[str(length)].append(iters)\n",
    "\n",
    "x = list(map(lambda x: int(x), y.keys()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "\n",
    "ratio = 16/9\n",
    "size = 5\n",
    "fig.set_size_inches(size*ratio, size)\n",
    "fig.set_dpi(300)\n",
    "\n",
    "point_x = []\n",
    "point_y = []\n",
    "point_avg = []\n",
    "theoretical = []\n",
    "\n",
    "for i in y:\n",
    "    sum = 0\n",
    "    for j in y[i]:\n",
    "        point_x.append(int(i))\n",
    "        point_y.append(j)\n",
    "        sum+=j\n",
    "    point_avg.append(sum/len(y[i]))\n",
    "for n in x:\n",
    "    theoretical.append(factorial(n))\n",
    "\n",
    "ax.scatter(point_x, point_y)\n",
    "\n",
    "ax.plot(x, point_avg, color=\"orange\", label='Average experimental performance')\n",
    "\n",
    "ax.plot(x, theoretical, color=\"red\", label=\"Theoretical average case performance\")\n",
    "\n",
    "plt.semilogy(base=10)\n",
    "\n",
    "ax.legend()\n",
    "\n",
    "ax.set_xlabel(\"Array length\")\n",
    "ax.set_ylabel(\"Comparisons\")\n",
    "\n",
    "plt.show()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.10 64-bit",
   "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.8.10"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}