10 - Python 10min a day - Testing your new skills - code a quick-sort algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"assets/jeremy-lapak-CVvFVQ_-oUg-unsplash.png\" alt=\"Python Envs\" style=\"display: block; margin: 0 auto\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Learning Python 10 minutes a day #10\n",
    "## Testing your new skills: code a quick-sort algorithm\n",
    "[Medium article link](https://towardsdatascience.com/learning-python-10-minutes-a-day-10-91b8ff16cd60)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a [series](https://python-10-minutes-a-day.rocks) of short 10 minute Python articles helping you to get started with Python. I try to post an article each day (no promises), starting from the very basics, going up to more complex idioms. Feel free to contact me on [LinkedIn](https://www.linkedin.com/in/dennisbakhuis/) for questions or requests on particular subjects of Python, you want to know about."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Today, we will not discuss a new topic but have a short assignment to harden your knowledge. About ten years ago I went to a talk in which Python was promoted for doing scientific computing. During this talk, there was an example showing the quicksort algorithm. Quicksort is an relatively simple but effective sorting algorithm. What amazed me during the talk was that after discussing how the algorithm worked using pseudo-code, the python solution was almost identical to the pseudo-code. Hopefully, you can also be amazed how straightforward it is to implement the algorithm in Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"assets/day10-quicksort.png\" alt=\"Python Envs\"  width=\"600\" style=\"display: block; margin: 0 auto\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quicksort is a so-called divide-and-conquer algorithm. First, it selects one element out of the list, which is called the pivot. Then it iterates through the remaining elements and divides them into three groups: smaller than the pivot value, equal to the pivot value, and larger than the pivot value. It repeats the process with the smaller and larger portions by calling itself. In the end, it merges all list together and you and up with a sorted list. In pseudo-code it looks something like this:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"assets/day10-pseudo.png\" alt=\"Python Envs\"  width=\"400\" style=\"display: block; margin: 0 auto\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only using this information and all the topics we have discussed so far, you should be able to write your own quicksort algorithm. The only thing you might need is a nice list of values to sort. There are many ways to create those but we have not yet discussed the packages that might help with generating random numbers. Therefore, I will provide the code for creating a list of random numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "N = 10  # amount of random values\n",
    "\n",
    "values = []\n",
    "for ix in range(N):\n",
    "    values.append(random.random() * 100)\n",
    "\n",
    "# your quicksort function should start here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code snippet imports the random module from the Python standard library and is used to generate random numbers. The random() function returns a random number between 0 and 1. To have them somewhat bigger, we multiply them by 100, as it is easier to read. While implementing your solution, I would keep N, i.e. the number of values, small. When all is working well, feel free to experiment with the size of the list to sort. A nice way to test code in IPython is using the %timeit magic command. Magic commands are special functions built into IPython (not Python itself) to help with various things. The %timeit function repeats a function a couple of times and gives you an average measure for each iteration. This is a great way to test if you code execution speed has improved when changing steps. If you have solved it, [here](https://gist.github.com/dennisbakhuis/f6a4e5ad8666ef87c62bf1f4c282617b) is my solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I hope you had fun implementing the quicksort algorithm. It is still used quite often, of course with some optimizations. Did you notice the similarity with the pseudo-code?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you have any questions, feel free to contact me through [LinkedIn](https://www.linkedin.com/in/dennisbakhuis/)."
   ]
  },
  {
   "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}