CS21 Lab 9: Sorting

Due Saturday April 8, before midnight

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.


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

1. Top Twitter Users (from 2009)

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

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.

Requirements and tips

Make sure your program meets all of the following specifications:

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

2. Visualize a Sorting Algorithm

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.

Requirements and tips
Extra Challenge - Use graphics
For an extra challenge, create a visualization of your sorting algorithm using the Zelle graphics library. Here are some examples:

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.

Answer the Questionnaire; Run handin21

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.