A Computer Science Tapestry10.1From practice to theory and back againIn theory there is no difference between theory and practice, but not in practicez We’ve studied binary search: requires a sorted vector¾ Much faster than sequential search (how much)¾ Add elements in sorted order or sort vector after addingz Many sorting algorithms have been well-studied¾ Slower ones are often “good enough” simple to implement¾ Some fast algorithms are better than others• Always fast, fast most-of-the-time• Good in practice even if flawed theoretically?z New algorithms still discovered¾ Quick sort in 1960, revised and updated in 1997A Computer Science Tapestry10.2Tools for algorithms and programsz We can time different methods, but how to compare timings?¾ Different on different machines, what about “workload”?¾ Mathematical tools can help analyze/discuss algorithmsz We often want to sort by different criteria¾ Sort list of stocks by price, shares traded, volume traded¾ Sort directories/files by size, alphabetically, or by date¾ Object-oriented concepts can help in implementing sortsz We often want to sort different kinds of vectors: string and int¾ Don’t want to duplicate the code, that leads to errors¾ Generic programming helps, in C++ we use templatesA Computer Science Tapestry10.3To code or not to code, that is the …z Should you call an existing sorting routine or write your own?¾ If you can, don’t rewrite code written and accessible¾ Sometimes you don’t know what to call¾ Sometimes you can’t call the existing library routinez In C++ there are standard sort functions that can be used with built-in arrays and with both vectors and tvectors¾ These are accessible via #include <algorithm>¾ These are robust and fast, call sort(…) or stable_sort(…)• Can’t study the code, it’s not legiblez We’ll use sorts in #include “sortall.h”¾ Work only with tvector, as efficient as standard sorts, but code is legibleA Computer Science Tapestry10.4On to sorting: Selection Sortz Find smallest element, move into first array location¾ Find next smallest element, move into second location¾ Generalize and repeatvoid SelectSort(tvector<int> & a)// precondition: a contains a.size() elements// postcondition: elements of a are sorted{int k, index, numElts = a.size();// invariant: a[0]..a[k-1] in final position for(k=0; k < numElts - 1; k+=1) {index = MinIndex(a,k,numElts - 1); // find min elementSwap(a[k],a[index]);}}z How many elements compared? Swapped?¾ Total number of elements examined? N + (N-1) + … + 1¾ How many elements swapped?¾ This sort is easy to code, works fine for “small” vectorsA Computer Science Tapestry10.5Selection Sort: The Code (selectsort2.cpp)void SelectSort(tvector<int> & a)// pre: a contains a.size() elements// post: elements of a are sorted in non-decreasing order{int j,k,temp,minIndex,numElts = a.size();// invariant: a[0]..a[k-1] in final positionfor(k=0; k < numElts - 1; k++){ minIndex = k; // minimal element indexfor(j=k+1; j < numElts; j++){ if (a[j] < a[minIndex]){ minIndex = j; // new min, store index}}temp = a[k]; // swap min and k-th elementsa[k] = a[minIndex];a[minIndex] = temp;}}A Computer Science Tapestry10.6What changes if we sort strings?z The parameter changes, the definition of temp changes¾ Nothing else changes, code independent of type• We must be able to write a[j] < a[k] for vector a¾ We can use features of language to capture independencez We can have different versions of function for different array types, with same name but different parameter lists¾ Overloaded function: parameters different so compiler can determine which function to call¾ Still problems, duplicated code, new algorithm means …?z With function templates we replace duplicated code maintained by programmer with compiler generated codeA Computer Science Tapestry10.7Creating a function templatetemplate <class Type>void SelectSort(tvector<Type> & a)// pre: a contains a.size() elements// post: elements of a are sorted in non-decreasing order{int j,k,minIndex,numElts = a.size();Type temp;// invariant: a[0]..a[k-1] in final positionfor(k=0; k < numElts - 1; k++){ minIndex = k; // minimal element indexfor(j=k+1; j < numElts; j++){ if (a[j] < a[minIndex]){ minIndex = j; // new min, store index}}temp = a[k]; // swap min and k-th elementsa[k] = a[minIndex];a[minIndex] = temp;}}z When the user calls this code, different versions are compiledA Computer Science Tapestry10.8Some template detailsz Function templates permit us to write once, use several times for several different types of vector¾ Template function “stamps out” real function¾ Maintenance is saved, code still large (why?)z What properties must hold for vector elements?¾ Comparable using < operator¾ Elements can be assigned to each otherz Template functions capture property requirements in code¾ Part of generic programming¾ Some languages support this better than othersA Computer Science Tapestry10.9From practical to theoreticalz We want a notation for discussing differences between algorithms, avoid empirical details at first¾ Empirical studies needed in addition to theoretical studies¾ As we’ll see, theory hides some details, but still worksz Binary search : roughly 10 entries in a 1,000 element vector¾ What is exact relationship? How to capture “roughly”?¾ Compared to sequential/linear search?z We use O-notation, big-Oh, to capture properties but avoid details¾ N2is the same as 13N2is the same as 13N2+ 23N¾ O(N2), in the limit everything is the sameA Computer Science Tapestry10.10Running times @ 106instructions/sec318 centuries18.3 hr16.7 min0.0000301,000,000,00011.6 day19.91.00.0000201,000,0002.78 hr1.6610000.100000.000017100,0001.7 min0.1329000.010000.00001310,0001.00.0100000.001000.0000101,0000.10000.0006640.000100.0000071000.00010.0000330.000010.00000310O(N2)O(N log N)O(N)O(log N)NA Computer Science Tapestry10.11What does table show? Hide?z Can we sort a million element vector with selection sort?¾ How can we do this, what’s missing in the table?¾ What are hidden constants, low-order terms?z Can we sort a billion-element vector? Are there other sorts?¾ We’ll see quicksort, an efficient (most of the time) method¾ O(N log N), what does this mean?z Sorting code for different algorithms in sortall.h/sortall.cpp¾ Template functions, prototypes in .h file, implementations in .cpp file, must have