We will explore lists using two algorithms we discussed in lecture: finding the maximum and bubble sort.
Here is an algorithm to find the maximum in an list of data:
1. Input n (the length of the list) 2. Input a list of values A[0], A[1], ..., A[n-1] 3. Set i = 0 4. Set max_so_far = A[0] 5. Do the following while i < n-1: a. Add 1 to i b. If A[i] > max_so_far, set max_so_far = A[i] 6. Output max_so_far
To create a list of data, we can simply define a variable (say, A) and list the data values in brackets, like follows:
A = [4, 7, 3, 9, 8]
To display the contents of a list, we can simply print the list:
print A
In our algorithms, we often say that the list has n elements and we use n in our solution to determine how many times to loop. Python has a function called len that gives us the length of the list (i.e. how many elements it has). So len(A) for the list above would return 5.
Now we can implement the algorithm in Python:
# findmax.py
# Finds the maximum integer in a list of integers
def main():
A = [4, 7, 3, 9, 8]
i = 0
max = A[0]
while i < len(A)-1:
i = i + 1
if A[i] > max:
max = A[i]
print "The maximum positive integer is", max
main()
Here is the output so far:
The maximum positive integer is 9
But how do we know if this is right? To get a better idea of what we're doing, we can add debugging statements that output the variables at key points of the algorithm, just as we did when we traced in class:
# findmax.py
# Finds the maximum integer in a list of integers
def main():
A = [4, 7, 3, 9, 8]
print A
i = 0
max = A[0]
print i, " ", max
while i < len(A)-1:
i = i + 1
if A[i] > max:
max = A[i]
print i, " ", max
print "The maximum positive integer is", max
main()
Here is the output now:
[4, 7, 3, 9, 8] 0 4 1 7 2 7 3 9 4 9 The maximum positive integer is 9
This looks better. For each value we look at, if it's larger than the current maximum, then it becomes the new maximum.
Here is a simple algorithm for Bubble Sort:
1. Input n
2. Input a list of values A[0], A[1], ..., A[n-1]
3. Do the following n-1 times:
a. Let i = 0
b. Do the following n-1 times:
i. If A[i] > A[i+1], exchange A[i] and A[i+1]
ii. Add 1 to i
4. Output A
To implement this algorithm, we need to deal with two things. First, we need to execute a loop a specific number of times. Remember that the for instruction does this. If we want to repeat something n-1 times, we can write
for x in range(n-1):
This creates a variable x that counts from 0 to n-2, one for each iteration. In this example, we are not using x in our computation itself; it is merely counting the number of loop iterations. In general, we could use the variable x as part of our computation if we needed it. Now, n is actually the size of the list, so we should write
for x in range(len(A)-1):
Now, how do we exchange A[i] and A[i+1]? There is no exchange command in Python. We can do this by using the following sequence of steps:
temp = A[i] A[i] = A[i+1] A[i+1] = temp
Now we can put the entire program together:
# Python implementation of Bubble Sort
def main():
A = [8, 4, 9, 3, 7]
print "Before sort: ", A
for j in range(len(A)-1):
i = 0
for k in range(len(A)-1):
if A[i] > A[i+1]:
temp = A[i]
A[i] = A[i+1]
A[i+1] = temp
i = i + 1
print "After sort: " , A
main()
Note the use of print statements so we can display the contents of the list before and after the sort.
Here is the output of this program:
Before sort: [8, 4, 9, 3, 7] After sort: [3, 4, 7, 8, 9]