{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Programming with Python (lab classes)\n", "#### Stefan Güttel, [guettel.com](http://guettel.com)\n", "#### (based on course notes written by Vedran Šego, [vsego.org](http://vsego.org/))\n", "\n", "## Content:\n", "\n", "1. Reversing a list\n", "\n", "2. Sorting a list\n", "\n", "3. Binary search" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "From the Python perspective, most of these are purely exercises in list manipulations. However, they are important ones, and they can also come in handy for the languages without the rich lists support that Python offers.\n", "\n", "**Note** that among these explanations of the Exercises, there are also four new problems in this document." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Reversing a list\n", "\n", "We want to **reverse** a list without using Python's built-in functions reversed and reverse (that exist in some languages as well, but not all of them)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If we were to reverse a list in real life (say, a sequence of papers, each with a number on it), we would have done it like this:\n", "\n", "> Swap the first and the last element of a list. \n", "> Swap the second and the second to last element of a list. \n", "> ...\n", "\n", "(recall that we have done swapping of two variables in the (sub)example in Lecture 2 (*Loops and Conditionals*)\n", "\n", "Here is how we'd do it on an example:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let this be a sequence of five papers with one number on each of them:\n", "\n", "
\n", "
17
\n", "
23
\n", "
11
\n", "
13
\n", "
19
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**The first step:** Take the **first** element from the left (marked blue) and the **first** element from the right (marked green):\n", "\n", "
\n", "
17
\n", "
23
\n", "
11
\n", "
13
\n", "
19
\n", "
\n", "\n", "Swap them:\n", "\n", "
\n", "
19
\n", "
23
\n", "
11
\n", "
13
\n", "
17
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "All that is left now is inverse the sublist without the swapped elements.\n", "\n", "**The second step:** Take the **second** element from the left (marked blue) and the **second** element from the right (marked green):\n", "\n", "
\n", "
19
\n", "
23
\n", "
11
\n", "
13
\n", "
17
\n", "
\n", "\n", "Swap them:\n", "\n", "
\n", "
19
\n", "
13
\n", "
11
\n", "
23
\n", "
17
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since swapping 11 with itself makes no sense, nor would it make sense to (again) swap 23 with 13 or 17 with 19, we stop." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "So, in a general case, how long does this go?\n", "\n", "There are to possibilities:\n", "\n", "1. Do this until \"left\" index becomes bigger than the \"right\" one (effectively putting the \"left\" one to the right of the \"right\" one).\n", "\n", "2. Do this until you reach the center of the list. \n", " One way to get an index of a central element is\n", "python\n", "index_of_center = len(x) // 2\n", "\n", "\n", "Let us first show how the first approach works (as it should work in all modern languages):" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Before reversing: [17, 19, 23]\n", "After reversing: [23, 19, 17]\n" ] } ], "source": [ "x = [17, 19, 23]\n", "\n", "print(\"Before reversing:\", x)\n", "\n", "left = 0 # index of a left element to swap\n", "right = len(x) - 1 # index of a right element to swap\n", "while left < right:\n", " temp = x[left]\n", " x[left] = x[right]\n", " x[right] = temp\n", " left += 1\n", " right -= 1\n", "\n", "print(\"After reversing: \", x)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "If the language in question can work with negative indices (for indexing the elements from the right), we can use the following method:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Before reversing: [17, 19, 23]\n", "After reversing: [23, 19, 17]\n" ] } ], "source": [ "x = [17, 19, 23]\n", "\n", "print(\"Before reversing:\", x)\n", "\n", "k = 0 # index of a left element to swap\n", "for k in range(len(x)//2):\n", " temp = x[k]\n", " x[k] = x[-(k+1)]\n", " x[-(k+1)] = temp\n", "\n", "print(\"After reversing: \", x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In Python, this is faster, because for is generally faster than while." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We could have also done this without negative indices:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Before reversing: [17, 19, 23]\n", "After reversing: [23, 19, 17]\n" ] } ], "source": [ "x = [17, 19, 23]\n", "\n", "print(\"Before reversing:\", x)\n", "\n", "k = 0 # index of a left element to swap\n", "len_of_x = len(x)\n", "for k in range(len(x)//2):\n", " temp = x[k]\n", " x[k] = x[len_of_x-(k+1)]\n", " x[len_of_x-(k+1)] = temp\n", "\n", "print(\"After reversing: \", x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Sorting a list\n", "\n", "We want to **sort** a list without using Python's built-in functions sorted and sort (that exist in some languages as well, but not all of them)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Assume that you have a sequence of papers on a table, each paper with a single number written on it. For example:\n", "\n", "
\n", "
17
\n", "
23
\n", "
11
\n", "
13
\n", "
19
\n", "
\n", "\n", "How would you sort them?\n", "\n", "Remember, this sequence can have hundreds of elements (actually, millions, but you won't find a table that big :-))." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**The first step:** Find the smallest element (marked green) in the entire list, i.e., from the **first** element (marked blue) to the last one:\n", "\n", "
\n", "
17
\n", "
23
\n", "
11
\n", "
13
\n", "
19
\n", "
\n", "\n", "Swap them:\n", "\n", "
\n", "
11
\n", "
23
\n", "
17
\n", "
13
\n", "
19
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, the smallest element is on the first position. Forget about it for now and focus on the rest of the list:\n", "\n", "**The second step:** Find the smallest element (marked green) in the sublist starting from the **second** element (marked blue):\n", "\n", "
\n", "
11
\n", "
23
\n", "
17
\n", "
13
\n", "
19
\n", "
\n", "\n", "Swap them:\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
23
\n", "
19
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, the two smallest elements are where they should be. Forget about them for now and focus on the rest of the list:\n", "\n", "**The third step:** Find the smallest element in the sublist starting from the **third** element. This time, it is the **third** element itself, which means that it is already positioned properly (marked turquoise):\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
23
\n", "
19
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, the three smallest elements are where they should be. Forget about them for now and focus on the rest of the list:\n", "\n", "**The fourth step:** Find the smallest element (marked green) in the sublist starting from the **fourth** element (marked blue):\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
23
\n", "
19
\n", "
\n", "\n", "Swap them:\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
19
\n", "
23
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, with the first four elements of the five-element list in their proper positions, we don't need to check the rest of the list (it's only one element, which is sorted by definition). So, we're done!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us summarize what needs to be done:\n", "\n", "1. Go through all members of the list except the last one. This is the left index, so let's use a variable left.\n", "\n", "2. For each of those:\n", "\n", " 1. find the minimum among elements with indices left, left+1,..., n-1, where n denotes the length of the list. We shall denote the index of the minimum as right.\n", "\n", " 2. if the minimum is **not** the one with the index left, swap these two.\n", "\n", "Written as a Python code, this is how we do it:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x: [17, 23, 11, 13, 19]\n", "sorted(x): [11, 13, 17, 19, 23]\n", "Our sorted x: [11, 13, 17, 19, 23]\n" ] } ], "source": [ "x = [17, 23, 11, 13, 19]\n", "print(\"x: \", x)\n", "print(\"sorted(x): \", sorted(x))\n", "\n", "n = len(x)\n", "for left in range(n-1):\n", " right = left # assume that this one is the minimum; check all the others\n", " for k in range(left+1, n):\n", " if x[k] < x[right]:\n", " right = k\n", " if right > left:\n", " tmp = x[left]\n", " x[left] = x[right]\n", " x[right] = tmp\n", "print(\"Our sorted x:\", x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This sort is called [*selection sort*](http://en.wikipedia.org/wiki/Selection_sort) and is one of the slowest (but also among the most intuitive ones and easy to understand)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Problem 1.** Write a function that sorts a list *descendingly* by the *reversed value* of its elements.\n", "\n", "For example, the list $1719, 1123, 3113$ is sorted descendedly by the reversed numbers because $9171 \\ge 3211 \\ge 3113$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Binary search\n", "\n", "In ancient times, many years ago, people used phonebooks. Those were big books with a huge list of people's names and their phone numbers, sorted by their surname. So, how would one find -- for example -- Mr. Turing there?\n", "\n", "The key property of a phonebook is that it is **sorted**. Let us use that to our advantage.\n", "\n", "**Step 1.** Open the book roughly in the middle. You're likely to get people whose surnames start with \"M\" or \"N\". Since \"T\" > \"N\" (or \"M\", doesn't really matter) and the list is sorted, we can conclude that Mr. Turing can only be in the right half of the book.\n", "\n", "**Step 2.** Open the book roughly in the middle of that right half and say you've found people starting with \"S\". Again, \"T\" > \"S\", so Mr. Turing is in the right half (of the half we were observing, so in the rightmost quarter of the whole book).\n", "\n", "**Step 3.** Open that last quarter in the middle. You're likely to hit \"V\". Since \"T\" < \"V\", we conclude that Mr. Turing is in the left half of that last quarter, i.e., in the seventh 1/8 of the book.\n", "\n", "We continue to do so until Mr. Turing is found, or the part of the book that we're observing is small enough for us to observe that there is no Mr. Turing in the phonebook." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Example with numbers.** Let us observe a step by step search for the number $17$ on the following example:\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
19
\n", "
23
\n", "
29
\n", "
31
\n", "
37
\n", "
41
\n", "
43
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Step 1.** Memorize which part of the list we are searching in (this is the whole list when we begin) and select a middle element (marked green):\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
19
\n", "
23
\n", "
29
\n", "
31
\n", "
37
\n", "
41
\n", "
43
\n", "
\n", "\n", "Our list has an even length, so we there are two middle elements. It doesn't matter which we pick, but it's usually the left one, because this is what an integer division will give us. So, we have:\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
19
\n", "
23
\n", "
29
\n", "
31
\n", "
37
\n", "
41
\n", "
43
\n", "
\n", "\n", "Is $17 = 23$?\n", "\n", "No, it is not. But, we know that $17 < 23$ and, since the list is sorted, we also know that $23 \\le x$ for all $x$ right of the $23$. In other words,\n", "$$17 < 23 \\le x, \\quad \\forall \\text{x in the right part of the observed list}.$$\n", "We \"discard\" the right part of the list and repeat the process." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We are now working with the part of the list left of $23$:\n", "\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
19
\n", "
23
\n", "
29
\n", "
31
\n", "
37
\n", "
41
\n", "
43
\n", "
\n", "\n", "**Step 2.** Select a middle element (marked green) in the observed part of the list:\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
19
\n", "
23
\n", "
29
\n", "
31
\n", "
37
\n", "
41
\n", "
43
\n", "
\n", "\n", "Is $17 = 13$?\n", "\n", "No, it is not. But, we know that $13 < 17$ and, since the list is sorted, we also know that $x < 13 < 17$ for all $x$ left of the $13$. In other words,\n", "$$x < 13 < 17, \\quad \\forall \\text{x in the right part of the observed list}.$$\n", "We \"discard\" the left part of the list and repeat the process." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We are now working with the part of the list between $13$ and $23$ (not including these two):\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
19
\n", "
23
\n", "
29
\n", "
31
\n", "
37
\n", "
41
\n", "
43
\n", "
\n", "\n", "**Step 3.** Select a middle element (marked green) in the observed part of the list:\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
19
\n", "
23
\n", "
29
\n", "
31
\n", "
37
\n", "
41
\n", "
43
\n", "
\n", "\n", "Is $17 = 17$?\n", "\n", "Yes, so we have found it in the list." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, assume that we were looking for $18$ instead of $17$. All the steps so far would be the same. However, in this last step, we would have $17 < 18$, so we would have to discard $17$ and everything left of it:\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
19
\n", "
23
\n", "
29
\n", "
31
\n", "
37
\n", "
41
\n", "
43
\n", "
\n", "\n", "**Step 4.** Select a middle element (marked green) in the observed part of the list:\n", "\n", "
\n", "
11
\n", "
13
\n", "
17
\n", "
19
\n", "
23
\n", "
29
\n", "
31
\n", "
37
\n", "
41
\n", "
43
\n", "
\n", "\n", "Is $18 = 19$?\n", "\n", "No, it is not. In fact, $18 < 19$ and we -- as before -- discard $19$ and everything right of it. However, this time, the remaining list is empty (we have discarded all of its elements).\n", "\n", "Conclusion: $18$ is not an elment of the list." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, to implement this as a Python code:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Index of 17 in x: 2\n", "Index of 18 in x: None\n" ] } ], "source": [ "x = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43]\n", "\n", "def search(L, el):\n", " \"\"\"\n", " Returns the index of el in L if it exists, or None otherwise.\n", " \"\"\"\n", " # We're observing the part of the list between indices left and right.\n", " # When we start, it's the whole list, so from left=0 to right=len(x)-1.\n", " left = 0\n", " right = len(x)-1\n", "\n", " # The length of the observed part of the list is right-left+1, so\n", " # the list is NOT empty as long as right-left+1 > 0, i.e.,\n", " # the list is NOT empty as long as right>left-1, i.e.,\n", " # the list is NOT empty as long as right>=left.\n", " while right >= left:\n", " # The middle of the left,left+1,...,right range\n", " mid = (left + right) // 2\n", " # Compare the middle element to el\n", " if L[mid] == el:\n", " # We have found the element\n", " return mid\n", " # No else because return, if executed, interupts the function\n", " if L[mid] < el:\n", " # el can only be on the right of L[mid], so we move the left\n", " # border of the observed part of the list\n", " left = mid + 1\n", " else:\n", " # The else is needed here and corresponds to el < L[mid]\n", " # el can only be on the left of L[mid], so we move the right\n", " # border of the observed part of the list\n", " right = mid - 1\n", " # If we get here, we have exited the loop because its condition turned false.\n", " # In other words, the observed part of the list got to the zero length,\n", " # which means that el does not exist in L.\n", " return None\n", "\n", "print(\"Index of 17 in x:\", search(x, 17))\n", "print(\"Index of 18 in x:\", search(x, 18))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Problem 2.** If there is more than one occurence of an element in the list, which one will the algorithm find?\n", " 1. The first one,\n", " 2. The last one,\n", " 3. One of them, but not always the same one.\n", "\n", "Adapt the algorithm so that the last one is found." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Problem 3.** Adapt the binary search to a list sorted descendingly by the reversed values of its elements." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Problem 4.** Write a function is_sorted_asc(L) that returns True if the list L is sorted ascendingly and False otherwise." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## A note on creating new reversed/sorted list\n", "\n", "A quick way to adapt the algorithms presented above in a way that those functions return a new list with the same elements in a reversed/sorted order is to use functions from the [copy](https://docs.python.org/3.1/library/copy.html) module to copy the list and then just sort it. The preferred function to use here is usually (but not always!) [copy.deepcopy](https://docs.python.org/3.1/library/copy.html#copy.deepcopy).\n", "\n", "We can also create a new list and populate it with the original list's elements in the appropriate order, but this requires more work and can be considerably slower." ] } ], "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.5.1" } }, "nbformat": 4, "nbformat_minor": 0 }