Exercise 7: Bubble Sort

This week you'll be getting more practice with loops and lists by sorting usernames.

  • sort.py - This part may be completed in pairs if you wish.

Program background

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):

If you'd prefer visualizations without folk dancing (but why??), you can play through this version step-by-step, or compare bubble sort to (and race it with) other sorting algorithms here.

Program requirements

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:

  1. is_sorted(L, ascending)L is a list of strings, ascending is a boolean. This function should return True if L is sorted in the order indicated by ascending; from A to Z if ascending is True, or from Z to A if ascending is False.
  2. swap(L, i, j)L is a list of strings, i and j are valid indexes into the list. Your function should exchange the values at i and j, but be careful not to lose either of the values! (Return a copy of the list with the modifications made.)
  3. compare(x, y) — since we're ignoring case, deciding on the correct order of strings x and y is not as straightforward as just checking x < y. This function should return a numeric value - a negative if x comes before y alphabetically, a positive if it's the other way, and 0 if x and y are the same thing ignoring case.
  4. bubble_sort(L, ascending) — as with is_sorted, L is a list of strings, ascending is a boolean indicating the order of the list (A to Z, or Z to A). After every pass through the list, your function should print the current state of L, so you can watch the sorting happen. (Return a copy of the list with the modifications made.)

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.

How do we approach this?

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]
  1. Starting with the bubble_sort() function, see how you could translate that pseudocode to real Python code using the other functions in your file. It doesn't have to be perfect! You can always fix it later. Just get a general idea of how your functions might fit together first.
  2. Next, implement the swap() and compare() functions (neither of these rely on other functions to work). Test them out using the examples given in the skeleton, and using your own examples.
  3. Once you're confident with compare(), implement is_sorted() (which will need to compare list elements in order to work). If you need some help using compare():

    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.
  4. Finally, go back and verify your bubble_sort() implementation. Don't forget to print out the state of the list every time you make a pass!
>>> 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']

Commenting your code

Once again, some of your program points will come from commenting your code.

  • Add a 1-2 sentence description of the program and its function to the top of your code.
  • Include comments within your code describing what you're doing. You don't need to comment on every line of code, but be clear in your explanations.

Submitting your files

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.

If you worked in a pair, only one person will need to hand in the code.

Note that the dropbox will close at noon on 17 March, so be sure to submit your files before then.