Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Sorting11-2-2011Opening DiscussionMinute essay comments:Will your final project game look like what we did in class last time?Getting diagonal movement with keys.User input to draw stuff. (No API call.)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 SolutionsWriting TransformsLast 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.MotivationThere 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 SortingIf 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(n2) SortsWe 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 SortInner 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 SortThis 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:Find the smallest element and SWAP it into position if not already there.Outer loop:Repeat n-1 times so all elements are in the right place.Does only O(n) swaps, but still O(n2) comparisons.Insertion SortInner loop:Take the next element and shift it down to the right spot.Outer loop: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 WorkOne 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 EssayShow me what would happen after each iteration of the inner loop if we min-sort these values.4, 7, 1, 3, 8, 2Registration info:CS Major/Minor:CSCI 1321, 1323, 1120Watch for e-mail about CSCI 3194Others:CSCI 1321, PHED
View Full Document