Initial commit

[sort-animations.git] / insertion-sort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import time\n",
    "import re\n",
    "from IPython.display import clear_output\n",
    "from PIL import Image, ImageDraw, ImageColor, ImageFont"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "ROWS = 300\n",
    "COLUMNS = 720\n",
    "RANGE = 360"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "initial_items = [int((float(i) * RANGE) / float(COLUMNS)) for i in range(COLUMNS)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_frame(rows, frame_number, prefix='frame'):\n",
    "    im = Image.new('RGB', (COLUMNS * 1, ROWS * 1))\n",
    "\n",
    "    draw = ImageDraw.Draw(im)\n",
    "    for r in range(len(rows)):\n",
    "        if frame_number >= len(rows[r]):\n",
    "            row = rows[r][-1]\n",
    "        else:\n",
    "            row = rows[r][frame_number]\n",
    "#     for (r, row) in enumerate(grid):\n",
    "        for (c, cell) in enumerate(row):\n",
    "            rx = c * 1\n",
    "            ry = r * 1\n",
    "    #         print(rx, ry)\n",
    "            draw.rectangle([rx, ry, rx + 1, ry + 1], \n",
    "                           fill=ImageColor.getrgb(\"hsl({}, 100%, 50%)\".format(cell)))\n",
    "\n",
    "    im.save('{}{:04}.png'.format(prefix, frame_number), 'PNG')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertsort_step(items, sorted_limit):\n",
    "    inserting = items[sorted_limit]\n",
    "    i = len([item for item in items[:sorted_limit] if item < inserting])\n",
    "#     print('sl = {}, i = {}; items = {};  slices {} {} {} {}'.format(sorted_limit, i, items, items[:i], inserting, items[i:sorted_limit], items[sorted_limit + 1:]))\n",
    "    items = items[:i] + [inserting] + items[i:sorted_limit] + items[sorted_limit + 1:]\n",
    "    return items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 'b']"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list('abcde')[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertsort(items, step_history):\n",
    "    for sorted_limit in range(1, len(items)):\n",
    "        step_history += [items[:]]\n",
    "        items = insertsort_step(items, sorted_limit)\n",
    "    step_history += [items[:]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "histories = []\n",
    "for _ in range(ROWS):\n",
    "    items = initial_items[:]\n",
    "    random.shuffle(items)\n",
    "    step_history = []\n",
    "    insertsort(items, step_history)\n",
    "    histories += [step_history]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "# histories"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0,\n",
       " 10,\n",
       " 20,\n",
       " 30,\n",
       " 40,\n",
       " 50,\n",
       " 60,\n",
       " 70,\n",
       " 80,\n",
       " 90,\n",
       " 100,\n",
       " 110,\n",
       " 120,\n",
       " 130,\n",
       " 140,\n",
       " 150,\n",
       " 160,\n",
       " 170,\n",
       " 180,\n",
       " 190,\n",
       " 200,\n",
       " 210,\n",
       " 220,\n",
       " 230,\n",
       " 240,\n",
       " 250,\n",
       " 260,\n",
       " 270,\n",
       " 280,\n",
       " 290,\n",
       " 300,\n",
       " 310,\n",
       " 320,\n",
       " 330,\n",
       " 340,\n",
       " 350]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# histories[2][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "720"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(histories[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "! rm insertsort*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for frame_n in range(max(len(h) for h in histories)):\n",
    "    draw_frame(histories, frame_n, prefix='insertsort')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "719"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frame_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "! apngasm all-insertsort.png insertsort*png 1 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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
}