{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# tools\n",
    "import time\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "# generate random data\n",
    "def make_random(n):\n",
    "    return [random.randint(1,1000) for i in range(0,n)]\n",
    "# generate ascending sequence of data\n",
    "def ascending(n):\n",
    "    return [i for i in range(0,n)]\n",
    "# geenrate descending sequence of data\n",
    "def descending(n):\n",
    "    return [n-i for i in range(0,n)]\n",
    "# check if data x are sorted\n",
    "def check(x):\n",
    "    n = len(x)\n",
    "    for i in range(1,n):\n",
    "        assert x[i-1] <= x[i]\n",
    "# measure the time used to apply some sorting algorithm \"algo\" to data \"x\"\n",
    "def measure_time(algo,x):\n",
    "    start = time.time()\n",
    "    algo(x)\n",
    "    end = time.time();\n",
    "    check(x) # sanity\n",
    "    return end - start\n",
    "# plot time of some sorting algorithms\n",
    "def show_time(n,scenario,sorts):\n",
    "    durations = []\n",
    "    m = len(sorts)\n",
    "    plt.figure(figsize=(10,6))\n",
    "    for k in range(0,m):\n",
    "        durations.append([measure_time(sorts[k][0],scenario(i)) for i in range(1,n)])\n",
    "        plt.plot(durations[k], label=sorts[k][1])\n",
    "    plt.xlabel(\"Array length\")\n",
    "    plt.ylabel(\"Runtime (s)\")\n",
    "    plt.legend(bbox_to_anchor=(0.85, 1), loc='lower right', borderaxespad=0.)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# original sorting algorithm (\"selection sort\" from last week)\n",
    "def original_selection_sort(x):\n",
    "    n = len(x)\n",
    "    for i in range(0,n):\n",
    "        for j in range(i,n):\n",
    "            if x[j] < x[i]:\n",
    "                x[i],x[j] = x[j],x[i]\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# selection sort algorithm, slightly improved\n",
    "def selection_sort (x):\n",
    "    n = len(x)\n",
    "    for i in range(0,n):\n",
    "        v = x[i]\n",
    "        k = i\n",
    "        for j in range(i+1,n):\n",
    "            if x[j] < x[k]:\n",
    "                k = j\n",
    "        if k != i:\n",
    "            x[k],x[i] = x[i],x[k]\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# insertion sort algorithm from case study\n",
    "def original_insertion_sort(x):\n",
    "    n = len(x)\n",
    "    for i in range(1, n):\n",
    "        for j in reversed(range(0, i)):\n",
    "            if x[j+1] < x[j]:\n",
    "                x[j+1], x[j] = x[j], x[j+1]\n",
    "            else:\n",
    "                break\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# insertion sort algorithm (slightly improved)\n",
    "def insertion_sort(x):\n",
    "    n = len(x)\n",
    "    for i in range(0, n):\n",
    "        j = i;\n",
    "        v = x[i];\n",
    "        while j > 0 and v < x[j-1]:\n",
    "            x[j] = x[j-1]\n",
    "            j = j-1\n",
    "        x[j] = v\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = make_random(10)\n",
    "print(x)\n",
    "insertion_sort(x)\n",
    "check(x)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=4000\n",
    "print(\"random\")\n",
    "print(\"original selection\",measure_time(original_selection_sort,make_random(n)))\n",
    "print(\"selection\",measure_time(selection_sort,make_random(n)))\n",
    "print(\"original insertion\",measure_time(original_insertion_sort,make_random(n)))\n",
    "print(\"insertion\",measure_time(insertion_sort,make_random(n)))\n",
    "print(\"ascending\")\n",
    "print(\"original selection\",measure_time(original_selection_sort,ascending(n)))\n",
    "print(\"selection\",measure_time(selection_sort,ascending(n)))\n",
    "print(\"original insertion\",measure_time(original_insertion_sort,ascending(n)))\n",
    "print(\"insertion\",measure_time(insertion_sort,ascending(n)))\n",
    "print(\"descending\")\n",
    "print(\"original selection\",measure_time(original_selection_sort,descending(n)))\n",
    "print(\"selection\",measure_time(selection_sort,descending(n)))\n",
    "print(\"original insertion\",measure_time(original_insertion_sort,descending(n)))\n",
    "print(\"insertion\",measure_time(insertion_sort,descending(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "show_time(400,make_random,[\n",
    "    [original_selection_sort,\"original selection\"],\n",
    "    [selection_sort,\"selection\"],\n",
    "    [original_insertion_sort,\"original insertion\"],\n",
    "    [insertion_sort,\"insertion\"]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linear_search(x,b):\n",
    "    n = len(x)\n",
    "    m = n\n",
    "    while m > 0 and b < x[m-1]:\n",
    "        m = m - 1\n",
    "    return m\n",
    "# right limit r exclusive\n",
    "def binary_search_r(x, l, r, b):\n",
    "    if l==r: # not found\n",
    "        return l\n",
    "    assert(l<r)\n",
    "    m = (l+r) // 2\n",
    "    if b < x[m]:\n",
    "        return binary_search_r(x,0,m,b)\n",
    "    elif b > x[m]:\n",
    "        return binary_search_r(x,m+1,r,b)\n",
    "    else: # b == x[m] found\n",
    "        return m\n",
    "def binary_search(x,b):\n",
    "    return binary_search_r(x,0,len(x),b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(binary_search([1,3,5],2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def time_search(x,algo):\n",
    "    start = time.time()\n",
    "    for i in range(0,10000):\n",
    "        b = algo(x,i)\n",
    "    end = time.time()\n",
    "    return end-start  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = ascending(10000)\n",
    "print(\"linear\",time_search(x,linear_search))\n",
    "print(\"binary\",time_search(x,binary_search))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_linear(x,b):\n",
    "    p = linear_search(x,b)\n",
    "    x.insert(p,b)\n",
    "    return x\n",
    "def linear_insertion_sort (x):\n",
    "    res = []\n",
    "    n = len(x)\n",
    "    for i in range(0,n):\n",
    "        insert_linear(res,x[i])\n",
    "    for i in range(0,n):\n",
    "        x[i] = res[i]\n",
    "def insert_binary(x,b):\n",
    "    p = binary_search(x,b)\n",
    "    x.insert(p,b)\n",
    "    return x\n",
    "def binary_insertion_sort (x):\n",
    "    res = []\n",
    "    n = len(x)\n",
    "    for i in range(0,n):\n",
    "        insert_binary(res,x[i])\n",
    "    for i in range(0,n):        \n",
    "        x[i] = res[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(insert_linear([1,3,5,11,17,23],333))\n",
    "print(insert_binary([1,3,5,11,17,23],333))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = [10,18,2,8,20]\n",
    "binary_insertion_sort(data)\n",
    "print(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show_time(400,make_random,[\n",
    "    [selection_sort,\"selection\"],\n",
    "    [insertion_sort,\"insertion\"],\n",
    "    [linear_insertion_sort,\"linear insert\"],\n",
    "    [binary_insertion_sort,\"binary insert\"]\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=8000\n",
    "print(\"random\")\n",
    "print(\"binary_insertion\",measure_time(binary_insertion_sort,make_random(n)))\n",
    "print(\"linear_insertion\",measure_time(linear_insertion_sort,make_random(n)))\n",
    "print(\"ascending\")\n",
    "print(\"binary_insertion\",measure_time(binary_insertion_sort,ascending(n)))\n",
    "print(\"linear_insertion\",measure_time(linear_insertion_sort,ascending(n)))\n",
    "print(\"descending\")\n",
    "print(\"binary_insertion\",measure_time(binary_insertion_sort,descending(n)))\n",
    "print(\"linear_insertion\",measure_time(linear_insertion_sort,descending(n)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(x,l,m,r):\n",
    "    result = []\n",
    "    i = l\n",
    "    j = m\n",
    "    while i < m and j < r:\n",
    "        if x[i] < x[j]:\n",
    "            result.append(x[i])\n",
    "            i = i + 1\n",
    "        else:\n",
    "            result.append(x[j])\n",
    "            j = j + 1\n",
    "    while i < m:\n",
    "        result.append(x[i])\n",
    "        i = i + 1\n",
    "    while j < r:\n",
    "        result.append(x[j])\n",
    "        j = j + 1\n",
    "    for i in range(l,r):\n",
    "        x[i] = result[i-l]\n",
    "\n",
    "# recursively sort data in x[l:r], (l included, r excluded!)\n",
    "def merge_sort_r(x,l,r):\n",
    "    assert(0 <= l and l <= r)\n",
    "    assert(r <= len(x))\n",
    "    if r - l > 1: # more than one element\n",
    "        m = (l+r) // 2\n",
    "        merge_sort_r(x,l,m)\n",
    "        merge_sort_r(x,m,r)\n",
    "        merge(x,l,m,r)\n",
    "\n",
    "def merge_sort(x):\n",
    "    merge_sort_r(x,0,len(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = make_random(80)\n",
    "merge_sort(x)\n",
    "check(x)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show_time(1000,make_random,[[binary_insertion_sort,\"insert\"],[merge_sort,\"merge\"]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=100000\n",
    "print(\"random\")\n",
    "print(\"binary_insertion\",measure_time(binary_insertion_sort,make_random(n)))\n",
    "print(\"merge\",measure_time(merge_sort,make_random(n)))\n",
    "print(\"ascending\")\n",
    "print(\"binary_insertion\",measure_time(binary_insertion_sort,ascending(n)))\n",
    "print(\"merge\",measure_time(merge_sort,ascending(n)))\n",
    "print(\"descending\")\n",
    "print(\"binary_insertion\",measure_time(binary_insertion_sort,descending(n)))\n",
    "print(\"merge\",measure_time(merge_sort,descending(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(x,l,r,p):\n",
    "    r = r-1\n",
    "    while (l < r):\n",
    "        while x[l] < p:\n",
    "            l = l + 1\n",
    "        while x[r] > p:\n",
    "            r = r - 1\n",
    "        x[l],x[r] = x[r],x[l]\n",
    "        if x[l] == x[r]:\n",
    "            l = l + 1\n",
    "    return l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quick_sort_r(x,l,r):\n",
    "    if r-l > 1:\n",
    "        m = partition(x,l,r,x[(l+r)//2])\n",
    "        quick_sort_r(x,l,m)\n",
    "        quick_sort_r(x,m+1,r)\n",
    "\n",
    "def quick_sort(x):\n",
    "    quick_sort_r(x,0,len(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = make_random(100)\n",
    "quick_sort(x)\n",
    "check(x)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show_time(1000,make_random,[[binary_insertion_sort,\"insert\"],[merge_sort,\"merge\"],[quick_sort,\"quick\"]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=100000\n",
    "print(\"random\")\n",
    "print(\"binary_insertion\",measure_time(binary_insertion_sort,make_random(n)))\n",
    "print(\"merge\",measure_time(merge_sort,make_random(n)))\n",
    "print(\"quick\",measure_time(merge_sort,make_random(n)))\n",
    "print(\"ascending\")\n",
    "print(\"binary_insertion\",measure_time(binary_insertion_sort,ascending(n)))\n",
    "print(\"merge\",measure_time(merge_sort,ascending(n)))\n",
    "print(\"quick\",measure_time(merge_sort,make_random(n)))\n",
    "print(\"descending\")\n",
    "print(\"binary_insertion\",measure_time(binary_insertion_sort,descending(n)))\n",
    "print(\"merge\",measure_time(merge_sort,make_random(n)))\n",
    "print(\"quick\",measure_time(merge_sort,descending(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def natural_merge_sort(x):\n",
    "    n = len(x)\n",
    "    l = n\n",
    "    while l != 0:\n",
    "        r = 0\n",
    "        while r < n:\n",
    "            # build intervals [l,m) and [m,r)\n",
    "            l = r # previous right border, valid element\n",
    "            m = l\n",
    "            while m < n-1 and x[m] <= x[m+1]:\n",
    "                m = m + 1\n",
    "            m = m + 1 # first element not in ascending sequence\n",
    "            if m < n:\n",
    "                r = m # valid element\n",
    "                while r < n-1 and x[r] <= x[r+1]:\n",
    "                    r = r + 1\n",
    "                r = r + 1 # first element not in ascending sequence\n",
    "                merge(x,l,m,r)\n",
    "            else: # sweep done\n",
    "                r = n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=100000\n",
    "print(\"random\")\n",
    "print(\"natural_merge\",measure_time(natural_merge_sort,make_random(n)))\n",
    "print(\"merge\",measure_time(merge_sort,make_random(n)))\n",
    "print(\"quick\",measure_time(merge_sort,make_random(n)))\n",
    "print(\"ascending\")\n",
    "print(\"natural_merge\",measure_time(natural_merge_sort,ascending(n)))\n",
    "print(\"merge\",measure_time(merge_sort,ascending(n)))\n",
    "print(\"quick\",measure_time(merge_sort,make_random(n)))\n",
    "print(\"descending\")\n",
    "print(\"natural_merge\",measure_time(natural_merge_sort,descending(n)))\n",
    "print(\"merge\",measure_time(merge_sort,make_random(n)))\n",
    "print(\"quick\",measure_time(merge_sort,descending(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.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}