$30
ITI 1120
Lab # 9
SEARCHING AND SORTING:
Algorithms to solve them, their analysis/efficiency
Applications of searching and sorting
1
Star/ng Lab 9
• Open a browser and log into Blackboard Learn
• On the le? hand side under Labs tab, find lab6 material
contained in lab9-students.zip file
• Download that file to the Desktop and unzip it.
2
Before star/ng, always make sure
you are running Python 3
This slide is applicable to all labs, exercises, assignments … etc
ALWAYS MAKE SURE FIRST that you are running Python 3.4 (3.5 is
fine too)
That is, when you click on IDLE (or start python any other way)
look at the first line that the Python shell displays. It should say
Python 3.4 or 3.5 (and then some extra digits)
If you do not know how to do this, read the material provided
with Lab 1. It explains it step by step
3
4
Later on if you wish, you can type them
into a computer (or copy/paste from the
solu/ons once I poste them)
Do all the exercises labeled as
Task in your head i.e. on a
paper
5
ANALASYS OF ALGORITHMS:
For the rest of this semester running /me of a program/
algorithm/func/on will mean the same thing as
the number of opera/ons of a program/algorithm/
func/on. These two terms mean the same thing!! I will use
them interchangeably. You textbook uses “running /me”
Big O nota/on hides the constants and slower going terms
of a func/on. For example:
4n2 is O(n2), (and so is n2/100 +n for example)
20n -70 is O(n)
10log2 n + 100 is O(log2 n)
Task 1:
For each of the following 7 func/ons answer the ques/on about
how many opera/ons the func/ons does, roughly, as n grows. For
example the answer is roughly linear in n for foo3, i.e O(n)
Task 2: answer the 4
ques/ons
1. What does the program on
the left print?
2. Write one sentence that
describes abstractly (in
plain English) what the
function annona does?
(something a person with
no programming knowledge
can understand)
3. Suppose the function
annona is called on an
list that has 1000
integers. How many times
would L[i]==L[j] test be
executed?
a) less than 20
b) Between 1000 and 9,000 times
c) Between 10,000 and 100, 000 times
d) Between 200, 000 and 2 million times
e) between 10 million and 200 million
times
f) None of the above
4. How many operations
(roughly) does
function L do on a
list of size n?
PART 1: SEARCHING
Python’s search
Python’s “in” operator can be used to determine if a given element is in a given
list. For example
>>> 10 in [1,20,-1,10,-5, 10]
True
Python’s .index method can be used to determine if a given element is in a
given list and if it is it returns its posi/on, and otherwise -1
>>> L=[1,20,-1,10,-5,10]
>>> L.index(10)
3
>>> A=['d', 'a', 'b', 'a']
>>> A.index('a')
1
>>> A.index(‘c')
-1
Both in and .index methods perform linear search and thus take linear number
of opera/ons in the size of the list
Study: overview of Linear Search
Linear search starts at index 0 and looks at each item one by one.
At each index, we ask this ques/on: Is the value we are looking for
at the current index?
IMPORTANT: Linear search is used to find an item in an UNSORTED
list! It takes, roughly, linear number of opera/ons (in the worst
case, i.e. O(n) ), where n is the size of the list.
Python’s “in” and .index built-in func/ons perform linear search
and thus they too take do O(n) opera/ons.
Task 3: Linear Search
Open the file called linear_search-3-versions.py and study the 3
implementa/ons of linear search. They are all correct and all do
roughly n opera/ons ( i.e. O(n) ) on lists of size n.
“Which one you prefer is largely a maler of taste: some
programmers dislike returning in the middle of a loop, so they
won’t like the second version. Others dislike modifying parameters
in any way, so they won’t like the third version. S/ll others will
dislike that extra check that happens in the first version. “
Interlude: some useful list methods to know
Here is some useful list methods that modify the given list lst:
lst.append(item) adds item to the end of lst
lst.pop() removes the last element from lst
lst.pop(i) removes item in posi/on i in the lst
and returns that item
lst.insert(i, item) inserts v before index i in lst
For more run in python shell:
help(list.append)
help(list.pop)
help(list.insert)
Programming exercise 1 and Task 4:
Prog ex 1:
• All three versions of linear search in linear_search-3-versions.py
start at index 0. Rewrite all three to search from the end of the
list instead of from the beginning. Make sure you test them.
Task 4:
• For the new versions of linear search: if you are looking for value
v and it appears in the list more than once, which posi/on will
your modified linear searches find?
Programming ex 2: min or max and Task 5
Prog Ex 2:
• Write a func/on named min_or_max_index that has two
parameters: one of type list and another type bool. If the
Boolean parameter refers to True, the func/on returns a
tuple containing the minimum and its index; and if it refers to
False, it returns a tuple containing the maximum and its
index.
(do not use python’s min and max func/ons – roll your own
implementa/on)
Task 5:
• On a list of size n, what is roughly the number of opera/ons
your program does in the worst case? (constant, linear in n,
quadra/c in n, log n ….?)
Study: overview of Binary Search and Task 6
IMPORTANT:
Binary search is used to find an item in an SORTED list!
It does, roughly, log2 n of opera/ons (in the worst case, i.e. O(log2
n)), where n the size of the list.
Task 6:
Open the file called binary_search.py. It contains the binary search
version we developed in class and study again how it works.
Ques/on: Binary search is significantly faster than the linear search but requires
that the list is sorted. As you know, the number of opera/ons for the best
sor/ng algorithm is on the order of n log2 n, where n is the size of the list. If we
search a lot of /mes on the same list of data, it makes sense to sort it once
before doing the searching. Roughly how many /mes do we need to search in
order to make sor/ng and then searching as fast or faster than linear search?
Programming exercise 3 (a bit of a challenge):
1. Write a func/on called first_one(L) that takes as input a list where each
element of L is either a number 0 or 1. In addi/on all 0s appear before all
1s. Func/on first_one(L) should return the posi/on in L of the first 1. If
there is no 1s in the list, return -1.
Unless the list is very small (less than 3 elements) your solu/on should not
access all the elements in the list. In par/cular if the list has 1000 elements you
solu/on should access roughly 10 of them, if it has 100,000 elements it should
access not more than 20. Roll your own implementa/on (only use loops and if
statements). Basically it should run in O(log n) opera/ons.
>>> first_one( [0,0,0,0,0,0,1,1] )
6
>>> first_one( [1,1] )
0
>>> first_one( [0,0,0] )
-1
2. Repeat the exercise except this /me write a func/on called last_zero(L) that
returns the posi/on of the last 0. If helpful, you can make a call to your own
func/on first_one(L)
Study Refined Binary Search
The version of binary search we developed in class returns SOME
POSITION where value v is found in the given list L (and -1 if v is
not in the list).
Open the file called binary_search_refined.py. It contains a refined
binary search version that returns THE FIRST posi/on the value v
is found in L (and -1 if v is not in L)
1. Study and understand the solu/on
2. Think of how just one call to binary_search_refined.py would
resolve the previous first_one problem (and different variants
of such problem)
PART 2: SORTING
Task 7: Selec/on Sort
See file selec/on_sort.py to recall the selec/on sort
algorithm we studied and developed in class.
• Given the unsorted list [6, 5, 4, 3, 7, 1, 2] write down
what the contents of the list would be a?er each
itera/on (of the outer loop) as the list is sorted using
the selec/on sort
6 Programming Exercises
Recall from the analysis we did in class that selec/on sort does roughly n2
opera/ons (more precisely, O(n^2)) on a list of size n. As contrast, merge sort
does at most O( n log2 n) opera/ons. You can think of python’s sort as also
doing at most O( n log2 n) opera/ons (although it is not exactly true).
Open file applica/ons.py and program (and test) the 6 func/ons described
there. All your solu/ons should perform
at most O(n log n) opera/ons.
The only Python func/on you can use is “.sort” or “sorted” (since you know
something about the number of opera/ons they take and how they work
roughly). You can also use .append and assume one append call takes constant
number of opera/ons.
DO NOT USE DICTIONARIES. DICTIONARIES are black boxes, for now. Their
running /me analysis you will only study in the 2nd year.
BONUS TASK 8: CHALLENGE ANALYSIS:
The function below sorts the given list L. Can you figure out how
many operations it takes in the worst case? In other words is it
better of worse or the same as as selection sort (selec. sort does
O(n2) operations). What about merge sort? Think of L being a list where
elements are ordered from biggest to smallest. That is the worst case
for the below algorithm. You can assume that .append and .pop(0) take
constant number of operations. min takes linear on a list of size n.
You can find rough running times of Python’s operations here:
https://wiki.python.org/moin/TimeComplexity
AFTERWARDS, AT HOME:
--- Study the inser/on sort from the (Prac/cal Programming)
textbook. It is yet another algorithm that takes quadra/c number
of opera/ons, i.e. O(n2), to sort. Try to figure out why in the worst
case it takes quadra/c number of opera/ons?
--- Implement bubble sort
https://en.wikipedia.org/wiki/Bubble_sort
Bubble sort is also quadra/c algorithm in the worst case