CS 61B Lab 15 May 7-8, 2009 Sorting Games Goal: To help you practice sorting algorithms for the final exam. You MUST have a partner for this lab, unless there's an odd number of people and you are the odd one out. You'll also need lots of paper. Copy the Lab 15 directory by doing the following, starting from your home directory. cp -r $master/lab/lab15 . In this lab, you and your partner will help each other practice the in-place array versions of heapsort, quicksort, and quickselect. Then you will compete against another team for the fastest sorting time. Hour 1: ------- The lab directory includes a program called GimmeYoNumber, which prints two lists of 13 random numbers in the range 0...99. Although the numbers for "Opponent 1" and "Opponent 2" are different, the two lists have been scrambled exactly the same way, and will require exactly the same sequence of swaps to sort them. For now, take just the first list of numbers and write them in a row on a sheet of paper. One of you should then sort the numbers with in-place heapsort as described in the Lecture 30 notes, while your partner watches, catches your mistakes, and helps if you're uncertain of the details of the algorithm. To prepare for competition, you should diagram the sorting process in a particular way: each swap of two keys is written on a separate line, under the previous swap. For example, here's an illustration of selection sort. (Lined paper helps.) 83 18 72 21 93 44 7 21 ----------------------- 7 83 ----------------------- 21 72 ----------------------- 21 72 ----------------------- 44 93 ----------------------- 72 93 You must write down EVERY swap of two keys (unlike in the Lecture 30 notes, where I did entire removeMin() operations in one step). If you swap two identical keys (as often happens in quicksort, and can happen in heapsort), you must illustrate that too. You do not have to note when a key is swapped with itself; for instance, in the selection sort above, the 18 is swapped with itself, but I haven't written it down. In each row, you are allowed to write down keys that haven't moved, but you don't have to. (I've omitted them all in the example above.) This same format will be accepted on the final exam. When you're done, run GimmeYoNumber again and have your partner practice in-place heapsort. When you're confident that both you and your partner understand heapsort, repeat the process with in-place quicksort (exactly as described in the Lecture 31 notes) and in-place quickselect. When you practice quickselect, your goal is to find the median key (seventh out of thirteen). When you think you're ready to compete, or one hour has passed (whichever comes first), it's time to find another team to vanquish... Hour 2: ------- Find another team to compete against. (If you're the odd team out, wait until a game completes; the losers are required to play a second game.) You will play a round of heapsort and a round of quicksort. If each team wins one round, you'll have a quickselect tiebreaker. During each sort, either you or your partner will be the _lead_, and the other will be the assistant. Only the lead is allowed to write. The assistant is allowed to speak, point out mistakes, etc., but not to hold a writing instrument. The lead is allowed to write any diagrams that will help with sorting (e.g. heaps in tree form), in addition to the official answer. Designate one of yourselves to be the heapsort lead, and the other to be the quicksort lead. (Either of you can lead the quickselect tiebreaker; if one of you is clearly faster, they should get the job.) Decide which team is Opponent 1 and which is Opponent 2. To start a round of sorting, run GimmeYoNumber, which will generate one list for each team. Each team writes down their complete list on a sheet of paper. Then, it's up to you whether you want to be in eyeshot of the opposing team or not. Perform the sort. When you are done, yell "Sorted!". The team that declared themselves sorted first is the tentative winner. After making this statement, you must immediately hand your solution to the other team; you are not allowed to write on that paper again. The other team may finish their solution at their leisure, then hand it to you. The round ends with each team checking the other team's sort for errors. A team that has made an error (e.g. omitting a swap of two equal keys) loses unless both teams made an error, in which case the round must be repeated. Disputes on whether something is an error shall be adjudicated by the TA. The first team to win two rounds (including the quickselect tiebreaker if necessary) wins the game. If you lose the game, you must play a second game with a different team to get full marks for the lab. Please give preference to a team that hasn't had a chance to play yet. To get full marks for the lab, you must either play two games or win one. You are welcome to play additional games, though. Bonus ----- One in ten billion players will be the lucky winner of a FRIENDSHIP WITH BRITNEY SPEARS! To find out if you've won, enter the first ten digits printed by GimmeYoNumber into your cell phone. Check-off --------- 2 points: For playing one game against another team and losing. 4 points: For playing one game against another team and winning, or for playing games against two other teams.