CS 2120: Topic 10
=================
.. image:: ../img/comp_think.png
:width: 500px
Videos for this week:
^^^^^^^^^^^^^^^^^^^^
.. raw:: html
.. raw:: html
.. raw:: html
Algorithms
^^^^^^^^^^
.. admonition:: What is an algorithm?
:class: Note
**Algorithm** = a set of instructions for performing a specific task; a "recipe" for solving problems
Python allows you to *use* any number of algorithms (i.e. ``list.sort()``) without having to know about any of their implementation details
* *this is a good thing* when we want to just get things done
But, it's also important to *have a basic understanding of them*
* this can help you to become a better programmer, abstract thinker, and problem solver --- see ``computational thinking``
.. raw:: html
.. raw:: html
.. raw:: html
We will cover ``three`` algorithms today:
``binary search``, ``bubble sort``, and ``merge sort``.. one for each of the following categories:
* .. raw:: html
Searching
* .. raw:: html
Sorting
* .. raw:: html
Recursion
------------
.. Warning::
In this module we are moving away from *using code* and towards *understanding how it works*. As such, don't expect to look at these algorithms and immediately understand how they work. They require *careful study* to make sense of. The best tool you have for understanding how they work is to *carefully trace their operation, step by step*. Trying to understand complex algorithms "all in one go" is a recipe for frustration. Take your time, and step through the algorithm (with pen and paper) on a small input to get a feel for what it's doing.
Binary search
^^^^^^^^^^^^^
Let's take a look at ``binary search``::
def binary_search(list,val,left,right):
while left <= right:
midpoint = (left+right)/2
if list[midpoint] > val:
right = midpoint - 1
elif list[midpoint] < val:
left = midpoint + 1
else:
return midpoint
return -1
* On average, how many iterations through the loop does this function make?
.. image:: ../img/binary_search.png
:width: 600px
.. admonition:: How it works
:class: Note
* You give me a **sorted** list (``list``), a value to search for (``val``), the left index (``left``) and right index (``right``)
* I cut the list in half by taking the midpoint
* If ``val`` is left of midpoint, ``val`` must be on the left half of the list, so re-assign ``right`` to equal midpoint - 1
* If ``val`` is right of midpoint, ``val`` must be on the right half of the list, so re-assign ``left`` to equal midpoint + 1
* If ``val`` is at the midpoint, we're done
* Keep splitting the list and changing ``left``, ``right``, and midpoint until we find our value
* It's called "binary search" because we are splitting the list into 2 pieces for each iteration.
Bubble Sort
^^^^^^^^^^^
Let's take a look at ``bubble sort``::
def bubble_sort(list):
swap = True
while swap:
swap = False
for i in range(len(list)-1):
if list[i] > list[i+1]:
tmp = list[i]
list[i]=list[i+1]
list[i+1]=tmp
swap = True
return list
.. image:: ../img/bubble_sort.png
:width: 600px
.. admonition:: How it works
:class: Note
* You give me a list called ``list``
* I scan through the list, looking at adjacent pairs of values.
* If I see a pair that is "out of order" (e.g., ``[17, 9]`` ), I swap the two values to be in order ( ``[9,17]`` ).
* I keep doing that until the list is sorted.
* It's called "bubble sort" because the smaller values seem to "bubble up to the top".
Is bubble sort the best?
^^^^^^^^^^^^^^^^^^^^^^^^
* Definitely not... there are many better sorting algorithms
* With *recursion*, we can do ``Mergesort`` (better than bubble sort)
Recursion
^^^^^^^^^^
* If a function calls *itself*, it is said to be a *recursive function*.
Writing a simple recursive function
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
* Every recursive function needs two things:
* A **base case** that *terminates* the recursion.
* A **recursive step** that calls the function again, but with a modified (probably smaller) parameter
.. admonition:: Activity
:class: Note
Write a function ``fact(n)`` which computes the factorial
of ``n`` *using recursion* (no loops allowed!).
Identify the ``base case`` and ``recursive step``.
Mergesort
^^^^^^^^^^
.. admonition:: Remember this
:class: Warning
There are *many* algorithms to solve any given problem.
* First, we need to implement a ``merge`` operation in Python::
def merge(left, right):
merged = []
l=0
r=0
while l < len(left) and r < len(right):
if left[l] <= right[r]:
merged.append(left[l])
l = l + 1
else:
merged.append(right[r])
r = r + 1
if l < len(left):
merged.extend(left[l:])
else:
merged.extend(right[r:])
return merged
* With merge defined, let's take a look at merge sort::
def mergesort(list):
if len(list) <= 1:
return list
else:
midpoint = int( len(list) / 2 )
left = mergesort(list[:midpoint])
right = mergesort(list[midpoint:])
return merge(left,right)
.. image:: ../img/merge_sort.png
:width: 600px
.. admonition:: How it works
:class: Note
* You give me a list (``list``) with ``n`` elements
* I divide ``list`` into ``n`` sublists, each having 1 element.
* The sublists are now already sorted! (Any list with only one element is automatically sorted)
* I now begin *merging* sublists, to produce bigger (but still sorted) sublists:
* I compare the first element in one sublist to the first in the other
* Whichever is smaller goes into the merged list
* I now compare the *second* element in that list to the first element in the other list
* ... and so on...
* I keep going until there is nothing left to merge (there's only *one* big, sorted, list)
For next class
^^^^^^^^^^^^^^
* If you've made it this far, congrats! Check out http://www.sorting-algorithms.com/ and see how bubble sort and merge sort compare to other popular sorting algorithms
* Work on Assignment 3 and Assignment 4