{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Module 2, Practical 5\n", "\n", "In this practical we will work with sorting algorithms.\n", "\n", "## Sorting algorithms\n", "\n", "The basic principle of sorting algorithms is quite simple: \n", ">given an input sequence ($U$) of (at least partially) un-sorted elements $U=u_{1},u_{2}, ..., u_{n}$, output a new sequence $S = s_{1}, s_{2}, ... , s_{n}$ which is a permutation of the elements in $U$ such that $s_{1}\\leq s_{2}, ..., \\leq s_{n}$.\n", "\n", "Several sorting algorithms exist, the first one we will work with is **selection sort**.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Selection sort\n", "\n", "Selection sort is the simplest of the sorting algorithms. \n", "\n", "The idea of **selection sort** is that given $U=u_{1},u_{2},...,u_{n}$ the algorithm loops through all the elements of $U$, finds the minimum $u_m$ and places it at the beginning of the sequence $U$, swapping $u_{1}$ with $u_m$. At the next iteration, the algorithm continues looking for the minimum starting from $u_2$ and so on.\n", "\n", "If $U$ has $n$ elements, we need to perform the following two steps for each position $i=0,..,n-1$ in the list:\n", "\n", "1. (argmin) Find index of the minimum element in the sublist $U[i:]$, let's call it $min$ (i.e. $u_{min} = min(U[i:])$);\n", "\n", "2. (swap) Swap $u_{min}$ with $u_i$;\n", "\n", "A reminder on how selection sort works is shown in this picture taken from the lecture slides. Yellow cells are the minimum found at each iteration, while orange cells are those already sorted by previous iterations.\n", "\n", "![](images/selection_sort.png)\n", "\n", "\n", "A good implementation of this sorting algorithm has complexity $O(n^2)$, where $n$ is the number of elements in the list to sort." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### A base class for sorting algorithms\n", "\n", "Implement a base class, ```SortingAlgorithm```, that has the following attributes:\n", "\n", "- ```data``` (the actual data to sort) \n", "- ```operations``` (initialized to 0) that counts how many swaps have been done to perform the sorting\n", "- ```comparisons``` (initialized to 0) that counts how many comparisons have been done \n", "- ```verbose``` a boolean (default= True) that is used to decide if the method should report what is happening at each step and some stats or not. \n", "\n", "The class has one method, ```sort```, that implements the sort algorithm (empty for the base class)" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "<__main__.SortingAlgorithm object at 0x7f1da5dd6530>\n" ] }, { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "Cell \u001b[0;32mIn[1], line 22\u001b[0m\n\u001b[1;32m 20\u001b[0m sa \u001b[38;5;241m=\u001b[39m SortingAlgorithm([])\n\u001b[1;32m 21\u001b[0m \u001b[38;5;28mprint\u001b[39m(sa)\n\u001b[0;32m---> 22\u001b[0m \u001b[43msa\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43msort\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\n", "Cell \u001b[0;32mIn[1], line 18\u001b[0m, in \u001b[0;36mSortingAlgorithm.sort\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 17\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m\u001b[38;5;250m \u001b[39m\u001b[38;5;21msort\u001b[39m(\u001b[38;5;28mself\u001b[39m):\n\u001b[0;32m---> 18\u001b[0m \u001b[38;5;28;01mraise\u001b[39;00m \u001b[38;5;167;01mNotImplementedError\u001b[39;00m\n", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "class SortingAlgorithm:\n", " def __init__(self, data, verbose = True):\n", " self.data = data\n", " self.comparisons = 0\n", " self.operations = 0\n", " self.verbose = verbose\n", " \n", " def getData(self):\n", " return self.data\n", " \n", " def getOperations(self):\n", " return self.operations\n", " \n", " def getComparisons(self):\n", " return self.comparisons\n", "\n", " def sort(self):\n", " raise NotImplementedError\n", "\n", "sa = SortingAlgorithm([])\n", "print(sa)\n", "sa.sort()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Please, note that the method ```sort``` raises an exception ```NotImplementedError```. Exceptions are used to detect and manage errors occurred during execution. Exceptions can be raised thorough the instruction ```raise``` and they can be captured by the construct ```try```:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OS error: [Errno 2] No such file or directory: 'myfile.txt'\n" ] } ], "source": [ "import sys\n", "\n", "try:\n", " f = open('myfile.txt')\n", " s = f.readline()\n", " i = int(s.strip())\n", "except OSError as err:\n", " # code executed if an exception OSError is raised during the execution of the code in the try instruction block\n", " print(\"OS error: {0}\".format(err))\n", "except ValueError:\n", " # exception ValueError\n", " print(\"Could not convert data to an integer.\")\n", "except:\n", " # general exception\n", " print(\"Unexpected error:\", sys.exc_info()[0])\n", " raise\n", "else:\n", " # optional, collects code that has to be executed ONLY if no exceptions are raised\n", " f.close()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In our praticals we will not use extensively Python exceptions. For a detailed explanation on how to manage errors and exceptions in Python, \n", "we refer to the official language tutorial [https://docs.python.org/3/tutorial/errors.html](https://docs.python.org/3/tutorial/errors.html).\n", "\n", "### Exercise (implementation)\n", "\n", "1. Implement a class SelectionSort that inherits from the base class, with the following attributes: \n", "- ```data``` (the actual data to sort) \n", "- ```operations``` (initialized to 0) that counts how many swaps have been done to perform the sorting\n", "- ```comparisons``` (initialized to 0) that counts how many comparisons have been done \n", "- ```verbose``` a boolean (default= True) that is used to decide if the method should report what is happening at each step and some stats or not. \n", "\n", "The class implements the sort method, ```sort```, that implements the selection sort algorithm (two more *private* methods might be needed to compute ```swap``` and ```argmin``` -- see description above). \n", "\n", "Once you implemented the class, test it with some data like:\n", "```\n", "[7, 5, 10, -11 ,3, -4, 99, 1]\n", "```\n", "\n", "
Show/Hide Implementation\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Swapping position 0 with 3\n", "Swapping position 1 with 5\n", "Swapping position 2 with 7\n", "Swapping position 3 with 4\n", "Swapping position 4 with 5\n", "Swapping position 6 with 7\n", "[-11, -4, 1, 3, 5, 7, 10, 99]\n", "\n", "Number of elements: 1000\n", "Number of comparisons: 499500\n", "Number of swaps: 995\n", "\n", "Number of elements: 2000\n", "Number of comparisons: 1999000\n", "Number of swaps: 1991\n", "\n", "Sorting test passed? True\n" ] } ], "source": [ "import random\n", "\n", "class SortingAlgorithm:\n", " def __init__(self, data, verbose = True):\n", " self.data = data\n", " self.comparisons = 0\n", " self.operations = 0\n", " self.verbose = verbose\n", " \n", " def getData(self):\n", " return self.data\n", " \n", " def getOperations(self):\n", " return self.operations\n", " \n", " def getComparisons(self):\n", " return self.comparisons\n", "\n", " def sort(self):\n", " raise NotImplementedError\n", "\n", "class SelectionSort(SortingAlgorithm):\n", " \n", " def __swap(self, i, j):\n", " \"\"\"\n", " swaps elements i and j in data.\n", " \"\"\"\n", " if(i != j): #no point in swapping if i==j\n", " if self.verbose:\n", " print(\"Swapping position {} with {}\".format(i,j))\n", " self.operations += 1\n", " tmp = self.data[i]\n", " self.data[i] = self.data[j]\n", " self.data[j] = tmp\n", " \n", " def __argmin(self, i):\n", " \"\"\"\n", " returns the index of the smallest element of\n", " self.__data[i:]\n", " \"\"\"\n", " mpos = i\n", " N = len(self.data)\n", " minV = self.data[mpos]\n", " for j in range(i + 1, N):\n", " if self.data[j] < minV:\n", " mpos = j\n", " minV = self.data[j]\n", " # keep track of what was done\n", " self.comparisons += 1\n", " \n", " return mpos\n", " \n", " def sort(self):\n", " self.comparisons = 0\n", " self.operations = 0\n", "\n", " for i in range(len(self.data) - 1):\n", " j = self.__argmin(i)\n", " self.__swap(i, j) \n", "\n", "\n", "if __name__ == \"__main__\":\n", " # this code is executed when SelectionSort is directly executed... \n", " # https://docs.python.org/3/library/__main__.html\n", " d = [7, 5, 10, -11 ,3, -4, 99, 1]\n", " selSorter = SelectionSort(d, verbose = True)\n", " selSorter.sort()\n", " print(d)\n", " d = []\n", "\n", " for i in range(0,1000):\n", " d.append(random.randint(0,1000))\n", " selSorter = SelectionSort(d, verbose = False)\n", " selSorter.sort()\n", " print(\"\\nNumber of elements: {}\".format(len(d)))\n", " print(\"Number of comparisons: {}\".format(selSorter.getComparisons()))\n", " print(\"Number of swaps: {}\".format(selSorter.getOperations()))\n", " \n", " d = []\n", " for i in range(0,2000):\n", " d.append(random.randint(0,1000))\n", " selSorter = SelectionSort(d, verbose = False)\n", " selSorter.sort()\n", " print(\"\\nNumber of elements: {}\".format(len(d)))\n", " print(\"Number of comparisons: {}\".format(selSorter.getComparisons()))\n", " print(\"Number of swaps: {}\".format(selSorter.getOperations()))\n", " \n", " test = True\n", " for el in range(0,len(d)-1):\n", " test = test and (d[el]<= d[el+1])\n", " print(\"\\nSorting test passed? {}\".format(test))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [SelectionSort.py](sorting_algos/SelectionSort.py)\n", "\n", "
\n", "\n", "## Insertion sort\n", "\n", "The second sorting algorithm we will see is **insertion sort**. As for selection sort, this algorithm builds the solution one element at a time. It is not a very efficient sorting algorithm but it is quite simple and has several advantages. \n", "Indeed, it is an *in place* algorithm (i.e. it does not need to copy the array to sort it therefore it is easy on memory), and it can be efficient for *nearly sorted* lists. *This is the algorithm that people use when sorting a deck of cards.*\n", "\n", "The algorithm builds a sorted list step by step. At each iteration it removes one element from the list, placing it in the correct position within the growing sorted list. \n", "\n", "The algorithm makes use of two indexes: $i$ moving on the un-sorted part of the list and $j$, on the growing sorted part of the list. The index $i$ starts from 1 and loops up to the end of the list, while $j$ starts from $i$ at each iteration and goes down to finding the place where the element at index $i$ should go in the sorted list, pushing the other elements up while finding the right place. \n", "An element at position $h$ is pushed-up by copying $u_h$ to position $h+1$. \n", "\n", "\n", "Given an unsorted list $U = u_0, u_1, ..., u_n$:\n", "\n", "For each $i$ from 1 to $l = length(list)$:\n", "\n", "1. get $u_i$ and store it in a temporary variable $temp$; \n", "\n", "2. for $j = i$,...,0 push $u_{j-1}$ to position $j$ until $temp$ > $u_{j-1}$. If $j$ exists such that $temp$ < $u_j$, place $temp$ at position $j$, otherwise place $temp$ in position $0$. \n", "\n", "\n", "A graphical representation of the algorithm (from the lecture slides) follows:\n", "\n", "![](images/insertion_sort1.png)\n", "![](images/insertion_sort2.png)\n", "![](images/insertion_sort3.png)\n", "\n", "\n", "The worst case complexity of this algorithm is $O(n^2)$, with $n$ being the number of elements in the list. If one element is no more than $k$ places away from its place in the sorted array, the real complexity goes to $O(kn)$. *The cost of the algorithm is therefore dependent on the sorting of the input list.*\n", "\n", "Another graphical representation of the algorithm follows (from geeksforgeeks.org). At each iteration, red boxes are pushed to the right to make room for the green element. \n", "\n", "![](images/ins_sort_pic.png)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise (implementation)\n", "\n", "2. Implement a class ```InsertionSort``` that inherits from the base class and has the following attributes: \n", "- ```data``` (the actual data to sort)\n", "- ```operations``` (initialized to 0) that counts how many swaps (movements of data to the left) have been done to perform the sorting\n", "- ```comparisons``` (initialized to 0) that counts how many comparisons have been done \n", "- ```verbose```, a boolean (default= True) used to decide if the method should report what is happening at each step and some stats or not \n", "\n", "The class should implement the ```sort``` method.\n", "\n", "
Show/Hide Implementation\n" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "It. 1: [5, 7, 10, -11, 3, -4, 99, 1] comp: 1 push+place:2\n", "It. 2: [5, 7, 10, -11, 3, -4, 99, 1] comp: 2 push+place:3\n", "It. 3: [-11, 5, 7, 10, 3, -4, 99, 1] comp: 5 push+place:7\n", "It. 4: [-11, 3, 5, 7, 10, -4, 99, 1] comp: 9 push+place:11\n", "It. 5: [-11, -4, 3, 5, 7, 10, 99, 1] comp: 14 push+place:16\n", "It. 6: [-11, -4, 3, 5, 7, 10, 99, 1] comp: 15 push+place:17\n", "It. 7: [-11, -4, 1, 3, 5, 7, 10, 99] comp: 21 push+place:23\n", "[-11, -4, 1, 3, 5, 7, 10, 99]\n", "\n", "Number of comparisons: 21\n", "Number of push-ups+place: 23\n", "[-11, -4, 1, 3, 5, 7, 10, 99]\n", "\n", "Number of elements: 1000\n", "Number of comparisons: 251526\n", "Number of push-ups+place: 251533\n", "\n", "Number of elements: 2000\n", "Number of comparisons: 994483\n", "Number of push-ups+place: 994488\n", "\n", "Sorting test passed? True\n" ] } ], "source": [ "import random\n", "\n", "class SortingAlgorithm:\n", " def __init__(self, data, verbose = True):\n", " self.data = data\n", " self.comparisons = 0\n", " self.operations = 0\n", " self.verbose = verbose\n", " \n", " def getData(self):\n", " return self.data\n", " \n", " def getOperations(self):\n", " return self.operations\n", " \n", " def getComparisons(self):\n", " return self.comparisons\n", "\n", " def sort(self):\n", " raise NotImplementedError\n", "\n", "class InsertionSort(SortingAlgorithm):\n", "\n", " def sort(self):\n", " self.comparisons = 0\n", " self.operations = 0\n", "\n", " for i in range(1, len(self.data)):\n", " temp = self.data[i]\n", " j = i\n", " while j > 0 and self.data[j-1] > temp:\n", " self.data[j] = self.data[j - 1]\n", " self.operations += 1\n", " self.comparisons += 1\n", " j = j - 1\n", "\n", " self.data[j] = temp\n", " self.operations += 1\n", " if j > 0:\n", " self.comparisons += 1\n", " if self.verbose:\n", " print(\"It. {}: {} comp: {} push+place:{}\".format(i,\n", " self.data,\n", " self.comparisons,\n", " self.operations\n", " ))\n", "\n", " if self.verbose:\n", " print(self.data)\n", " print(\"\\nNumber of comparisons: {}\".format(self.comparisons))\n", " print(\"Number of push-ups+place: {}\".format(self.operations))\n", "\n", "\n", "if __name__ == \"__main__\":\n", " # this code is executed when SelectionSort is directly executed... \n", " # https://docs.python.org/3/library/__main__.html\n", " d = [7, 5, 10, -11 ,3, -4, 99, 1]\n", " insSorter = InsertionSort(d, verbose = True)\n", " insSorter.sort()\n", " print(d)\n", "\n", " d = []\n", " for i in range(0,1000):\n", " d.append(random.randint(0,1000))\n", " insSorter = InsertionSort(d, verbose = False)\n", " insSorter.sort()\n", " print(\"\\nNumber of elements: {}\".format(len(d)))\n", " print(\"Number of comparisons: {}\".format(insSorter.getComparisons()))\n", " print(\"Number of push-ups+place: {}\".format(insSorter.getOperations()))\n", "\n", " d = []\n", " for i in range(0,2000):\n", " d.append(random.randint(0,1000))\n", " insSorter = InsertionSort(d, verbose = False)\n", " insSorter.sort()\n", " print(\"\\nNumber of elements: {}\".format(len(d)))\n", " print(\"Number of comparisons: {}\".format(insSorter.getComparisons()))\n", " print(\"Number of push-ups+place: {}\".format(insSorter.getOperations()))\n", " \n", " test = True\n", " for el in range(0,len(d)-1):\n", " test = test and (d[el]<= d[el+1])\n", " print(\"\\nSorting test passed? {}\".format(test))\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [InsertionSort.py](sorting_algos/InsertionSort.py)\n", "\n", "
\n", "\n", "## Merge sort and Quick sort\n", "\n", "These are *divide et impera* algorithms (latin, *divide and conquer* in English) and they work by:\n", "\n", "1. *dividing* the original problem in smaller problems (based on parameters such as the size of the input list);\n", "2. recursively *solving the smaller problems* (splitting them until the minimum unit -- the base case -- is reached and solved);\n", "3. combining the partial results in the final solution.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Merge sort\n", "\n", "The idea of **merge sort** is that given an unsorted list $U=u_{1},u_{2},...,u_{n}$ the $MergeSort$ procedure:\n", "\n", "1. breaks the list $U$ in two similarly sized lists (if the size is odd, the first list is always one element bigger than the other); \n", "2. calls $MergeSort$ recursively on the two sublists, until we have sublists of one element only, which are ordered by definition;\n", "3. merges the two already sorted sublists in a sorted list.\n", "\n", "The base-case of this algorithm is that lists with size $0$ or $1$ are ordered and are ready to be merged, therefore the algorithm keeps splitting partial lists in two sublists until these reach the length $0$ or $1$. At that point the two lists are merged into a bigger **sorted** list by using a **merge** method. \n", "This is done recursively until only one list is obtained, which is the final result.\n", "\n", "The algorithm makes use of three methods:\n", "\n", "1. (```merge```): gets two sorted lists and produces a sorted list that contains all the elements of the two lists. This method builds the return list by getting the minimum element of the two lists, \"removing\" it from the corresponding list and appending it to the list with the result. \"removal\" can be done by using two indexes pointing to the smallest elements of each of the two (sub)lists and incrementing the index of the minimum of the two (i.e. the element that is also copied to the result list);\n", "\n", "2. (```recursiveMergeSort```): gets an unordered (sub)list, the index of the beginning of the list, and the index of the end of the list. It recursively splits it in two halves until it reaches lists with length $0$ or $1$ - at that point it starts merging pairs of sorted lists to build the result; \n", "\n", "2. (```mergeSort```) gets a list and applies the recursiveMergeSort method to it starting from position $0$ to $len - 1$.\n", "\n", "A reminder on how merge sort works is shown here (from the lecture slides). The first part is the splitting of the initial list into smaller lists, until the base level is reached with ```recursiveMergeSort```. \n", "\n", "![](images/merge_sort1.png)\n", "\n", "This second picture shows how the sorted list can be reconstructed by applying the ```merge``` method to pairs of sorted lists.\n", "\n", "![](images/merge_sort2.png)\n", "\n", "\n", "A good implementation of this sorting algorithm has complexity $O(n log (n))$ where $n$ is the number of elements in the list to sort. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise (Implementation)\n", "\n", "3. Implement a class ```MergeSort``` that inherits from the base class and has the following attributes: \n", "- ```data``` (the actual data to sort)\n", "- ```operations``` (initialized to 0) that counts how many recursive calls have been done to perform the sorting\n", "- ```comparisons``` (initialized to 0) that counts how many comparisons have been done\n", "- ```time``` attribute that keeps track of the elapsed time (hint: use the Python ```time``` module) \n", "- ```verbose``` a boolean (default= True) that is used to decide if the method should report what is happening at each step and some stats or not. \n", "\n", "The class implements the ```sort``` method that implements the merge sort algorithm (two more *private* methods might be needed to compute ```merge``` and ```recursiveMergeSort``` -- see description above). \n", "\n", "Once you implemented the class you can test it with some data like:\n", "```\n", "[7, 5, 10, -11 ,3, -4, 99, 1]\n", "```\n", "\n", "
Show/Hide Implementation\n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Executing recursive merge sort(0,6)...\n", "Executing recursive merge sort(0,3)...\n", "Executing recursive merge sort(0,1)...\n", "Executing recursive merge sort(0,0)...\n", "Executing recursive merge sort(1,1)...\n", "Executing merge(0,1,0)...\n", "Executing recursive merge sort(2,3)...\n", "Executing recursive merge sort(2,2)...\n", "Executing recursive merge sort(3,3)...\n", "Executing merge(2,3,2)...\n", "Executing merge(0,3,1)...\n", "Executing recursive merge sort(4,6)...\n", "Executing recursive merge sort(4,5)...\n", "Executing recursive merge sort(4,4)...\n", "Executing recursive merge sort(5,5)...\n", "Executing merge(4,5,4)...\n", "Executing recursive merge sort(6,6)...\n", "Executing merge(4,6,5)...\n", "Executing merge(0,6,3)...\n", "[-11, -4, 3, 5, 7, 10, 99]\n", "\n", "Number of elements: 1000\n", "Number of comparisons: 8698\n", "Number of swaps: 1999\n", "In 0.0025s\n", "\n", "Number of elements: 2000\n", "Number of comparisons: 19427\n", "Number of recursions: 3999\n", "In 0.0059s\n", "\n", "Sorting test passed? True\n" ] } ], "source": [ "import random\n", "import time\n", "\n", "class SortingAlgorithm:\n", " def __init__(self, data, verbose = True):\n", " self.data = data\n", " self.comparisons = 0\n", " self.operations = 0\n", " self.verbose = verbose\n", " \n", " def getData(self):\n", " return self.data\n", " \n", " def getOperations(self):\n", " return self.operations\n", " \n", " def getComparisons(self):\n", " return self.comparisons\n", "\n", " def sort(self):\n", " raise NotImplementedError\n", "\n", "class MergeSort(SortingAlgorithm):\n", " def __init__(self,data, verbose = True):\n", " self.data = data\n", " self.time = 0\n", " self.comparisons = 0\n", " self.operations = 0\n", " self.verbose = verbose\n", " \n", " def getTime(self):\n", " return(self.time)\n", " \n", " def __merge(self, first, last, mid):\n", " if self.verbose:\n", " print(\"Executing merge({},{},{})...\".format(first,last,mid))\n", " tmp = []\n", " i = first\n", " j = mid + 1\n", " while i <= mid and j <= last:\n", " if self.data[i] < self.data[j]:\n", " tmp.append(self.data[i])\n", " i += 1\n", " else:\n", " tmp.append(self.data[j])\n", " j += 1\n", " self.comparisons += 1\n", " while i <= mid:\n", " tmp.append(self.data[i])\n", " i += 1\n", " self.data[first:first+len(tmp)] = tmp\n", " \n", " def __recursiveMergeSort(self, first, last):\n", " if self.verbose:\n", " print(\"Executing recursive merge sort({},{})...\".format(first,last))\n", "\n", " self.operations += 1\n", " if first < last:\n", " mid = (first + last)//2 #<- index so mid+1 elements go in the first sublist!!! \n", " self.__recursiveMergeSort(first, mid)\n", " self.__recursiveMergeSort(mid +1, last)\n", " self.__merge(first,last,mid)\n", " \n", " def sort(self):\n", " self.comparisons = 0\n", " self.operations = 0\n", " start = time.time()\n", " self.__recursiveMergeSort(0,len(self.data)-1) \n", " end = time.time()\n", " self.time = end - start\n", "\n", "\n", "\n", "if __name__ == \"__main__\":\n", " # this code is executed when SelectionSort is directly executed... \n", " # https://docs.python.org/3/library/__main__.html\n", " d = [7, 5, 10, -11 ,3, -4, 99]\n", " mergeSorter = MergeSort(d, verbose = True)\n", " mergeSorter.sort()\n", " print(d)\n", "\n", " d = []\n", " for i in range(0,1000):\n", " d.append(random.randint(0,1000))\n", " mergeSorter = MergeSort(d, verbose = False)\n", " mergeSorter.sort()\n", " print(\"\\nNumber of elements: {}\".format(len(d)))\n", " print(\"Number of comparisons: {}\".format(mergeSorter.getComparisons()))\n", " print(\"Number of swaps: {}\".format(mergeSorter.getOperations()))\n", " print(\"In {:.4f}s\".format(mergeSorter.getTime()))\n", " \n", " d = []\n", " for i in range(0,2000):\n", " d.append(random.randint(0,1000))\n", " mergeSorter = MergeSort(d, verbose = False)\n", " mergeSorter.sort()\n", " print(\"\\nNumber of elements: {}\".format(len(d)))\n", " print(\"Number of comparisons: {}\".format(mergeSorter.getComparisons()))\n", " print(\"Number of recursions: {}\".format(mergeSorter.getOperations()))\n", " print(\"In {:.4f}s\".format(mergeSorter.getTime()))\n", " \n", " test = True\n", " for el in range(0,len(d)-1):\n", " test = test and (d[el]<= d[el+1])\n", " print(\"\\nSorting test passed? {}\".format(test))\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [MergeSort.py](sorting_algos/MergeSort.py)\n", "\n", "
\n", "\n", "### Quick sort\n", "\n", "The last sorting algorithm we will see is **quick sort**. As for merge sort, this algorithm follows the *divide et impera* paradigm and its easiest implementation is recursive.\n", "\n", "The idea is that, given an unsorted list $U = u_1, ..., u_n$, at each step a **pivot** $j$ is selected and elements are rearranged in a way that all $u_i$ such that $u_i < u_j$ are placed at the left of $u_j$ and all $u_h$ such that $u_h$ > $u_j$ are placed to the right of $u_j$.\n", "\n", "This *divide and conquer* approach works like that:\n", "\n", "1. (*divide*) partition the initial list $U = u_1, .., u_n$ in two non-empty sublists (reordering the elements) such that all the elements in the first sublist are lower than the elements in the second. The pivot element $u_j$ is such that all the elements $u_i$ for $1 \\leq i \\lt j$ are lower than $u_j$ and all $u_k$ for $k > j$ are higher than $u_j$;\n", "2. (*conquer*) each sublist is recurisvely partitioned in two sublists, repeating until single elements are reached;\n", "3. (*recombine*) nothing is left to do to recombine the results.\n", "\n", "A graphical representation of the algorithm follows (red elements are the pivot of each sublist):\n", "\n", "![](images/quicksort.png)\n", "\n", "\n", "The algorithm makes use of the following methods:\n", "\n", "1. ```pivot```: gets the list, a ```start``` and ```end``` index, sets the first element as **pivot** and reorders all the elements in the list from ```start``` to ```end``` in such a way that all the elements to the left of the pivot (i.e. having index lower) are smaller than the pivot and all the elements to the right (i.e. with index higher) are bigger than the pivot. The function returns the index of the pivot;\n", "\n", "2. ```swap```: gets two indexes and swaps their values;\n", "\n", "3. ```recursiveQuickSort```: gets an unordered (sub)list, with ```start``` and ```end``` positions and finds the pivot and recursively applies the same procedure to the sublists to the left and right of the pivot;\n", "\n", "3. ```quickSort```: gets an unordered list and applies the recursive quick sort procedure to it.\n", "\n", "The pivot method is shown below (from lecture slides). The pivot is initially set to the first element of the sublist, then all the elements in the interval ```start``` - ```end``` are compared to it (using an index $i$) and placed right after the pivot if smaller (updating an index $j$ on where the pivot should go at the end of the procedure), left untouched otherwise. At the end the pivot is moved to position $j$. The pivot is yellow and moved elements are pink:\n", "\n", "![](images/pivot.png)\n", "\n", "![](images/pivot_1.png)\n", "\n", "Another graphical representation follows. This picture highlights the selection of pivots (red), their placing after the (```pivot```) method (green) and the split of the two sublists in correspondence of the placed pivot. \n", "\n", "![](images/quick_sort1.png)\n", "\n", "The average case complexity of the quick sort algorithm is $O(n log n)$ with $n$ being the number of elements in the list. The worst case complexity is $O(n^2)$ which is worse than merge sort's $O(n log n)$. In general, however, it performs better than merge sort." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise (Implementation)\n", "\n", "4. Implement a class ```QuickSort``` that inherits from the base class and has the following attributes: \n", "- ```data``` (the actual data to sort)\n", "- ```operations``` (initialized to 0) that counts how many swaps (movements of data to the left) have been done to perform the sorting\n", "- ```comparisons``` (initialized to 0) that counts how many comparisons have been done \n", "- ```verbose``` a boolean (default= True) that is used to decide if the method should report what is happening at each step and some stats or not. \n", "\n", "The class implements the method called ```sort``` that implements the quick sort algorithm (which will use the *private* methods ```pivot```, ```swap``` and ```recQuickSort```-- see description above). \n", "\n", "How long does it take with a list of 10,000 elements? With 300,000?\n", "\n", "
Show/Hide Implementation\n" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Number of elements: 1000\n", "Number of comparisons: 12505\n", "Number of push-ups+place: 4838\n", "In 0.0049s\n", "\n", "Number of elements: 10000\n", "Number of comparisons: 176168\n", "Number of push-ups+place: 63565\n", "In 0.0323s\n", "\n", "Number of elements: 300000\n", "Number of comparisons: 48809884\n", "Number of push-ups+place: 1864031\n", "In 3.6578s\n", "\n", "Sorting test passed? True\n" ] } ], "source": [ "import random\n", "import time\n", "\n", "class SortingAlgorithm:\n", " def __init__(self, data, verbose = True):\n", " self.data = data\n", " self.comparisons = 0\n", " self.operations = 0\n", " self.verbose = verbose\n", " \n", " def getData(self):\n", " return self.data\n", " \n", " def getOperations(self):\n", " return self.operations\n", " \n", " def getComparisons(self):\n", " return self.comparisons\n", "\n", " def sort(self):\n", " raise NotImplementedError\n", "\n", "class QuickSort(SortingAlgorithm):\n", " def __init__(self,data, verbose = True):\n", " self.data = data\n", " self.time = 0\n", " self.comparisons = 0\n", " self.operations = 0\n", " self.verbose = verbose\n", "\n", " def getTime(self):\n", " return(self.time)\n", "\n", " def __swap(self, i,j):\n", " \"\"\"swaps elements at positions i and j\"\"\"\n", " if(i != j): # no point in swapping if i==j\n", " self.operations += 1\n", " tmp = self.data[i]\n", " self.data[i] = self.data[j]\n", " self.data[j] = tmp\n", "\n", " def __pivot(self, start, end):\n", " \"\"\"gets the pivot and swaps elements in [start, end]\n", " accordingly\"\"\"\n", " p = self.data[start]\n", " j = start\n", "\n", " for i in range(start + 1, end + 1):\n", " self.comparisons += 1\n", " if self.data[i] < p:\n", " j = j + 1\n", " self.__swap(i, j)\n", "\n", " self.__swap(start,j)\n", "\n", " return j\n", "\n", " def __recQuickSort(self, start, end):\n", " \"\"\"gets the pivot and recursively applies\n", " itself on the left and right sublists\n", " \"\"\"\n", " if start < end:\n", " #GET THE PIVOT\n", " j = self.__pivot(start, end)\n", "\n", " self.__recQuickSort(start, j - 1)\n", "\n", " self.__recQuickSort(j + 1, end)\n", "\n", " def sort(self):\n", " self.comparisons = 0\n", " self.operations = 0\n", " start = time.time()\n", " self.__recQuickSort(0, len(self.data) - 1)\n", " end = time.time()\n", " self.time = end - start\n", "\n", "\n", "if __name__ == \"__main__\":\n", " # this code is executed when SelectionSort is directly executed... \n", " # https://docs.python.org/3/library/__main__.html\n", " d = [7, 3, 10, -11 ,5, -4, 99, 1]\n", " qkSorter = QuickSort(d, verbose = True)\n", " qkSorter.sort()\n", " d = []\n", "\n", " for i in range(0,1000):\n", " d.append(random.randint(0,1000))\n", " qkSorter = QuickSort(d, verbose = False)\n", " qkSorter.sort()\n", " print(\"\\nNumber of elements: {}\".format(len(d)))\n", " print(\"Number of comparisons: {}\".format(qkSorter.getComparisons()))\n", " print(\"Number of push-ups+place: {}\".format(qkSorter.getOperations()))\n", " print(\"In {:.4f}s\".format(qkSorter.getTime()))\n", "\n", " d = []\n", " for i in range(0,10000):\n", " d.append(random.randint(0,1000))\n", " qkSorter = QuickSort(d, verbose = False)\n", " qkSorter.sort()\n", " print(\"\\nNumber of elements: {}\".format(len(d)))\n", " print(\"Number of comparisons: {}\".format(qkSorter.getComparisons()))\n", " print(\"Number of push-ups+place: {}\".format(qkSorter.getOperations()))\n", " print(\"In {:.4f}s\".format(qkSorter.getTime()))\n", " test = True\n", "\n", " d = []\n", " for i in range(0,300000):\n", " d.append(random.randint(0,1000))\n", " qkSorter = QuickSort(d, verbose = False)\n", " qkSorter.sort()\n", " print(\"\\nNumber of elements: {}\".format(len(d)))\n", " print(\"Number of comparisons: {}\".format(qkSorter.getComparisons()))\n", " print(\"Number of push-ups+place: {}\".format(qkSorter.getOperations()))\n", " print(\"In {:.4f}s\".format(qkSorter.getTime()))\n", " test = True\n", "\n", " for el in range(0,len(d)-1):\n", " test = test and (d[el]<= d[el+1])\n", " print(\"\\nSorting test passed? {}\".format(test))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [QuickSort.py](sorting_algos/QuickSort.py)\n", "\n", "
\n", "\n", "## Exercise (algorithm benchmark)\n", "\n", "5. Write some python code to test the performance of selection sort, insertion sort, merge sort and quick sort with different lists of incremental size. Test the algorithms, reporting stats and running time. \n", "\n", "To complete the exercise, you will need to add the time measurement feature to the base ```SortingAlgorithm``` class and modify all four child classes accordingly. \n", "\n", "Finally, challenge them with the following arrays:\n", "\n", "- list(range(5000))\n", "\n", "- c = list(range(5000)); c.sort(reverse=True) (reverse-sorted, worst case scenario)\n", "\n", "- a = list(range(1000)); b = list(range(1000,2000)); b.sort(reverse=True); sort(a+b)\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test with a list of 10 elements...\n", "TestList:\n", "[8078, 4403, -3266, -433, -6566, -3205, -1978, -1743, 5538, 1272]\n", "TestList1:\n", "[8078, 4403, -3266, -433, -6566, -3205, -1978, -1743, 5538, 1272]\n", "TestList2:\n", "[8078, 4403, -3266, -433, -6566, -3205, -1978, -1743, 5538, 1272]\n", "TestList3:\n", "[8078, 4403, -3266, -433, -6566, -3205, -1978, -1743, 5538, 1272]\n", "Outputs:\n", "[-6566, -3266, -3205, -1978, -1743, -433, 1272, 4403, 5538, 8078]\n", "[-6566, -3266, -3205, -1978, -1743, -433, 1272, 4403, 5538, 8078]\n", "[-6566, -3266, -3205, -1978, -1743, -433, 1272, 4403, 5538, 8078]\n", "[-6566, -3266, -3205, -1978, -1743, -433, 1272, 4403, 5538, 8078]\n", "Test with 10 elements\n", "Insertion sort:\n", "Number of comparisons: 28\n", "Number of operations: 31\n", "In 0.0000s\n", "Selection sort:\n", "Number of comparisons: 45\n", "Number of operations: 17\n", "In 0.0000s\n", "Merge sort:\n", "Number of comparisons: 11\n", "Number of operations: 19\n", "In 0.0001s\n", "Quick sort:\n", "Number of comparisons: 29\n", "Number of operations: 31\n", "In 0.0000s\n", "#############\n", "Test with a list of 5000 elements...\n", "Test with 5000 elements\n", "Insertion sort:\n", "Number of comparisons: 4999\n", "Number of operations: 4999\n", "In 0.0018s\n", "Selection sort:\n", "Number of comparisons: 12497500\n", "Number of operations: 4999\n", "In 0.8285s\n", "Merge sort:\n", "Number of comparisons: 32004\n", "Number of operations: 9999\n", "In 0.0073s\n", "Quick sort:\n", "Number of comparisons: 12497500\n", "Number of operations: 4999\n", "In 0.8164s\n", "#############\n", "Test with a list of 5000 elements in reverse order...\n", "Test with 5000 elements\n", "Insertion sort:\n", "Number of comparisons: 12497500\n", "Number of operations: 12502499\n", "In 1.7834s\n", "Selection sort:\n", "Number of comparisons: 12497500\n", "Number of operations: 7499\n", "In 0.8580s\n", "Merge sort:\n", "Number of comparisons: 0\n", "Number of operations: 9999\n", "In 0.0059s\n", "Quick sort:\n", "Number of comparisons: 12497500\n", "Number of operations: 6254999\n", "In 1.8754s\n", "#############\n", "Test with a list of 2000 elements, with last half in reverse order...\n", "Test with 2000 elements\n", "Insertion sort:\n", "Number of comparisons: 501499\n", "Number of operations: 501499\n", "In 0.0876s\n", "Selection sort:\n", "Number of comparisons: 1999000\n", "Number of operations: 2499\n", "In 0.1682s\n", "Merge sort:\n", "Number of comparisons: 6044\n", "Number of operations: 3999\n", "In 0.0019s\n", "Quick sort:\n", "Number of comparisons: 1999000\n", "Number of operations: 251999\n", "In 0.1513s\n" ] } ], "source": [ "import random\n", "import sys\n", "import time\n", "\n", "class SortingAlgorithm:\n", " def __init__(self, data, verbose = True):\n", " self.data = data\n", " self.comparisons = 0\n", " self.operations = 0\n", " self.time = 0 # novel addition!\n", " self.verbose = verbose\n", " \n", " def getData(self):\n", " return self.data\n", " \n", " def getOperations(self):\n", " return self.operations\n", " \n", " def getComparisons(self):\n", " return self.comparisons\n", "\n", " def getTime(self):\n", " return(self.time) # novel addition!\n", "\n", " def sort(self):\n", " raise NotImplementedError\n", "\n", "\n", "class SelectionSort(SortingAlgorithm):\n", " \n", " def __swap(self, i, j):\n", " \"\"\"\n", " swaps elements i and j in data.\n", " \"\"\"\n", " if(i != j): #no point in swapping if i==j\n", " if self.verbose:\n", " print(\"Swapping position {} with {}\".format(i,j))\n", " self.operations += 1\n", " tmp = self.data[i]\n", " self.data[i] = self.data[j]\n", " self.data[j] = tmp\n", " \n", " def __argmin(self, i):\n", " \"\"\"\n", " returns the index of the smallest element of\n", " self.__data[i:]\n", " \"\"\"\n", " mpos = i\n", " N = len(self.data)\n", " minV = self.data[mpos]\n", " for j in range(i + 1, N):\n", " if self.data[j] < minV:\n", " mpos = j\n", " minV = self.data[j]\n", " # keep track of what was done\n", " self.comparisons += 1\n", " \n", " return mpos\n", " \n", " def sort(self):\n", " start = time.time()\n", " self.comparisons = 0\n", " self.operations = 0\n", "\n", " for i in range(len(self.data) - 1):\n", " j = self.__argmin(i)\n", " self.__swap(i, j) \n", " # keep track of what was done\n", " self.operations += 1\n", "\n", " end = time.time()\n", " self.time = end - start\n", "\n", "class InsertionSort(SortingAlgorithm):\n", "\n", " def sort(self):\n", " start = time.time()\n", " self.comparisons = 0\n", " self.operations = 0\n", "\n", " for i in range(1, len(self.data)):\n", " temp = self.data[i]\n", " j = i\n", " while j > 0 and self.data[j-1] > temp:\n", " self.data[j] = self.data[j - 1]\n", " self.operations += 1\n", " self.comparisons += 1\n", " j = j - 1\n", "\n", " self.data[j] = temp\n", " self.operations += 1\n", " if j > 0:\n", " self.comparisons += 1\n", " if self.verbose:\n", " print(\"It. {}: {} comp: {} push+place:{}\".format(i,\n", " self.data,\n", " self.comparisons,\n", " self.operations\n", " ))\n", "\n", " if self.verbose:\n", " print(self.data)\n", " print(\"\\nNumber of comparisons: {}\".format(self.comparisons))\n", " print(\"Number of push-ups+place: {}\".format(self.operations))\n", " \n", " end = time.time()\n", " self.time = end - start\n", "\n", "\n", "class MergeSort(SortingAlgorithm):\n", " def __init__(self,data, verbose = True):\n", " self.data = data\n", " self.time = 0\n", " self.comparisons = 0\n", " self.operations = 0\n", " self.verbose = verbose\n", " \n", " def __merge(self, first, last, mid):\n", " if self.verbose:\n", " print(\"Executing merge({},{},{})...\".format(first,last,mid))\n", " tmp = []\n", " i = first\n", " j = mid + 1\n", " while i <= mid and j <= last:\n", " if self.data[i] < self.data[j]:\n", " self.comparisons += 1\n", " tmp.append(self.data[i])\n", " i += 1\n", " else:\n", " tmp.append(self.data[j])\n", " j += 1\n", " while i <= mid:\n", " tmp.append(self.data[i])\n", " i += 1\n", " self.data[first:first+len(tmp)] = tmp\n", " \n", " def __recursiveMergeSort(self, first, last):\n", " if self.verbose:\n", " print(\"Executing recursive merge sort({},{})...\".format(first,last))\n", "\n", " self.operations += 1\n", " if first < last:\n", " mid = (first + last)//2 #<- index so mid+1 elements go in the first sublist!!! \n", " self.__recursiveMergeSort(first, mid)\n", " self.__recursiveMergeSort(mid +1, last)\n", " self.__merge(first,last,mid)\n", " \n", " def sort(self):\n", " self.comparisons = 0\n", " self.operations = 0\n", " start = time.time()\n", " self.__recursiveMergeSort(0,len(self.data)-1) \n", " end = time.time()\n", " self.time = end - start\n", "\n", "class QuickSort(SortingAlgorithm):\n", " def __init__(self,data, verbose = True):\n", " self.data = data\n", " self.time = 0\n", " self.comparisons = 0\n", " self.operations = 0\n", " self.verbose = verbose\n", "\n", " def __swap(self, i,j):\n", " \"\"\"swaps elements at positions i and j\"\"\"\n", " self.operations += 1\n", " tmp = self.data[i]\n", " self.data[i] = self.data[j]\n", " self.data[j] = tmp\n", "\n", " def __pivot(self, start, end):\n", " \"\"\"gets the pivot and swaps elements in [start, end]\n", " accordingly\"\"\"\n", " p = self.data[start]\n", " j = start\n", "\n", " for i in range(start + 1, end + 1):\n", " self.comparisons += 1\n", " if self.data[i] < p:\n", " j = j + 1\n", " self.__swap(i, j)\n", "\n", " self.__swap(start,j)\n", "\n", " return j\n", "\n", " def __recQuickSort(self, start, end):\n", " \"\"\"gets the pivot and recursively applies\n", " itself on the left and right sublists\n", " \"\"\"\n", " if start < end:\n", " #GET THE PIVOT\n", " j = self.__pivot(start, end)\n", "\n", " self.__recQuickSort(start, j - 1)\n", "\n", " self.__recQuickSort(j + 1, end)\n", "\n", " def sort(self):\n", " self.comparisons = 0\n", " self.operations = 0\n", " start = time.time()\n", " self.__recQuickSort(0, len(self.data) - 1)\n", " end = time.time()\n", " self.time = end - start\n", "\n", "\n", "#Need to extend the recursion limit for the test on reverse sorted\n", "#array with 5000 elements\n", "sys.setrecursionlimit(10000)\n", "def getNrandom(n):\n", " res = []\n", " for i in range(n):\n", " res.append(random.randint(-10000,10000))\n", " return res\n", "\n", "def testSorters(myList, verbose = False):\n", " #copy because the sorter will actually change the list!\n", " myList1 = myList[:]\n", " myList2 = myList[:]\n", " myList3 = myList[:]\n", " selSorter = SelectionSort(myList, verbose = False)\n", " insSorter = InsertionSort(myList1, verbose = False)\n", " mSorter = MergeSort(myList2, verbose = False)\n", " qSorter = QuickSort(myList3, verbose = False)\n", " if verbose:\n", " print(\"TestList:\\n{}\".format(myList))\n", " print(\"TestList1:\\n{}\".format(myList1))\n", " print(\"TestList2:\\n{}\".format(myList2))\n", " print(\"TestList3:\\n{}\".format(myList3))\n", " selSorter.sort()\n", " insSorter.sort()\n", " mSorter.sort()\n", " qSorter.sort()\n", " if verbose:\n", " print(\"Outputs:\")\n", " print(myList)\n", " print(myList1)\n", " print(myList2)\n", " print(myList3)\n", " print(\"Test with {} elements\".format(len(myList)))\n", " print(\"Insertion sort:\")\n", " print(\"Number of comparisons: {}\".format(insSorter.getComparisons()))\n", " print(\"Number of operations: {}\".format(insSorter.getOperations()))\n", " print(\"In {:.4f}s\".format(insSorter.getTime()))\n", " print(\"Selection sort:\")\n", " print(\"Number of comparisons: {}\".format(selSorter.getComparisons()))\n", " print(\"Number of operations: {}\".format(selSorter.getOperations()))\n", " print(\"In {:.4f}s\".format(selSorter.getTime()))\n", " print(\"Merge sort:\")\n", " print(\"Number of comparisons: {}\".format(mSorter.getComparisons()))\n", " print(\"Number of operations: {}\".format(mSorter.getOperations()))\n", " print(\"In {:.4f}s\".format(mSorter.getTime()))\n", " print(\"Quick sort:\")\n", " print(\"Number of comparisons: {}\".format(qSorter.getComparisons()))\n", " print(\"Number of operations: {}\".format(qSorter.getOperations()))\n", " print(\"In {:.4f}s\".format(qSorter.getTime()))\n", "\n", "# script that finally executes the comparisons...\n", "print(\"Test with a list of 10 elements...\")\n", "testList = getNrandom(10)\n", "testSorters(testList, verbose = True) # just for testing that everything is OK...\n", "print(\"#############\")\n", "print(\"Test with a list of 5000 elements...\")\n", "testList = list(range(5000))\n", "testSorters(testList, verbose = False)\n", "print(\"#############\")\n", "print(\"Test with a list of 5000 elements in reverse order...\")\n", "testList = list(range(5000))\n", "testList.sort(reverse = True)\n", "testSorters(testList, verbose = False)\n", "print(\"#############\")\n", "print(\"Test with a list of 2000 elements, with last half in reverse order...\")\n", "a = list(range(1000))\n", "b = list(range(1000,2000))\n", "b.sort(reverse=True)\n", "testSorters(a+b, verbose = False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [Comparison.py](sorting_algos/Comparison.py)\n", "\n", "
\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "## Exercise (Counting Sort)\n", "\n", "7. Implement counting sort for a list of elements included in the range [min, max]. Counting sort's code for the simplified case of numbers in the range [0, n] is reported below:\n", "\n", "![](images/countingsort.png)\n", "\n", "Please note that **values below zero might be present** too. \n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Test 1\n", "[-5, 0, -1, 9, 1, 8, -2, 3, 6, 2]\n", "[-5, -2, -1, 0, 1, 2, 3, 6, 8, 9]\n", "\n", "Test 2\n", "[-6, 1, -10, -3, -6, -6, -7, -2, 9, 4]\n", "[-10, -7, -6, -6, -6, -3, -2, 1, 4, 9]\n", "\n", "Test 3\n", "[0, -1, -2, -3, -8, 2, -2, 10, -6, -5]\n", "[-8, -6, -5, -3, -2, -2, -1, 0, 2, 10]\n", "\n", "Test 4\n", "[-4, -2, -6, -6, -3, 0, 10, 0, 9, -1]\n", "[-6, -6, -4, -3, -2, -1, 0, 0, 9, 10]\n", "\n", "Test 5\n", "[-9, 8, -3, 7, -8, -2, 2, 3, -1, 5]\n", "[-9, -8, -3, -2, -1, 2, 3, 5, 7, 8]\n", "\n", "Test 6\n", "[-2, 4, 7, 0, 0, -5, 0, 7, -2, -10]\n", "[-10, -5, -2, -2, 0, 0, 0, 4, 7, 7]\n", "\n", "Test 7\n", "[-7, -6, 2, -4, 6, 3, 10, 5, -7, -4]\n", "[-7, -7, -6, -4, -4, 2, 3, 5, 6, 10]\n", "\n", "Test 8\n", "[-10, -9, -5, -10, -2, 1, -5, -4, 0, 2]\n", "[-10, -10, -9, -5, -5, -4, -2, 0, 1, 2]\n", "\n", "Test 9\n", "[2, 6, 8, 0, 6, 3, 2, -6, 0, 8]\n", "[-6, 0, 0, 2, 2, 3, 6, 6, 8, 8]\n", "\n", "Test 10\n", "[9, -8, -7, 5, -4, 10, 9, -7, 0, -9]\n", "[-9, -8, -7, -7, -4, 0, 5, 9, 9, 10]\n" ] } ], "source": [ "import random\n", "\n", "def countingSort(A):\n", " M = A[0] # will store max(A), used to extend with negative numbers\n", " m = A[0] # will store min(A), used to extend with negative numbers\n", " for i in range(1,len(A)):\n", " if M < A[i]:\n", " M = A[i]\n", " if m > A[i]:\n", " m = A[i]\n", " \n", " B = [0]*(M-m+1)\n", "\n", " for a in A:\n", " B[a - m] = B[a - m] + 1\n", "\n", " j = 0\n", " for i in range(M-m + 1):\n", " while B[i] > 0:\n", " A[j] = i + m\n", " B[i] = B[i] - 1\n", " j = j + 1\n", "\n", "for k in range(10): \n", " x = []\n", " for i in range(10):\n", " x.append(random.randint(-10, 10))\n", " print(\"\\nTest {}\".format(k+1))\n", " print(x)\n", " countingSort(x)\n", " print(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
" ] } ], "metadata": { "celltoolbar": "Edit Metadata", "kernelspec": { "display_name": "3.10.14", "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.10.14" } }, "nbformat": 4, "nbformat_minor": 2 }