#!/usr/bin/env python # coding: utf-8 # # Programming with Python (lab classes) # #### Stefan Güttel, [guettel.com](http://guettel.com) # # ## Content: # # 1. Reversing a list # # 2. Sorting a list # # 3. Binary search # From the Python perspective, most of this week's problems are purely exercises in list manipulations. However, they are important for understanding search and sorting algorithms, and they might be useful for other programming languages which do not offer the many list functionalities support that Python offers. # # **Note:** Among the below explanations of the Exercises, there are also four new problems in this document. # ## Reversing a list # # 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). # 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: # # > Swap the first and the last element of a list. # > Swap the second and the second to last element of a list. # > ... # # Rrecall that we have learned how to swap the values of two variables in the (sub)example in Lecture 2 (*Loops and Conditionals*). # # Here is how we'd do it on an example: # Let this be a sequence of five papers with one number on each of them: # #

# **The first step:** Take the **first** element from the left (marked blue) and the **first** element from the right (marked green): # #

# # Swap them: # #

# All that is left now is to inverse the sublist without the swapped elements. # # **The second step:** Take the **second** element from the left (marked blue) and the **second** element from the right (marked green): # #

# # Swap them: # #

# 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. # So, in a general case, how long does this go? # # There are to possibilities: # # 1. Do this until "left" index becomes bigger than the "right" one (effectively putting the "left" one to the right of the "right" one). # # 2. Do this until you reach the center of the list. # One way to get an index of a central element is # ```python # index_of_center = len(x) // 2 # ``` # # Let us first show how the first approach works (as it should work in all modern languages): # In[1]: x = [17, 19, 23] print("Before reversing:", x) left = 0 # index of a left element to swap right = len(x) - 1 # index of a right element to swap while left < right: temp = x[left] x[left] = x[right] x[right] = temp left += 1 right -= 1 print("After reversing: ", x) # If the language in question can work with negative indices (for indexing the elements from the right), we can use the following method: # In[2]: x = [17, 19, 23] print("Before reversing:", x) k = 0 # index of a left element to swap for k in range(len(x)//2): temp = x[k] x[k] = x[-(k+1)] x[-(k+1)] = temp print("After reversing: ", x) # In Python, this approach is faster because `for` is generally faster than `while`. # We could have also done this without negative indices: # In[3]: x = [17, 19, 23] print("Before reversing:", x) k = 0 # index of a left element to swap len_of_x = len(x) for k in range(len(x)//2): temp = x[k] x[k] = x[len_of_x-(k+1)] x[len_of_x-(k+1)] = temp print("After reversing: ", x) # ## Sorting a list # # We want to **sort** a list without using Python's built-in functions `sorted` and `sort` (that exist in some other programming languages as well, but not all of them). # Assume that you have a sequence of papers on a table, each paper with a single number written on it. For example: # #

# # How would you sort them? # # Remember, this sequence can have hundreds of elements (actually, millions, but you won't find a table that big :-)). # **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: # #

# # Swap them: # #

# Now, the smallest element is on the first position. Forget about it for now and focus on the rest of the list: # # **The second step:** Find the smallest element (marked green) in the sublist starting from the **second** element (marked blue): # #

# # Swap them: # #

# Now the two smallest elements are where they should be. Forget about them for now and focus on the rest of the list: # # **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): # #

# Now the three smallest elements are where they should be. Forget about them for now and focus on the rest of the list: # # **The fourth step:** Find the smallest element (marked green) in the sublist starting from the **fourth** element (marked blue): # #

# # Swap them: # #

# 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! # Let us summarize this algorithm: # # 1. Go through all members of the list except the last one. This is the left index, so let's use a variable `left`. # # 2. For each of those: # # 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`. # # 2. if the minimum is **not** the one with the index `left`, swap these two. # # Written as a Python code, this is how we do it: # In[4]: x = [17, 23, 11, 13, 19] print("x: ", x) print("sorted(x): ", sorted(x)) n = len(x) for left in range(n-1): right = left # assume that this one is the minimum; check all the others for k in range(left+1, n): if x[k] < x[right]: right = k if right > left: tmp = x[left] x[left] = x[right] x[right] = tmp print("Our sorted x:", x) # 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). # **Problem 1.** Write a function that sorts a list *descendingly* by the *reversed value* of its elements. # # For example, the list $1719, 1123, 3113$ is sorted descendedly by the reversed numbers because $9171 \ge 3211 \ge 3113$. # ## Binary search # # 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? # # The key property of a phonebook is that it is **sorted**. Let us use that to our advantage. # # **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. # # **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). # # **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. # # 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. # **Example with numbers.** Let us observe a step by step search for the number $17$ on the following example: # #

# **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): # #

# # Our list has an even length, so we there are two middle elements. It doesn't matter which one we pick, but it's usually the left one, because this is what an integer division will give us. So, we have: # #

# # Is $17 = 23$? # # 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, # $$17 < 23 \le x, \quad \forall \text{$x$ in the right part of the observed list}.$$ # We "discard" the right part of the list and repeat the process. # We are now working with the part of the list left of $23$: # # #

# # **Step 2.** Select a middle element (marked green) in the observed part of the list: # #

# # Is $17 = 13$? # # 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, # $$x < 13 < 17, \quad \forall \text{$x$ in the right part of the observed list}.$$ # We "discard" the left part of the list and repeat the process. # We are now working with the part of the list between $13$ and $23$ (not including these two): # #

# # **Step 3.** Select a middle element (marked green) in the observed part of the list: # #

# # Is $17 = 17$? # # Yes, so we have found it in the list. # 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: # #

# # **Step 4.** Select a middle element (marked green) in the observed part of the list: # #

# # Is $18 = 19$? # # 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). # # Conclusion: $18$ is not an elment of the list. # Now, to implement this as a Python code: # In[5]: x = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43] def search(L, el): """ Returns the index of `el` in `L` if it exists, or `None` otherwise. """ # We're observing the part of the list between indices `left` and `right`. # When we start, it's the whole list, so from `left=0` to `right=len(L)-1`. left = 0 right = len(L)-1 # The length of the observed part of the list is `right-left+1`, so # the list is NOT empty as long as `right-left+1 > 0`, i.e., # the list is NOT empty as long as `right>left-1`, i.e., # the list is NOT empty as long as `right>=left`. while right >= left: # The middle of the `left,left+1,...,right` range mid = (left + right) // 2 # Compare the middle element to `el` if L[mid] == el: # We have found the element return mid # No `else` because `return`, if executed, interupts the function if L[mid] < el: # `el` can only be on the right of `L[mid]`, so we move the left # border of the observed part of the list left = mid + 1 else: # The `else` is needed here and corresponds to `el < L[mid]` # `el` can only be on the left of `L[mid]`, so we move the right # border of the observed part of the list right = mid - 1 # If we get here, we have exited the loop because its condition turned false. # In other words, the observed part of the list got to the zero length, # which means that `el` does not exist in `L`. return None print("Index of 17 in x:", search(x, 17)) print("Index of 18 in x:", search(x, 18)) # **Problem 2.** If there is more than one occurence of an element in the list, which one will the algorithm find? # 1. The first one. # 2. The last one. # 3. One of them, but not always the same one. # # Adapt the algorithm so that the last one is found. # **Problem 3.** Adapt the binary search to a list sorted descendingly by the reversed values of its elements. # **Problem 4.** Write a function `is_sorted_asc(L)` that returns `True` if the list `L` is sorted ascendingly and `False` otherwise. # ## A note on creating new reversed/sorted list # # 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). # # 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.