This week you'll be getting more practice with loops and lists by sorting usernames.
For this lab, we will be investigating a method of sorting values, called bubble sort.
You've probably sorted many things in your life, but now that you're a programmer, it's time to start thinking about exactly how you approach that task. There are many different ways to actually go about doing things, and each of them is called an algorithm. Since we're sorting things, we'll look at sorting algorithms.
Fundamentally, a sorting algorithm should take a list L and produce a sorted version of L. For example, sorting the list [3,2,9,6,5] in ascending order should return [2,3,5,6,9]; likewise, sorting it in descending order should return [9,6,5,3,2]. In this lab, you will be developing an implementation of bubble sort that can handle both of these cases.
For a visualization of how bubble sort actually works, I'm going to turn it over to this group of Hungarian folk dancers (yes, seriously):
Once again, we've created a bit of skeleton code including function headers and definitions: sort.py
To accomplish the task of sorting strings alphabetically, ignoring case, your program should implement the following functions:
Note: for this assignment, your functions should return a copy of the modified list (as you did with remove_outliers()). We'll look at modifying a list in place in later assignments.
First, put on your sorting hat:
Now let's talk algorithms.
Bubble sort makes a number of "passes" through the list, swapping values that are in the "wrong order" relative to the desired ascending/descending order. In pseudocode ("sort-of" code):
while list not sorted: for index = 1 to N: if list[index-1] and list[index] in wrong order: swap list[index-1] and list[index]
if compare(A,B) < 0: # in this case, we know that A is "less than" B, or comes before it alphabetically. elif compare(A,B) == 0: # in this case, we know that A is the same as B. else: # in this case, we know that A comes after B alphabetically.
>>> bubble_sort(['Adam','abel','bArt','baker'], False) ['Adam','bArt','baker','abel'] ['bArt','baker','Adam','abel'] >>> bubble_sort(['abel','Adam','baker','bArt'], False) ['Adam', 'baker', 'bArt', 'abel'] ['baker', 'bArt', 'Adam', 'abel'] ['bArt', 'baker', 'Adam', 'abel']
Once again, some of your program points will come from commenting your code.
As usual, you'll be handing in your lab work via the course Learn@UW dropboxes. Navigate to our 301 course page, and click the Dropbox link in the top navigation bar. You should see a dropbox for Program 7 - this is where you should hand in your sort.py file.
Note that the dropbox will close at noon on 17 March, so be sure to submit your files before then.