ARRAYS and ALGORITHMS part 1
An
array is an ordered list of items. All
programming languages that I am aware of include implementations of
arrays. Think first of a list of students in, say, CS 100
arranged alphabetically. There's a first student on this
alphabetic list (which is ordered alphabetically by last
names)--Aardvark, Fred. The next student might be Adams, Susan,
then Braden, William. The last person might be Beverly Zygmunt (a
real person, a former GTA--during her time here she was always the last
person in the student directory). This list would not be very
useful if it was not ordered: the Knoxville phone book is an
ordered list--imagine trying to find someone's phone number if this was
NOT ordered! Programming languages vary in terms of exactly how
they manage lists. But a common way is if the list is called,
say, myList, then the first element would be myList[0]--the 0th element
in reality. This is similar to for
in in range(10) where i runs not from 1 to 10 but from 0 to 9.
Python has both lists and tuples. There are differences
which we will not worry about here. There are a several ways to
get lists. One is to say, for example,
numbers = [17, 67, -2, 33, 45, 19, 106, 3]
This list has 8 elements: numbers[0] has the value 17, numbers[1]
has the value 67, numbers[7] has the value 3. You can also create
a list by reading values into it--this works a bit differently:
mylist = [] #this creates an
"empty" list
for i in range(8):
number = input("type in a value:")
mylist.append(number)
#this adds number onto the end of the list--the list has grown by 1
value
or
mylist = []
for i in range(8):
name = raw_input("type in a name:")
mylist.append(name)
Here we could have asked the person running the program to tell us
first how many values or names there would be:
howmany = input("how many names?")
then we could have said for i in range(howmany) to input that
number of names or values.
At any rate, we now have a list. The list may or may not be
sorted: the list of numbers above was not sorted, and the names
we read in might or might not be sorted--it would depend on what YOU
did about reading them in.
-------------------------------------------------
GETTING OUR LIST SORTED
We want the smallest value to be at mylist[0], etc, and the greatest
value to be at the end of the list. In the list of numbers above,
the smallest value was at numbers[2] and the largest value at
numbers[6]. So obviously, this list is not yet sorted.
There are a great many different sorting routines--some are a lot
better than others in terms of how long they take to sort a list.
Some are a lot better than others if your primary concern is not how
long it takes to sort a list but rather how long it takes you to write
the program that does the sorting. We'll look at a couple of
routines to sort our list of numbers (or names).
--------------------
THE BUBBLE SORT
This is probably the easiest of the sorting routines to
understand--it's also not very efficient in terms of sorting
speed. Let's first repeat the list of numbers above:
numbers = [17, 67, -2, 33, 45, 19,
106, 3]
We are going to run through this list comparing successive values
(0 vs 1, 1 vs 2, 2 vs 3, etc). We certainly want for any value of
i to have numbers[i] <= numbers[i+1]: this means that we want
numbers[0] <= numbers[1], and numbers[1] <= numbers[2],
etc. So what we will do is to compare successive pairs of values,
and if, say, numbers[3] > numbers[4] then we will switch/swap those
two values, so that what was numbers[4] becomes numbers[3] and
vice versa. So our main line of code will be:
for i in range(7): #NOT 8! see below!
if mylist[i] >
mylist[i+1]: #we need to
swap/switch values if this is true
temp =
mylist[i]
#save this value
mylist[i] = mylist[i+1]
mylist[i+1] = temp
if mylist[i] <= mylist[i+1] we do NOT swap values here. Let's
follow whatt happens with the list as i goes from 0 to 6:
1) i=0 numbers[0] vs numbers[1]: 17 < 67 do not
switch. 17, 67,
-2, 33, 45, 19, 106, 3
2) i=1 numbers[1] vs numbers[2]: 67 > -2
switch/swap
17, -2, 67, 33, 45, 19, 106, 3
3) i=2 numbers[2] vs numbers[3]: 67 > 33
switch
17, -2, 33, 67, 45, 19, 106, 3
4) i=3 numbers[3] vs numbers[4]: 67 > 45
switch
17, -2, 33, 45, 67, 19, 106, 3
5) i=4 numbers[4] vs numbers[5}: 67 > 19
switch
17, -2, 33, 45, 19, 67, 106, 3
6) i=5 numbers[5] vs numbers[6]: 67 < 106 do not
switch 17, -2,
33, 45, 19, 67, 106, 3
7) i-6 numbers[6] vs numbers[7]: 106 > 3
switch
17, -2, 33, 45, 19, 67, 3, 106
is this list sorted? NO! have we made progress? Well, note
that the largest number--106--is at the end of the list. Smaller
numbers have inched toward the front of the list (which is why it's
called the bubble sort--small numbers bubble up slowly toward the
front). So we need to go through the list again--try it!
The list would now appear as -2, 17, 33, 19, 45, 3, 67, 106 so the 2nd
largest value is now in the next-to-last position. The smallest
number is at the front, but the next smallest value has a ways to go to
reach its proper slot. So here's the overall code to make things
work:
flag = 1 #a 1 here says we assume the list is not
fully sorted
while flag >
0:
#continue until fully sorted
flag =
0
# we're hoping things are all sorted.......
for i in range(7):
if mylist[i] >
mylist[i+1]: #bah! we
found something out of order--swap values
temp = mylist[i]
mylist[i] = mylist[i+1]
mylist[i+1] = temp
flag =
1
#this means we found something not sorted in the list
print
mylist
#prints sorted list
So what this does is we keep making passes through the list.
Before each pass we set the flag to 0 indicating that nothing is out of
order--YET! If we ever do find values that need swapping, flag
gets set to 1 meaning we're going to need another pass through the
list. Suppose when we drop out of the for loop flag is still
0: this means that we didn't need to swap any values--in each
case numbers[1] was <= numbers[i+1], and so everything is sorted,
and since flag is still 0 at the end of the for loop, this also drops
us out of the while loop, so we're done, and we can print the
list.
--------------------------------------------