In Python, an array is implemented as a list of data. We will explore arrays using two algorithms we discussed in lecture: finding the maximum and bubble sort.
Recall the algorithm to find the maximum in an array (vector) of data:
1. Input n 2. Input a vector of values A[0], A[1], ..., A[n-1] 3. Set i = 0 4. Set m = A[0] 5. Do the following while i < n-1: a. Add 1 to i b. If A[i] > m, set m = A[i] 6. Output m
To create a vector 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 an array, we can simply print the array:
print A
In our algorithms, we often say that the array 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 array (i.e. how many elements it has). So len(A) for the array 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.
Recall the algorithm for Bubble Sort:
1. Input n
2. Input a vector of values A[0], A[1], ..., A[n-1]
3. Do the following n 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 times, we can write
for x in range(n):
This creates a variable x that counts from 0 to n-1, 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 array, so we should write
for x in range(len(A)):
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)):
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 array 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]