{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tutorial 06 - Data sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Various algorithms for data sorting and their comparison, bubble sort, selection sort, insertion sort, shell sort, quick sort, heap sort, benchmarking."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bubble sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "\n",
    "**Exercise 06.1:** Implement the bubble sort algorithm.\n",
    "    \n",
    "</div>    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(array):\n",
    "    \"\"\"\n",
    "    Sorts the input data using bubble sort algorithm.\n",
    "    Args:\n",
    "        array (array_like): input data\n",
    "    Returns:\n",
    "        numpy.ndarray: sorted data\n",
    "    \"\"\"\n",
    "    \n",
    "    # add your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may evaluate the correctness of your implementation using the [`numpy.sort`](https://numpy.org/doc/stable/reference/generated/numpy.sort.html) function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_array = np.random.rand(100)\n",
    "try:\n",
    "    np.testing.assert_array_almost_equal(bubble_sort(random_array), np.sort(random_array), decimal=7)\n",
    "except AssertionError as E:\n",
    "    print(E)\n",
    "else:\n",
    "    print(\"The implementation is correct.\")    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Selection sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "\n",
    "**Exercise 06.2:** Implement the selection sort algorithm.\n",
    "    \n",
    "</div>    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(array):\n",
    "    \"\"\"\n",
    "    Sorts the input data using selection sort algorithm.\n",
    "    Args:\n",
    "        array (array_like): input data\n",
    "    Returns:\n",
    "        numpy.ndarray: sorted data\n",
    "    \"\"\"\n",
    "    \n",
    "    # add your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may evaluate the correctness of your implementation using the [`numpy.sort`](https://numpy.org/doc/stable/reference/generated/numpy.sort.html) function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_array = np.random.rand(100)\n",
    "try:\n",
    "    np.testing.assert_array_almost_equal(selection_sort(random_array), np.sort(random_array), decimal=7)\n",
    "except AssertionError as E:\n",
    "    print(E)\n",
    "else:\n",
    "    print(\"The implementation is correct.\")    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Insertion sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "\n",
    "**Exercise 06.3:** Implement the insertion sort algorithm.\n",
    "    \n",
    "</div>    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(array):\n",
    "    \"\"\"\n",
    "    Sorts the input data using inserion sort algorithm.\n",
    "    Args:\n",
    "        array (array_like): input data\n",
    "    Returns:\n",
    "        numpy.ndarray: sorted data\n",
    "    \"\"\"\n",
    "    \n",
    "    # add your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may evaluate the correctness of your implementation using the [`numpy.sort`](https://numpy.org/doc/stable/reference/generated/numpy.sort.html) function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_array = np.random.rand(100)\n",
    "try:\n",
    "    np.testing.assert_array_almost_equal(insertion_sort(random_array), np.sort(random_array), decimal=7)\n",
    "except AssertionError as E:\n",
    "    print(E)\n",
    "else:\n",
    "    print(\"The implementation is correct.\")    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shell sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "\n",
    "**Exercise 06.4:** Implement the shell sort algorithm.\n",
    "    \n",
    "</div>    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shell_sort(array):\n",
    "    \"\"\"\n",
    "    Sorts the input data using shell sort algorithm.\n",
    "    Args:\n",
    "        array (array_like): input data\n",
    "    Returns:\n",
    "        numpy.ndarray: sorted data\n",
    "    \"\"\"\n",
    "    \n",
    "    # add your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may evaluate the correctness of your implementation using the [`numpy.sort`](https://numpy.org/doc/stable/reference/generated/numpy.sort.html) function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_array = np.random.rand(100)\n",
    "try:\n",
    "    np.testing.assert_array_almost_equal(shell_sort(random_array), np.sort(random_array), decimal=7)\n",
    "except AssertionError as E:\n",
    "    print(E)\n",
    "else:\n",
    "    print(\"The implementation is correct.\")  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quick sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "\n",
    "**Exercise 06.5:** Implement the quick sort algorithm.\n",
    "    \n",
    "</div>    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quick_sort(array):\n",
    "    \"\"\"\n",
    "    Sorts the input data using quicksort algorithm.\n",
    "    Args:\n",
    "        array (array_like): input data\n",
    "    Returns:\n",
    "        numpy.ndarray: sorted data\n",
    "    \"\"\"\n",
    "    \n",
    "    # add your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may evaluate the correctness of your implementation using the [`numpy.sort`](https://numpy.org/doc/stable/reference/generated/numpy.sort.html) function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_array = np.random.rand(100)\n",
    "try:\n",
    "    np.testing.assert_array_almost_equal(quick_sort(random_array), np.sort(random_array), decimal=7)\n",
    "except AssertionError as E:\n",
    "    print(E)\n",
    "else:\n",
    "    print(\"The implementation is correct.\")  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Heap sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "\n",
    "**Exercise 06.6:** Implement the heap sort algorithm.\n",
    "    \n",
    "</div>    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heap_sort(array):\n",
    "    \"\"\"\n",
    "    Sorts the input data using heapsort algorithm.\n",
    "    Args:\n",
    "        array (array_like): input data\n",
    "    Returns:\n",
    "        numpy.ndarray: sorted data\n",
    "    \"\"\"\n",
    "    \n",
    "    # add your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may evaluate the correctness of your implementation using the [`numpy.sort`](https://numpy.org/doc/stable/reference/generated/numpy.sort.html) function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_array = np.random.rand(100)\n",
    "try:\n",
    "    np.testing.assert_array_almost_equal(heap_sort(random_array), np.sort(random_array), decimal=7)\n",
    "except AssertionError as E:\n",
    "    print(E)\n",
    "else:\n",
    "    print(\"The implementation is correct.\")  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Benchmark"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "\n",
    "**Exercise 06.7:** Compare the running times of sorting algorithms for different size of input and plot the result.\n",
    "    \n",
    "</div>    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# add your code here\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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}