\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",
"17

\n",
" 23

\n",
" 11

\n",
" 13

\n",
" 19

\n",
"\n",
"

\n",
"\n",
"Swap them:\n",
"\n",
"17

\n",
" 23

\n",
" 11

\n",
" 13

\n",
" 19

\n",
"\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",
"19

\n",
" 23

\n",
" 11

\n",
" 13

\n",
" 17

\n",
"\n",
"

\n",
"\n",
"Swap them:\n",
"\n",
"19

\n",
" 23

\n",
" 11

\n",
" 13

\n",
" 17

\n",
"\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",
"19

\n",
" 13

\n",
" 11

\n",
" 23

\n",
" 17

\n",
"\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",
"17

\n",
" 23

\n",
" 11

\n",
" 13

\n",
" 19

\n",
"\n",
"

\n",
"\n",
"Swap them:\n",
"\n",
"17

\n",
" 23

\n",
" 11

\n",
" 13

\n",
" 19

\n",
"\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",
"11

\n",
" 23

\n",
" 17

\n",
" 13

\n",
" 19

\n",
"\n",
"

\n",
"\n",
"Swap them:\n",
"\n",
"11

\n",
" 23

\n",
" 17

\n",
" 13

\n",
" 19

\n",
"\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",
"11

\n",
" 13

\n",
" 17

\n",
" 23

\n",
" 19

\n",
"\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",
"11

\n",
" 13

\n",
" 17

\n",
" 23

\n",
" 19

\n",
"\n",
"

\n",
"\n",
"Swap them:\n",
"\n",
"11

\n",
" 13

\n",
" 17

\n",
" 23

\n",
" 19

\n",
"\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",
"11

\n",
" 13

\n",
" 17

\n",
" 19

\n",
" 23

\n",
"\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",
"11

\n",
" 13

\n",
" 17

\n",
" 19

\n",
" 23

\n",
" 29

\n",
" 31

\n",
" 37

\n",
" 41

\n",
" 43

\n",
"\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",
"11

\n",
" 13

\n",
" 17

\n",
" 19

\n",
" 23

\n",
" 29

\n",
" 31

\n",
" 37

\n",
" 41

\n",
" 43

\n",
"\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",
"11

\n",
" 13

\n",
" 17

\n",
" 19

\n",
" 23

\n",
" 29

\n",
" 31

\n",
" 37

\n",
" 41

\n",
" 43

\n",
"11

\n",
" 13

\n",
" 17

\n",
" 19

\n",
" 23

\n",
" 29

\n",
" 31

\n",
" 37

\n",
" 41

\n",
" 43

\n",
"11

\n",
" 13

\n",
" 17

\n",
" 19

\n",
" 23

\n",
" 29

\n",
" 31

\n",
" 37

\n",
" 41

\n",
" 43

\n",
"11

\n",
" 13

\n",
" 17

\n",
" 19

\n",
" 23

\n",
" 29

\n",
" 31

\n",
" 37

\n",
" 41

\n",
" 43

\n",
"11

\n",
" 13

\n",
" 17

\n",
" 19

\n",
" 23

\n",
" 29

\n",
" 31

\n",
" 37

\n",
" 41

\n",
" 43

\n",
"11

\n",
" 13

\n",
" 17

\n",
" 19

\n",
" 23

\n",
" 29

\n",
" 31

\n",
" 37

\n",
" 41

\n",
" 43

\n",
"11

\n",
" 13

\n",
" 17

\n",
" 19

\n",
" 23

\n",
" 29

\n",
" 31

\n",
" 37

\n",
" 41

\n",
" 43

\n",
"