{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sebastian Raschka \n",
      "last updated: 2017-07-24 \n",
      "\n",
      "CPython 3.6.1\n",
      "IPython 6.0.0\n"
     ]
    }
   ],
   "source": [
    "%load_ext watermark\n",
    "%watermark -a 'Sebastian Raschka' -u -d -v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bubble Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quick note about Bubble sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I don't want to get into the details about sorting algorithms here, but there is a great report  \n",
    "[\"Sorting in the Presence of Branch Prediction and Caches - Fast Sorting on Modern Computers\"](https://www.cs.tcd.ie/publications/tech-reports/reports.05/TCD-CS-2005-57.pdf) written by Paul Biggar and David Gregg, where they describe and analyze elementary sorting algorithms in very nice detail (see chapter 4).   \n",
    "\n",
    "And for a quick reference, [this website](http://www.sorting-algorithms.com/bubble-sort) has a nice animation of this algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A long story short: The \"worst-case\" complexity of the Bubble sort algorithm (i.e., \"Big-O\")  \n",
    " $\\Rightarrow \\pmb O(n^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bubble sort implemented in (C)Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def python_bubblesort(a_list):\n",
    "    \"\"\" Bubblesort in Python for list objects (sorts in place).\"\"\"\n",
    "    length = len(a_list)\n",
    "    for i in range(length):\n",
    "        for j in range(1, length):\n",
    "            if a_list[j] < a_list[j-1]:\n",
    "                a_list[j-1], a_list[j] = a_list[j], a_list[j-1]\n",
    "    return a_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "Below is a improved version that quits early if no further swap is needed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def python_bubblesort_improved(a_list):\n",
    "    \"\"\" Bubblesort in Python for list objects (sorts in place).\"\"\"\n",
    "    length = len(a_list)\n",
    "    swapped = 1\n",
    "    for i in range(length):\n",
    "        if swapped: \n",
    "            swapped = 0\n",
    "            for ele in range(length-i-1):\n",
    "                if a_list[ele] > a_list[ele + 1]:\n",
    "                    temp = a_list[ele + 1]\n",
    "                    a_list[ele + 1] = a_list[ele]\n",
    "                    a_list[ele] = temp\n",
    "                    swapped = 1\n",
    "    return a_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Verifying that all implementations work correctly"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bubblesort works correctly\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import copy\n",
    "random.seed(4354353)\n",
    "\n",
    "l = [random.randint(1,1000) for num in range(1, 1000)]\n",
    "l_sorted = sorted(l)\n",
    "for f in [python_bubblesort, python_bubblesort_improved]:\n",
    "    assert(l_sorted  == f(copy.copy(l)))\n",
    "print('Bubblesort works correctly')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Performance comparison"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 1.42 ms per loop\n",
      "The slowest run took 95.97 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000 loops, best of 3: 24.8 µs per loop\n"
     ]
    }
   ],
   "source": [
    "# small list\n",
    "\n",
    "l_small = [random.randint(1,100) for num in range(1, 100)]\n",
    "l_small_cp = copy.copy(l_small)\n",
    "\n",
    "%timeit python_bubblesort(l_small)\n",
    "%timeit python_bubblesort_improved(l_small_cp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 19.5 s per loop\n",
      "The slowest run took 7804.31 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1 loop, best of 3: 2.45 ms per loop\n"
     ]
    }
   ],
   "source": [
    "# larger list\n",
    "\n",
    "l_small = [random.randint(1,10000) for num in range(1, 10000)]\n",
    "l_small_cp = copy.copy(l_small)\n",
    "\n",
    "%timeit python_bubblesort(l_small)\n",
    "%timeit python_bubblesort_improved(l_small_cp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "<br>"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}