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.

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.

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:

—**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`.—**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.)— since we're ignoring case, deciding on the correct order of strings**compare(x, y)**`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*.— as with**bubble_sort(L, ascending)**`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.

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]

- 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. - 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. - 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.

- 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']

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.

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.