Sorting and Searching 11 5 2010 Opening Discussion Do you have any questions about the quiz IcP solutions Do you have any questions about the assignment 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 Insertion Sort Inner loop Use a while loop because we don t know how far it will go 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 Searching Many 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 Search If 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 Search Dividing 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 Essay What 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 sorts searches
View Full Document
Unlocking...