Make sure all programs are saved to your cs21/labs/09 directory. Files outside this directory will not be graded.
$ update21
$ cd ~/cs21/labs/09This is a two part assignment:
Sort Visualization - In visual_sort.py, you will write a graphics-based program that allows users to visualize and compare how sorting algorithms work. Make use of the Zelle Graphics Documentation.
Music Analysis - In music_sort.py, you will write a program that works with the same dataset as last week, but allows users to filter songs by a keyword and then sort songs based on play count. It also prints the top 25 most played artists.
In this part of the lab you will write a program to visualize two different sorting algorithms: selection sort and bubble sort. First, analyze and run the starter code in visual_sort.py. You should see a picture similar to the one below, with 10 random numbers ordered randomly.
Your task is to complete the program, visual_sort.py, to create a visualization of how two different sorting algorithms work. There are more detailed requirments below, but at a high level your program should:
Allow the user to choose the number of numbers to sort (modify the starter code for this part - you may also want to modify the width of the window to accommodate different user choices).
Allow allow the user to see how a particular sorting algorithm changes a list from unsorted to sorted, one swap at a time.
Work for both bubble sort and selection sort.
Here are two example of the program running. Note that the circles are just to show the user’s clicks - you do not need to have them in your final program.
Selection Sort
$ python3 visual_sort.py
Enter number of items to sort: 8
Enter 's' for selection sort or 'b' for bubble sort: sBubble Sort
$ python3 visual_sort.py
Enter number of items to sort: 8
Enter 's' for selection sort or 'b' for bubble sort: bYou must implement both selection sort and bubble sort (you may use in-class code as a starting point, but no built-in sorting algorithms).
You should use the functions in the starter code, no additional functions! (Hint: how can you modify swap? When you swap two numbers, you do not need to use move or change their positions in any way. You can use getText() and setText() to manipulate the Text objects in place.)
Your program should, at a minimum, update the visualization after each swap in both sorting algorithms.
Allow the user to choose the number of numbers to sort, as well as choose the type of sorting algorithm to use.
You should use a header Text object to explain the steps as they are happening (although it doesn’t have to look exactly like the demo)
Use getMouse() to pause after every swap in the sorting algorithms.
In this part the goal is to allow the user to enter a keyword, then find all the song titles that contain this keyword. Finally, sort these songs by their associated play count. The user should be able to keep entering keywords until they hit ENTER. After they hit ENTER, a list of the top 25 most played artists should be displayed. Here is an example on Music Library A (see the end of the lab for an example on the provided test file music-small.txt).
$ python3 music_sort.py
========== Welcome to Music Information =========
Enter A,B,C for music library: A
Enter keyword or ENTER to quit: love
Song Name Play Count
--------- ----------
The Power of Love 1470
Lucky Love 517
Dance of Love 253
Friday I'm in Love 131
Love They Say 81
Undying Love 40
If It's Love 19
I Love My Car 9
And I Love Her 8
The World You Love 7
She Loves You 6
Love Me Do 6
Fools in Love 6
Can't Buy Me Love 6
Who Loves You 5
Love Drought 5
Love Love Sugar 4
Sound of Love 2
She Will Be Loved 1
Seasons of Love 1
Seasons of Love B 1
Only Love 1
American Love 1
All Is Full Of Love 1
Enter keyword or ENTER to quit: music
Song Name Play Count
--------- ----------
Irish Dance Music 267
Enter keyword or ENTER to quit: wonder
Song Name Play Count
--------- ----------
Wonderwall 51
Winter Wonderland 3
Mr. Wonderful 2
Enter keyword or ENTER to quit: happy
Song Name Play Count
--------- ----------
My Happy Ending 5
Happy New Year 1
Happy New Year B 1
Enter keyword or ENTER to quit: hello
Song Name Play Count
--------- ----------
Hello 21
Hello Helicopter 1
Enter keyword or ENTER to quit: america
Song Name Play Count
--------- ----------
American Girl 71
American Girls 55
American Pie 37
American Idiot 35
American Love 1
Enter keyword or ENTER to quit: wish
Song Name Play Count
--------- ----------
Wish We Were Older 5
What You Wish To Do 2
Wish You Were Here 1
Enter keyword or ENTER to quit: maybe
Song Name Play Count
--------- ----------
Maybe; This Time 23
An Ode to Maybe 2
Enter keyword or ENTER to quit: orange
No songs with keyword orange!
Enter keyword or ENTER to quit: black
Song Name Play Count
--------- ----------
Black Blade 53
Paint it Black 19
Enter keyword or ENTER to quit:
Top 25 Most Played Artists:
Toto: 1579
Foster the People: 1522
Céline Dion: 1470
Fun.: 1397
Air: 1219
Two Steps From Hell: 1041
: 1005
Lana Del Rey: 932
Tegan and Sara: 778
The Killers: 734
E.S. Posthumus: 646
Jimmy Eat World: 635
The Beatles: 621
Ah Nee Mah: 599
Coldplay: 590
Garbage: 556
Blondie: 520
Ace of Base: 517
Green Day: 504
Belle & Sebastian: 468
Metro Station: 467
Sting: 465
Guster: 461
Jack's Mannequin: 448
Train: 438First write a TDD that stubs out all the functions you will need for this part. Feel free to use the code we have working on in class for sorting and searching, but no built-in sort/search algorithms may be used.
For the keyword part, if the song title contains the keyword in any case, it should be included (for just this part, it is okay to use the in operator). Similarly to Lab 8, you can use <str>.lower() to make a version of the keyword and a version of the artist in all lowercase (for ease of comparison). Filter the list of songs by keyword, then sort this new list by play count.
For the most played artist part, the total count of how many times the artist is played is the sum of the times the artist’s songs have been played. Think about how to obtain a list of lists containing both artist and cumulative play count information. For example, say I am considering the artist Lorde and Music Library C:
...
Green Light,Lorde,Melodrama,234,42,08/17/17; 4:04 AM
...
Homemade Dynamite,Lorde,Melodrama,189,26,08/17/17; 3:58 AM
...The first time I see the artist Lorde, the song is “Green Light” and it’s played 42 times. So I will search through the list of artists/counts I have so far and if I don’t find Lorde, I will create a new mini-list:
[“Lorde”,42]
and append it onto my list of artists. Then the next time I see Lorde, I will search again and find this mini-list, and add on 26 to 42:
[“Lorde”,68]
Finally, when I am finished looking at all the songs, I will sort the resulting artist list. Question: what type of search should we use to find the location of an artist we’ve previously seen? Binary search is not required for this part, but think about how you might use it for this part!
It is not required, but it would be ideal if you only had one sorting function for this lab, that will take in a list of lists and an index, and sort the list based on the value at the given index (for each mini-list in the overall list). Such a function would work for both the keyword part and the artist part.
Note that different sorting algorithms will treat items with the same value differently. For example, there is no “right” order for songs that all have play count one, so don’t worry if these are ordered differently than the examples in the writeup.
Here is another example from Music Library B:
$ python3 music_sort.py
========== Welcome to Music Information =========
Enter A,B,C for music library: B
Enter keyword or ENTER to quit: tuna
Song Name Play Count
--------- ----------
O Fortuna (Final) 2
O Fortuna 1
Fortunate Son 1
Fortunate Fool 1
Enter keyword or ENTER to quit:
Top 25 Most Played Artists:
Radiohead: 2066
Modest Mouse: 737
Beck: 609
Gomez: 588
Air: 568
Tool: 563
Thievery Corporation: 433
The Shins: 420
Franz Ferdinand: 415
Neil Young: 413
Nick Cave & The Bad Seeds: 408
Girl Talk: 312
Led Zeppelin: 312
Groove Armada: 300
The Crystal Method: 274
The Beastie Boys: 250
Gorillaz: 245
The Arcade Fire: 236
The Rolling Stones: 231
PJ Harvey: 230
Bob Schneider: 206
David Bowie: 190
Cat Power: 183
Mumford & Sons: 177
Sigur Ros: 176And finally, here is an example on the small test library:
$ python3 music_sort.py
========== Welcome to Music Information =========
Enter A,B,C for music library: small
Enter keyword or ENTER to quit: life
Song Name Play Count
--------- ----------
Part of Your Life 10
Live Life 9
Enter keyword or ENTER to quit: let
Song Name Play Count
--------- ----------
Let It Go 6
Snaggletooth 5
Let It Go 4
Enter keyword or ENTER to quit:
Song Name Play Count
--------- ----------
Top 25 Most Played Artists
Lana Del Rey: 144
Lorde: 68
The Cranberries: 39
Aquilo: 10
The Smiths: 10
Zayde Wølf: 9
Idina Menzel: 6
Vance Joy: 5
James Bay: 4
Marina and The Diamonds: 3There are many ways to make your sort visualization more interesting! Here are a few examples that involve both animation, and a color gradient like we saw in Lab 6. The speed of the swap is meant to show that swap is an O(1) operation no matter how far apart the elements are.
Another extension idea is to create “pointers” to show how the nested for loop indices are updated. This would make your animation more realistic. In the two videos below, it might seem that selection sort is faster than bubble sort because it has fewer swaps, but that is actually not the case since it took a lot of effort to find the minimum element each time. Try to create an animation that accurately reflects the runtime of each sorting algorithm.
Selection Sort Colors + Animation
$ python3 visual_sort.py
Enter number of items to sort: 10
Enter 's' for selection sort or 'b' for bubble sort: sBubble Sort Colors + Animation
$ python3 visual_sort.py
Enter number of items to sort: 10
Enter 's' for selection sort or 'b' for bubble sort: bOnce you are satisfied with your programs, fill out the questionnaire in QUESTIONS-09.txt. Then run handin21 a final time to make sure we have access to the most recent versions of your file.