Sorting 11 2 2011 Opening Discussion Minute essay comments Getting diagonal movement with keys User input to draw stuff No API call Will your final project game look like what we did in class last time How much do these graphics calls translate to the real world You can listen to mouse wheel for scrolling Resubmit assignments whenever Just e mail me Why can t Putty pop up GUI windows IcP Solutions Writing Transforms Last time we mentioned AffineTransforms but didn t see what they can do Let s take some time now to write code that uses an AffineTransform in our drawing Motivation There are many reasons that you might want the data you are working with to be in a particular order If nothing else humans often like seeing things in certain orders It turns out that ordered data can be beneficial for the computer as well Putting things in order by some value is called sorting Methods of Sorting If I ask you to sort a bunch of items how would you go about doing it Describe your approach How does it vary for different types or configurations of objects O n Sorts 2 We are going to look at three different sorting techniques today These sorts all do work that is proportional to the square of the number of elements That isn t good for large collections but the sorts are fairly simple to write These work in place so we use arrays Each involves an inner loop that reorders things and an outer loop that makes the inner one happen over and over Bubble Sort Inner loop Compare adjacent elements and swap them if they are out of order Outer loop Repeat n 1 times or until no swaps are done The latter option is called a flagged bubble sort Selection Sort This is often called a min sort or a max sort depending on how you write it I ll describe a min sort here Inner loop Outer loop Find the smallest element and SWAP it into position if not already there Repeat n 1 times so all elements are in the right place Does only O n swaps but still O n 2 comparisons Insertion Sort Inner loop Outer loop Take the next element and shift it down to the right spot Run through all the elements starting with the second This sort is actually a bit faster factor of 2 on random data It is really efficient on nearly sorted data Watching Them Work One advantage of doing graphics before sorting is that we can write code to visualize what is happening when we sort numbers with these sorts Let s write this code and watch our sorts work Minute Essay Show me what would happen after each iteration of the inner loop if we min sort these values 4 7 1 3 8 2 Registration info CS Major Minor CSCI 1321 1323 1120 Watch for e mail about CSCI 3194 Others CSCI 1321 PHED 1137
View Full Document
Unlocking...