Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Sorting and Searching11-5-2010Opening DiscussionDo you have any questions about the quiz?IcP solutions.Do you have any questions about the assignment?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.Insertion SortInner loop:Take the next element and shift it down to the right spot.Use a while loop because we don't know how far it will go.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.SearchingMany times we have to search in our data for where something is.If the data is not sorted, we have to use a linear search which will look at every element, one after another, to see if any matches what we want.This is O(n).The methods on collections in Scala use this approach.Binary SearchIf the data is sorted, we can do something much better.We check the middle to see if it matches. If it does, return it. Otherwise, see if what we want is above or below the middle and repeat the process on only that half.This continually divides the things we are searching in half.Order?Performance of Binary SearchDividing something by a fixed fraction repeatedly leads to O(log n) speed.O(log n) is much better than O(n) when n is large. To see this, consider a base 2 log for 1000, 1000000, or 1000000000.Minute EssayWhat questions do you have?Remember to give me your schedule as soon as you can so I can make a decision about when PAD2 will be.Interclass problem:Use the System.nanoTime method to compare the speed of some
View Full Document
Unlocking...