Sorting Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.animation as animation\n",
    "from IPython.display import HTML"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class randomNos:\n",
    "    def __init__(self,size,min_num = 1,max_num = 1000):\n",
    "        self.min_num = min_num\n",
    "        self.max_num = max_num\n",
    "        self.size = size\n",
    "        self.frames = []\n",
    "        self.colors = []\n",
    "        self.index = np.arange(size) \n",
    "        self.base_colors = ['gray']*self.size\n",
    "        \n",
    "    def generate(self):\n",
    "        '''\n",
    "        Generate random integers from min_num to max_num and assign it to rand_list\n",
    "        '''\n",
    "        self.rand_list = random.sample(range(self.min_num,self.max_num), self.size)\n",
    "        \n",
    "    def visualize(self):\n",
    "        '''\n",
    "        Create a bar plot of rand_list\n",
    "        '''\n",
    "        plt.bar(self.index, self.rand_list,color=self.base_colors)\n",
    "        plt.xticks([])\n",
    "        plt.show()\n",
    "        \n",
    "    def saveVideo(self,filename = 'bar'):\n",
    "        '''\n",
    "        Processes data and converts it into video\n",
    "        '''\n",
    "        fig = plt.figure(figsize=(8, 4))\n",
    "        plt.xticks([])\n",
    "        rects = plt.bar(self.index, self.frames[0],color=self.colors[0])\n",
    "        \n",
    "        def animate(i):\n",
    "            for rect, yi,c in zip(rects, self.frames[i],self.colors[i]):\n",
    "                rect.set_height(yi)\n",
    "                rect.set_color(c)\n",
    "            return rects\n",
    "\n",
    "        anim = animation.FuncAnimation(fig, animate, frames=len(x.frames), interval=250)\n",
    "        anim.save(filename + '.mp4', writer='pillow')\n",
    "    \n",
    "    def plot(self):\n",
    "        HTML(\"\"\"<video alt=\"test\" controls>\n",
    "                <source src=\"bar.mp4\" type=\"video/mp4\">\n",
    "                </video>\"\"\")\n",
    "            \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Buble Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bubbleSort(randomNos):\n",
    "    randomNos.frames.append(randomNos.rand_list.copy())\n",
    "    randomNos.colors.append(randomNos.base_colors.copy())\n",
    "\n",
    "    for i in range(0,randomNos.size):\n",
    "        for j in range(0,randomNos.size-1-i):\n",
    "\n",
    "            if randomNos.rand_list[j]>randomNos.rand_list[j+1]:\n",
    "\n",
    "                randomNos.rand_list[j+1],randomNos.rand_list[j] = randomNos.rand_list[j],randomNos.rand_list[j+1]\n",
    "                \n",
    "                colors_iter = randomNos.base_colors.copy()\n",
    "                colors_iter[j] = 'red'\n",
    "                colors_iter[j+1] = 'red'\n",
    "                randomNos.colors.append(colors_iter.copy())\n",
    "\n",
    "            else:\n",
    "                colors_iter = randomNos.base_colors.copy()\n",
    "                colors_iter[j] = 'green'\n",
    "                colors_iter[j+1] = 'green'\n",
    "                randomNos.colors.append(colors_iter.copy())\n",
    "\n",
    "            randomNos.frames.append(randomNos.rand_list.copy())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = randomNos(15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x.generate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[856, 571, 931, 500, 241, 125, 320, 824, 57, 503, 768, 168, 371, 361, 921]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.rand_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "bubbleSort(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\nickj\\AppData\\Local\\Continuum\\Anaconda3\\envs\\py35\\lib\\site-packages\\matplotlib\\animation.py:1021: UserWarning: MovieWriter pillow unavailable\n",
      "  warnings.warn(\"MovieWriter %s unavailable\" % writer)\n"
     ]
    }
   ],
   "source": [
    "x.saveVideo('bubble_sort')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<video alt=\"test\" controls>\n",
       "        <source src=\"bubble_sort.mp4\" type=\"video/mp4\">\n",
       "        </video>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HTML(\"\"\"<video alt=\"test\" controls>\n",
    "        <source src=\"bubble_sort.mp4\" type=\"video/mp4\">\n",
    "        </video>\"\"\")\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Insertion Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insertionSort(randomNos):\n",
    "    randomNos.frames.append(randomNos.rand_list.copy())\n",
    "    randomNos.colors.append(randomNos.base_colors.copy())\n",
    "\n",
    "    for i in range(0,randomNos.size):\n",
    "        \n",
    "        colors_iter = randomNos.base_colors.copy()\n",
    "        colors_iter[i] = 'black'\n",
    "        randomNos.colors.append(colors_iter.copy())\n",
    "        randomNos.frames.append(randomNos.rand_list.copy())\n",
    "        \n",
    "        j=i\n",
    "        \n",
    "        \n",
    "        while (0<j) and (randomNos.rand_list[j-1]>randomNos.rand_list[j]):\n",
    "            \n",
    "            colors_iter = randomNos.base_colors.copy()\n",
    "            colors_iter[j] = 'red'\n",
    "            colors_iter[j-1] = 'red'\n",
    "            randomNos.colors.append(colors_iter.copy())\n",
    "            randomNos.frames.append(randomNos.rand_list.copy())\n",
    "            \n",
    "            randomNos.rand_list[j-1],randomNos.rand_list[j]=randomNos.rand_list[j],randomNos.rand_list[j-1]\n",
    "            \n",
    "            colors_iter = randomNos.base_colors.copy()\n",
    "            colors_iter[j] = 'green'\n",
    "            colors_iter[j-1] = 'green'\n",
    "            randomNos.colors.append(colors_iter.copy())\n",
    "            randomNos.frames.append(randomNos.rand_list.copy())\n",
    "            \n",
    "            j-=1\n",
    "    \n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x = randomNos(15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x.generate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[701, 413, 83, 408, 340, 487, 976, 63, 715, 924, 683, 412, 636, 356, 242]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.rand_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "insertionSort(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\nickj\\AppData\\Local\\Continuum\\Anaconda3\\envs\\py35\\lib\\site-packages\\matplotlib\\animation.py:1021: UserWarning: MovieWriter pillow unavailable\n",
      "  warnings.warn(\"MovieWriter %s unavailable\" % writer)\n"
     ]
    }
   ],
   "source": [
    "x.saveVideo('insertion_sort')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<video alt=\"test\" controls>\n",
       "        <source src=\"insertion_sort.mp4\" type=\"video/mp4\">\n",
       "        </video>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HTML(\"\"\"<video alt=\"test\" controls>\n",
    "        <source src=\"insertion_sort.mp4\" type=\"video/mp4\">\n",
    "        </video>\"\"\")\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Selection Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selectionSort(randomNos):\n",
    "    randomNos.frames.append(randomNos.rand_list.copy())\n",
    "    randomNos.colors.append(randomNos.base_colors.copy())\n",
    "\n",
    "    for i in range(0,randomNos.size):\n",
    "        \n",
    "        colors_iter = randomNos.colors[-1]\n",
    "        for k in range(0,randomNos.size):\n",
    "            if k==i:\n",
    "                colors_iter[i] = 'black'\n",
    "            elif k<i:\n",
    "                colors_iter[k] = 'green'\n",
    "            else:\n",
    "                colors_iter[k] = 'gray'\n",
    "            \n",
    "            \n",
    "        randomNos.colors.append(colors_iter.copy())\n",
    "        randomNos.frames.append(randomNos.rand_list.copy())\n",
    "        \n",
    "        arr_min = randomNos.rand_list[i]\n",
    "        ind_min = i\n",
    "        for j in range(i+1,randomNos.size):\n",
    "            \n",
    "            if arr_min>randomNos.rand_list[j]:\n",
    "                colors_iter = randomNos.colors[-1]\n",
    "                if ind_min != i:\n",
    "                    colors_iter[ind_min] = 'red'\n",
    "                colors_iter[j] = 'green'\n",
    "                randomNos.colors.append(colors_iter.copy())\n",
    "                randomNos.frames.append(randomNos.rand_list.copy())\n",
    "\n",
    "                arr_min = randomNos.rand_list[j]\n",
    "                ind_min = j\n",
    "            \n",
    "            else:\n",
    "                colors_iter = randomNos.colors[-1]\n",
    "                colors_iter[j] = 'red'\n",
    "                randomNos.colors.append(colors_iter.copy())\n",
    "                randomNos.frames.append(randomNos.rand_list.copy())\n",
    "        \n",
    "        if randomNos.rand_list[i]>randomNos.rand_list[ind_min]:\n",
    "            randomNos.rand_list[ind_min],randomNos.rand_list[i] = randomNos.rand_list[i],randomNos.rand_list[ind_min]\n",
    "            colors_iter = randomNos.colors[-1]\n",
    "            colors_iter[i] = 'red'\n",
    "            colors_iter[ind_min] = 'red'\n",
    "            randomNos.colors.append(colors_iter.copy())\n",
    "            randomNos.frames.append(randomNos.rand_list.copy())\n",
    "            \n",
    "        else:\n",
    "            randomNos.rand_list[ind_min],randomNos.rand_list[i] = randomNos.rand_list[i],randomNos.rand_list[ind_min]\n",
    "            colors_iter = randomNos.colors[-1]\n",
    "            colors_iter[i] = 'green'\n",
    "            colors_iter[ind_min] = 'green'\n",
    "            randomNos.colors.append(colors_iter.copy())\n",
    "            randomNos.frames.append(randomNos.rand_list.copy())\n",
    "    \n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x = randomNos(15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x.generate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[735, 671, 719, 19, 459, 949, 433, 46, 764, 113, 634, 34, 213, 96, 743]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.rand_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "selectionSort(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\nickj\\AppData\\Local\\Continuum\\Anaconda3\\envs\\py35\\lib\\site-packages\\matplotlib\\animation.py:1021: UserWarning: MovieWriter pillow unavailable\n",
      "  warnings.warn(\"MovieWriter %s unavailable\" % writer)\n"
     ]
    }
   ],
   "source": [
    "x.saveVideo('selection_sort')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<video alt=\"test\" controls>\n",
       "        <source src=\"selection_sort.mp4\" type=\"video/mp4\">\n",
       "        </video>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HTML(\"\"\"<video alt=\"test\" controls>\n",
    "        <source src=\"selection_sort.mp4\" type=\"video/mp4\">\n",
    "        </video>\"\"\")\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "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.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}