{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58719c96",
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort_debug(x, debug_flag):\n",
    "    for i in range(len(x)):\n",
    "        min_idx = i\n",
    "        for j in range(i+1, len(x)):\n",
    "            if(x[j] < x[min_idx]):\n",
    "                min_idx = j\n",
    "        next_element = x.pop(min_idx)\n",
    "        x.insert(i, next_element)\n",
    "        if(debug_flag):\n",
    "            print(\"Breakpoint; invariant: List sorted until index i = \", i, \";\\n\"\\\n",
    "                  \"All elements of the unsorted part are greater or equal than those in the sorted part.\\n\"\\\n",
    "                  \"Sorted part of the list: \", x[:i+1], \"\\nUnsorted part of the list: \", x[i+1:], sep=\"\")\n",
    "            input()\n",
    "        \n",
    "def selection_sort(x):\n",
    "    selection_sort_debug(x, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "622231ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "n = 11\n",
    "test_list_n = [random.randrange(n*n) for j in range(n)]\n",
    "print(\"Test list:\", test_list_n, end=\"\\n\\n\")\n",
    "selection_sort_debug(test_list_n, True)\n",
    "print(\"Test list:\", test_list_n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f3863c1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergesort_debug(x, debug_flag):\n",
    "    sublist_size = 1  # size of sublists, each of which has been sorted already\n",
    "    while sublist_size < len(x):\n",
    "        for offset in range(0, len(x) - sublist_size, 2*sublist_size):\n",
    "            # we are now merging two sublists, one starting at offset, one starting at offset+sublist_size\n",
    "            merged_sublist = []\n",
    "            i = 0  # internal index defined over the first sublist\n",
    "            j, second_sublist_size = 0, sublist_size  # internal index defined over the second sublist\n",
    "            if offset + 2*sublist_size > len(x):\n",
    "                second_sublist_size = len(x) - offset - sublist_size  # index must remain within boundaries\n",
    "            if debug_flag:\n",
    "                print(\"Now merging x[\", offset, \":\", offset+sublist_size, \"] = \", \\\n",
    "                      x[offset: offset+sublist_size], \" with x[\", offset+sublist_size, \":\", \\\n",
    "                      offset+sublist_size+second_sublist_size, \"] = \",\n",
    "                      x[offset+sublist_size: offset+sublist_size+second_sublist_size], sep='')\n",
    "            \n",
    "            while i < sublist_size and j < second_sublist_size:\n",
    "                if(x[offset + i] < x[offset + sublist_size + j]):\n",
    "                    merged_sublist.append(x[offset + i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    merged_sublist.append(x[offset + sublist_size + j])\n",
    "                    j += 1\n",
    "            # one sublist is now exhausted, we only need to take care of this if it is the first one\n",
    "            if i < sublist_size:\n",
    "                for element in x[offset + i: offset + sublist_size]:\n",
    "                    merged_sublist.append(element)\n",
    "            \n",
    "            # now overwrite the two sublists with the merged sublist\n",
    "            for i in range(len(merged_sublist)):\n",
    "                x[offset+i] = merged_sublist[i]\n",
    "            if debug_flag:\n",
    "                print(\"Merged to x[\", offset, \":\", offset+sublist_size+second_sublist_size, \"] = \", \\\n",
    "                      x[offset: offset+sublist_size+second_sublist_size], sep = '')\n",
    "                input()\n",
    "        sublist_size *= 2\n",
    "        \n",
    "def mergesort(x):\n",
    "    mergesort_debug(x, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7f1bd5ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "n = 11\n",
    "test_list_n = [random.randrange(n*n) for j in range(n)]\n",
    "print(\"Test list:\", test_list_n, end=\"\\n\\n\")\n",
    "mergesort_debug(test_list_n, True)\n",
    "print(\"Test list:\", test_list_n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "353f2fdf",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import random\n",
    "\n",
    "step = 50\n",
    "nmax = 1000\n",
    "repetitions = 100\n",
    "\n",
    "perf_select = {}\n",
    "perf_merge = {}\n",
    "random.seed()\n",
    "\n",
    "for n in range(0, nmax+1, step):\n",
    "    runtime_select = 0.0\n",
    "    runtime_merge = 0.0\n",
    "    for i in range(repetitions):\n",
    "        test_list_n = [random.randrange(n*n) for j in range(n)]\n",
    "        list_copy = [test_list_n[j] for j in range(n)]\n",
    "        \n",
    "        start = time.time()\n",
    "        selection_sort(test_list_n)\n",
    "        runtime_select += time.time() - start\n",
    "        \n",
    "        start = time.time()\n",
    "        mergesort(list_copy)\n",
    "        runtime_merge += time.time() - start\n",
    "        \n",
    "    perf_select[n] = runtime_select / repetitions\n",
    "    perf_merge[n] = runtime_merge / repetitions\n",
    "    \n",
    "    print(n, perf_select[n], perf_merge[n], sep='\\t')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e477dc28",
   "metadata": {},
   "outputs": [],
   "source": [
    "import seaborn as sbn\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "keylist_select = list(perf_select.keys())\n",
    "vallist_select = list(perf_select.values())\n",
    "\n",
    "keylist_merge = list(perf_merge.keys())\n",
    "vallist_merge = list(perf_merge.values())\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "fig.set_size_inches(15, 9)\n",
    "plt.xticks(fontsize=18, color=\"#322300\")\n",
    "plt.yticks(fontsize=18, color=\"#322300\")\n",
    "ax.set_xlabel(\"input list size\", fontsize=24, color=\"#322300\")\n",
    "ax.set_ylabel(\"average runtime in seconds\", fontsize=24, color=\"#322300\")\n",
    "\n",
    "sbn.regplot(x=keylist_select, y=vallist_select, color='#005528', order=2)  # green for selection sort\n",
    "sbn.regplot(x=keylist_merge, y=vallist_merge, color='#002855', order=1)  # blue for mergesort"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}