{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Sort algorithms" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Warning: this topic is tough. \n", "
Read the algorithms several times and really work out examples with pencil on paper. I know that you are allergic to pencil and paper, but I had to do like this several decades ago in order to understand them (no, not because computers hadn't been invented at that time...) and I am sure it will help also you a lot." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Probably you have already written a sorting algorithm. It is not easy to come up with a strategy, but there are really many and I am sure that sooner or later in your life you had to sort something manually. The first algorithm which comes to my mind it this one: find the first element (be it the smallest if you are sorting numbers or the first in alphabetical order if you are dorting text) and put it in the new list in the first position. Repeat the process. \n", "

This algorithm has a complexity of $N + (N-1) + (N-2) + (N-3) + ... + 2 + 1$ comparisons which is $\\frac{N(N+1)}{2}$ comparisons, so approximately $N^2$ comparisons. Not bad! But we can do better." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Bubble Sort" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bubble sort algorithm works as if numbers were bubbles in the water. I do not know what is your experience with diving, but I assure you that the largest bubbles go up much faster than the small ones. We thus simulate this process going through the list and pushing the large numbers faster to the right, while automatically the small ones will end up on the left. Let's see how!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The algorithm goes through the full list and compares each element with the next one. E.g. we have\n", "
[4,7,2,5,1]\n", "
If the element is larger, it inverts the two elements. If the element is smaller, it leaves the elements as they are. \n", "

So in our example list we compare 4 with 7 and leave them as they are, then we compare 7 with 2 and swicth them obtaining [4,2,7,5,1] and then [4,2,5,7,1] and finally [4,2,5,1,7]. \n", "
After this first pass, you can clearly see that the largest element has arrived at the end of the list and thus we do not need to touch it anymore. \n", "

We repeat the same but this time going from the first element up to the second-last one (remember that the last one is already fine!). \n", "
Starting from [4,2,5,1,7] we get [2,4,5,1,7] and then [2,4,5,1,7] and finally [2,4,1,5,7] (remember that we arrive only to the second-last position).\n", "
After this second pass we will have the second-largest element which is in the second-last position of the list, so it's fine. \n", "

We go through the list a third time up to the third-last element and:\n", "
starting from [2,4,1,5,7] we remain with [2,4,1,5,7] and then [2,1,4,5,7]. Now also the 4 is in its right position.\n", "

Guess how does it go on? \n", "
starting from [2,1,4,5,7] we get [1,2,4,5,7]\n", "

Now we have only the first element, which does not need to be compared with anything." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's build the code. First we build a function which swicthes the elements of a list and then the real function. Pay attention that indexes in this code can be rather tricky." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n", "1\n", "2\n", "3\n", "[4, 2, 5, 1, 7]\n" ] } ], "source": [ "def switch(L,a,b):\n", " # this function switches a with b in L\n", " print(\"I am switching \",a,b,\" values: \" L[a],L[b])\n", " L[a],L[b]=L[b],L[a]\n", " # we do not need to return anything, our only scope is to change L\n", "\n", "def bubbleSort_firstPass(L):\n", " i=0\n", " while iL[i+1]:\n", " switch(L,i,i+1)\n", " i=i+1\n", " return L\n", "\n", "print(bubbleSort_firstPass([4,7,2,5,1]))" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "finish 4\n", "I compare 0 1\n", "I compare 1 2\n", "I compare 2 3\n", "I compare 3 4\n", "finish 3\n", "I compare 0 1\n", "I compare 1 2\n", "I compare 2 3\n", "finish 2\n", "I compare 0 1\n", "I compare 1 2\n", "finish 1\n", "I compare 0 1\n", "[1, 2, 4, 5, 7]\n" ] } ], "source": [ "def switch(L,a,b):\n", " # this function switches a with b in L\n", " L[a],L[b]=L[b],L[a]\n", "\n", "def bubbleSort(L):\n", " finish=len(L)-1\n", " while finish>0:\n", " print(\"finish \",finish)\n", " i=0\n", " while iL[i+1]:\n", " switch(L,i,i+1)\n", " i=i+1\n", " finish=finish-1\n", " return L\n", "\n", "print(bubbleSort([4,7,2,5,1]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Merge Sort" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Merge Sort is an algorithm that uses a **divide and conquer** strategy to be very efficient, invented by John Von Neumann in 1945. It starts from the observation that if you have two sorted lists, it is easy to combine them into a sorted one. You just go through the elements of both lists in parallel and choose which one is larger and add it to the final list." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Merge function" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Suppose that we have [2,6,8,9,10] and [3,5,6]. To merge them into a sorted common list, we keep an index of both lists: a=0 (which corresponds to 2) and b=0 (which corresponds to 3). We take the smallest one (2) and put it into a list and consequently increment a.\n", "

Now we have a=1 (6) and b=0 (3). The smallest one is 3, so we put it into a list and advance b.\n", "

Now we have a=1 (6) and b=1 (5). The smallest one is 5, so we put it into a list and advance b.\n", "

Now we have a=1 (6) and b=2 (6). The smallest one is any of the two, so we put it into a list and advance a or b, doesn't matter. Let's take b.\n", "

Now we have a=1 (6) and b is over!!! At this point we take the remaining part of the first list [6,8,9,10] and attach it to our final list." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Algorithm" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's start with the algorithm. Be ready to reverse your standard way of thinking because this is an algorithm which never sorts!!!\n", "

The algorithm first splits the list in two lists (divide) and analyses those two lists separately. \n", "
In our example [4,7,2,5,1] is split into [4,7,2] and [5,1].\n", "

Then each one is split into two lists which are anaysed separately. \n", "
So we have ( [4,7] and [2] ) , ( [5] and [1] )\n", "

Each one is split into two lists which are anaysed separately. \n", "
So we have ( ( [4] and [7] ) and [2] ) , ( [5] and [1] )\n", "

When we arrive at a list with only one element, that list is automatically sorted and we are happy (conquer). We can now use an appropriate join function to rejoin them:\n", "
Starting from: ( ( [4] and [7] ) and [2] ) , ( [5] and [1] )\n", "
we join [4] and [7] getting: ( [4,7] and [2] ) , ( [1,5] )\n", "
we join the things between parentheses getting: [2,4,7] , [1,5]\n", "
and finally we join the two lists getting: [1,2,4,5,7]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Easy, isn't it? :-)\n", "\n", "Please note that the algorithm never sorts anything! The only way in which it sorts is when joining two lists." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le's see another example depicted graphically!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's write the code. First of all we need a function which merges two ordered lists. Or better, if you look at the graphical example above, it joins two contiguous ordered pieces of the original list." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 4, 4, 6, 7, 7, 9, 5]\n" ] } ], "source": [ "def merge(L,left,mid,right):\n", " \n", " # this function merges lists from L. First list goes from left to mid included, second list goes from mid+1 to right included\n", " a=left\n", " b=mid+1\n", " R=[]\n", " while a<=mid and b<=right:\n", " if L[a]