As always, run update21 to get any necessary files into your cs21/labs/09 directory. Then cd into cs21/labs/09 and create the programs for lab 9 in this directory.

• Gain a deeper understanding of sorting algorithms.
• More practice reading data from a file into a list of lists.
• Use visualizations as an aid to understanding algorithms.

This week's lab requires you to write two programs that will test and hopefully deepen your understanding of sorting algorithms.

The file /usr/local/doc/twitter2009.csv contains data on all Twitter users who had more than 10,000 followers in the summer of 2009. It was collected as part of a research project into the dynamics of Twitter's social network. Each line in the file contains the name, username, bio, and number of followers (in that order) for one Twitter account. The first five lines of the file look like this:

Jack Dorsey|jack|Creator, Chairman and co-founder of Twitter|895829
Biz Stone|biz|Co-founder of Twitter, Inc.|922633
crystal|crystal|Twitter Support|14062
Evan Williams|ev|CEO of Twitter|1107133
sara|sara|N/A|10922

Currently the lines are ordered based on when the user's profile was created. Your task is to write a program, twitter-sort.py, that sorts these lines in order of most followers to least followers, and then prints out all data for the top 20 users.

Make sure your program meets all of the following specifications:

• Use top-down design and incremental development. A good program design and good use of functions is part of the grade.
• Read in the data on Twitter users and store it in a list of lists, similar to what you did last week with the climate data. The number of followers should be stored as an int. The file uses a pipe symbol ("|") as a delimiter.
• Implement a sorting algorithm that orders the list of lists from most followers to least followers. You may not use Python's built-in sort method.
• Print out all the data (name, username, bio, number of followers) for the top 20 Twitter users in terms of followers. You are free to format the output however you want, but it should be easy to read. Some of the bios are long—you may want to truncate these with the slicing operation. The example output below shows how you might format your output into a table. What you see is the heading of the table and rows 6-10 (we're not going to give away the entire answer!):

#  | Name           | Username      | Bio                                                | Followers
----------------------------------------------------------------------------------------------------
...
6  | Twitter        | twitter       | Always wondering what everyone's doing.            | 1854051
7  | Barack Obama   | BarackObama   | 44th President of the United States                | 1788362
8  | Ryan Seacrest  | RyanSeacrest  | Get official tweets from Ryan and his producers ab | 1739051
9  | THE_REAL_SHAQ  | THE_REAL_SHAQ | VERY QUOTATIOUS, I PERFORM RANDOM ACTS OF SHAQNESS | 1692121
10 | Kim Kardashian | KimKardashian | Armenian Princess                                  | 1619765
...

In the 8 years since this data was collected, the top Twitter users have increased their followings manyfold. Here are recent rankings.

Part 2 of this assignment is more open-ended than our typical lab programs. Your task is to write a program, visualize-sort.py, that displays a visualization of how one particular sorting algorithm works. This visualization can work by printing strings to the terminal, or—for the extra challenge—by creating an animation using Zelle graphics. Your program should allow its users to see how a particular sorting algorithm changes a list from unsorted to sorted, one swap at a time. But it should do more than just that to help its users understand the algorithm. We encourage you to choose a different sorting algorithm from the one you used in part 1, but this is not required.

Below are links to examples of terminal-based visualizations for selection sort and bubble sort. These are examples; we would like to see if you can come up with something different. The goal is to help your users understand the inner workings of your chosen algorithm, however you see fit. Along the way, hopefully you will also deepen your own understanding.

• Selection sort visualization
• Bubble sort visualization

• Use top down design; don't put all of your code in main().
• Randomly generate a list of integers to sort. You should pick the length of the list, and the range of possible integers that may appear as elements in the list. The randrange function may be helpful here.
• Convey to the user how this randomly-generated list would go from unsorted to sorted according to the steps of your chosen algorithm. You should attempt to explain these steps visually and with text. It is not sufficient to just print out the list each time there's a swap:

  [4,10,8,2,2]
  [2,10,8,4,2]
  [2,2,8,4,10]
  [2,2,4,8,10]
  [2,2,4,8,10]
  

For an extra challenge, create a visualization of your sorting algorithm using the Zelle graphics library. Here are some examples:

• Selection sort visualization
• Bubble sort visualization
• Insertion sort visualization

You may find inspiration from these visualizations as well, even though they weren't created with Zelle graphics.

Put your program in a file called graphical-viz.py. If you complete this challenge, you do not also need to create a text-based visualization.

Once you are confident that your programs work, fill out the questionnaire in README-09.txt.

Then run handin21 a final time to make sure we have access to the most recent versions of the files required for this lab.