### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# DATA STRUCTURES CS 261

OSU

GPA 3.95

### View Full Document

## 17

## 0

## Popular in Course

## Popular in ComputerScienence

This 20 page Class Notes was uploaded by Mrs. Maximo Lueilwitz on Monday October 19, 2015. The Class Notes belongs to CS 261 at Oregon State University taught by R. Metoyer in Fall. Since its upload, it has received 17 views. For similar materials see /class/224497/cs-261-oregon-state-university in ComputerScienence at Oregon State University.

## Reviews for DATA STRUCTURES

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/19/15

Chapter 4 Measuring Execution Time You would think that measuring the execution time of a program would be easy Simply use a stopwatch start the program and notice how much time it takes until the program ends But this sort of measurement called a wallclock time is for several reasons not the best characterization of a computer algorithm A benchmark describes only the performance of a program on a speci c machine on a given day Different processors can have dramatically different performances Even working on the same machine there X may be a selection of many alternative compilers for the V 1 same programming language For this and other reasons 1 computer scientists prefer to measure execution time in a I 1 more abstract fashion Algorithmic Analysis Why do dictionaries list words in alphabetical order The answer may seem obvious but it nevertheless can lead to a better understanding of how to abstractly measure execution time Perform the following mind experiment Abby Smith 9 5 4 98 4 5 Suppose somebody were to ask you to look up the Chris Smith 2 34 7832 telephone number for Chris Smith in the directory Fried Smi t1 4 35 35 4 5 for a large city How long would it take Now Jallf le Slf lth 845 392 3 95 Robln Smlth 436 9834 suppose they asked you to nd the name of the person with number 5648734 Would you do it How long do you think it would take Is there a way to quantify this intuitive feeling that searching an ordered list is faster than searching an unordered one Suppose n represents the number of words in a collection In an unordered list you must compare the target word to each list word in turn This is called a linear search If the search is futile that is the word is not on the list you will end up performing n comparisons Assume that the amount of time it takes to do a comparison is a constant You don t need to know what the constant is in fact it really doesn t matter what the constant is What is important is that the total amount of work you will perform is proportional to 71 That is to say if you were to search a list of 2000 words it would take twice as long as it would to search a list of 1000 words Now suppose the search is successful that is the word is found on the list We have no idea where it might be found so on average we would expect to search half the list So the expectation is still that you will have to perform about 712 comparisons Again this value is proportional to the length of the list 7 if you double the length of the list you would expect to do twice as much work What about searching an ordered list Searching a dictionary or a phonebook can be informally described as follows you divide the list in half after each comparison That is after you compare to the middle word you toss away either the first half or the last half of the list and continue searching the remaining and so on each step In an earlier chapter Chapter 4 Measuring Execution Time 1 you learned that this is termed a binary search If you have been doing the worksheets you have seen binary search already in worksheet 5 Binary search is similar to the way you guess a number if somebody says I m thinking of a value between 0 and 100 Can you nd my number To determine the speed of this algorithm we have to ask how many times can you divide a collection of n elements in half To nd out you need to remember some basic facts about two functions the exponential and the logarithm The exponential is the function you get by repeated multiplication In computer science we almost always use powers of two and so the exponential sequence is 1 2 4 8 16 32 64 128 256 512 1024 and so on The logarithm is the inverse of the exponential It is the number that a base generally 2 must be raised to in order to find a value If we want the log base 2 of 1000 for example we know that it must be between 9 and 10 This is because 29 is 512 and 210 is 1024 Since 1000 is between these two values the log of 1000 must be between 9 and 10 The log is a very slow growing function The log of one million is less than 20 and the log of one billion is less than 30 It is the log that provides the Logan39thms answer to our question Suppose I I I I you start with 1000 words After To the mathemat1c1an a logarithm 1s env1s1oned one comparison you have 500 as the inverse of the exponential function or as a after the second you have 250 solution to an integral equation However to a after the third 125 then 63 then computer scientist the log is something very 32 then 16 8 4 i and n lly 1 different The log base 2 ofa value n is approximately equal to the number of times that n can be split in half The word approximately is used because the log function yields a fractional value and the exact figure can be as much as one larger than the integer ceiling of the log But integer differences are normally ignored when discussing asymptotic bounds Logs occur in a great many situations as the result of dividing a value repeatedly in half Compare this to the earlier exponential sequence The values are listed in reverse order but can never be larger than the corresponding value in the exponential series The log function is an approximation to the number of times that a group can be divided We say approximation because the log function returns a fractional value and we want an integer But the integer we seek is never larger than 1 plus the ceiling that is next larger integer of the log Performing a binary search of an ordered list containing n words you will examine approximately log n words You don t need to know the exact amount of time it takes to perform a single comparison as it doesn t really matter Represent this by some unknown quantity 0 so that the time it takes to search a list of n words is represented by c log n This analysis tells us is the amount of time you expect to spend searching if for example you double the size of the list If you next search an ordered collection of 2n words you would expect the search to require c log 2n steps But this is c log 2 log n The log 2 isjust 1 and so this is nothing more than c c log n or c 1 log n Intuitively what this is saying is that if you double the size of the list you will expect to perform just one more comparison This is considerably better than in the unordered list Chapter 4 Measuring Execution Time 2 where if you doubled the size of the list you doubled the number of comparisons that you would expect to perform Big Oh notation There is a standard notation that is used to simplify the comparison between two or more algorithms We say that a linear search is a On algorithm read bigOh of n while a binary search is a Olog n algorithm bigOh of log n The idea captured by bigOh notation is like the concept of the derivative in calculus It represents the rate of growth of the execution time as the number of elements increases or 3time versus 6size Saying that an algorithm is On means that the execution time is bounded by some constant times n Write this as cn If the size of the collection doubles then the execution time is c2n But this is 2cn and so you expect that the execution time will double as well On the other hand if a search algorithm is Olog n and you double the size ofthe collection you go from clog n to clog 2n which is simply c clog n This means that Olog n algorithms are much faster than On algorithms and this difference only increases as the value of n increases A task that requires the same amount of time regardless of the input size is described as 01 or constant time A task that is On is termed a linear time task One that is Olog n is called logarithmic Other terms that are used include quadratic for Onz tasks and cubic for On3 algorithms What a bigoh characterization of an algorithm does is to abstract away unimportant distinctions caused by factors such as different machines or different compilers Instead it goes to the heart of the key differences between algorithms The discovery of a bigoh characterization of an algorithm is an important aspect of algorithmic analysis Due to the connection to calculus and the fact that the bigoh characterization becomes more relevant as n grows larger this is also often termed asymptotic analysis We will use the two terms interchangeably throughout this text In worksheet 8 you will investigate the bigOh characterization of several simple algorithms Summing Execution Times If you have ever sat in a car on a rainy day you might have noticed that small drops of rain can remain in place on the windscreen but as a drop gets larger it will eventually fall To see why think of the forces acting on the drop The force holding the drop in place is surface tension The force making it fall is gravity If we imagine the drop as a perfect sphere the surface tension is proportional to the square of the radius while the force of gravity is proportional to the volume which grows as the cube of the radius What you observe is that no matter what constants are placed in front of these two Chapter 4 Measuring Execution Time 3 values a cubic function c r3 ie gravity will eventually grow larger than a quadratic function d r ie surface tension The same idea is used in algorithmic analysis We say that one function dominates another if as the input gets larger the second will always be larger than the first regardless of any void makeldemity int mNND constants involved To see how this relates to for int i 0 i lt N i algorithms consider the function to initialize an for int j 0 j lt N 14 identity matrix If you apply the techniques from m m 0 the worksheets it is clear the first part is for int i 0 i lt N i performing Onz work while the second is On mm 1 So you might think that the algorithm is On2n But instead the rule is that when summing big Oh values you throw away everything except the dominating function Since n2 dominates n the algorithm is said to be Onz What functions dominate each common name other The table below lists functions in order from most gt costly to least The middle column is the common name for 317 years the function The third column can be used to illustrate why the 3 L6 dominating rule makes sense 1 2 Assume that an input is size 105 6 01 and you can perform 10 operations per second The third column shows the approximate time it would take to perform a task if the algorithm is of the given complexity So imagine that we had an algorithm had one part that was Onz and another that was On The Onz part would be taking about 28 hours while the On part would contribute about 01 seconds The smaller value gets overwhelmed by l I I I I Rootn 3 2 l l Constant the larger 8 In worksheet 9 you Will explore several lmear variations on the idea of dom1nat1ng functions 6 Each of the functions commonly found as 4 execution times has a characteristic shape when plotted as a graph Some of these are shown at right With experience you 2 should be able to look at a plot and recognize the type of curve it represents II I I I I Chapter 4 Measuring Execution Time 4 The Limits of bigOh The formal de nition of bigOh states that if fn is a function that represents the actual execution time of an algorithm the algorithm is Ogn if for all values n larger than a fixed constant no there exists a constant c such that fn is always bounded by that is smaller than or equal to the quantity c gn Although this formal definition may be of critical importance to theoreticians an intuitive felling for algorithm execution is of more practical importance The bigoh characterization of algorithms is designed to measure the behavior as inputs become ever larger They may not be useful when n is small In fact for small values of n it may be that an Onz algorithm for example is faster than an On log n algorithm because the constants involve mask the asymptotic behavior A real life example of this is matrix multiplication There are algorithms for matrix multiplication that are known to be faster than the naive On3 algorithm shown in worksheet 8 However these algorithms are much more complicated and since the value n representing the number of rows or columns in a matrix seldom gets very large the classic algorithm is in practice faster Another limitation of a bigoh characterization is that it does not consider memory usage There are algorithms that are theoretically fast but use an excessively large amount of memory In situations such as this a slower algorithm that uses less memory may be preferable in practice Using BigOh to Estimate Wall Clock Time A bigOh description of an algorithm is a characterization of the change in execution time as the input size changes If you have actual execution timings wall clock time for an algorithm with one input size you can use the bigOh to estimate the execution time for a different input size The fundamental equation says that the ratio of the big Oh s is equal to the ratio of the execution times If an algorithm is Ofn and you know that on input n1 it takes time t1 and you want to find the time t it will take to process an input of size n2 you create the equation fn1 fn2 I1 Iz To illustrate suppose you want to actually perform the mind experiment given at the beginning of this chapter You ask a friend to search for the phone number for Chris Smit in 8 pages ofa phone book Your friend does this in 10 seconds From this you can estimate how long it would take to search a 256 page phone book Remembering that binary search is Olog n you set up the following equation log8log256 which is 38 10 X Solving for X gives you the answer that your friend should be able to find the number in about 24 seconds Now you time your friend perform a search for the name attached to a Chapter 4 Measuring Execution Time 5 given number in the same 8 pages This time your friend takes 2 minutes Recalling that a linear search is On this tells you that to search a 256 page phone could would require 82562X Solving for X tells you that your friend would need about 64 minutes or about an hour So a binary search is really faster than a linear search In Worksheet 10 you will use this equation to estimate various different execution times Recursive Functions and Recurrence Relations The analysis of recursive functions is slightly more complicated than the analysis of algorithms with loops A useful technique is to describe the execution time using a recurrence relation To illustrate consider a function to print a positive integer value in binary format Here n will represent the number of binary digits in the printed form Because the argument is divided by 2 prior to the recursive call it will have one fewer digit Everything else outside of the recursive call can be performed in constant time The base case can Vold prmthary mt V also be performed in constant time Ifwe let Tn If V O H V 1 represent the time necessary to print an ndigit Prlntm number we have the following equation else printBinaryv2 Tn Tn 1 c PrintV2 T1 c Read this as asserting that the time for n is equal to the time for nl plus some unknown constant value Whenever you see this relation you can say that the running time of the recursive function is On To see why remember that On means that the actual running time is some constant times n plus other constant values Let us write this as c1n c2 To verify that this is the solution to the equation substitute for both sides and show that the results are equal if the constants are in the correct relation Tn is c1n c2 We want this to be equal to c1n1 c c But the latter is c1n c c 7 c1 Hence the two sides are equal ifc is equal to c1 In general we can just merge all constants into one constant value The four most common recurrence relations and their solutions are shown at left Here we simply assert these solutions without proof However it is not difficult to check that the solutions are reasonable For example to verify the second you can observe the following c1logncc1logn2cc1logn71cc1lognc Chapter 4 Measuring Execution Time 6 In worksheet 11 you will use these forms to estimate the running time of various recursive algorithms An analysis exercise at the end of this chapter asks you to verify the solution of each of these equations Best and Worst Case Execution Time The bubble sort and selection sort algorithms require the same amount of time to execute regardless of the input However for many algorithms the execution time will depend upon the input values often dramatically so In these situations it is useful to understand the best situation termed the best case time and the worst possibility termed the worst case time We can illustrate this type of analysis with yet another sorting algorithm This algorithm is termed insertion sort If you have been doing the worksheets you will remember this from worksheet 7 The insertion sort algorithm is most easily described by considering a point in the middle of execution already sorted Yet to be considered lzl3l4l7l9slllgl lol Let p represent an index position in the middle of an a1ray At this point the elements to the left of p those with index values smaller than p have already been sorted Those to the right of p are completely unknown The immediate task is simply to place the one element that is found at location p so that it too will be part of the sorted portion To do this the value at location p is compared to its neighbor If it is smaller it is swapped with its neighbor It is then compared with the next element possibly swapped and so on l234759391860l This process continues until one of two conditions occur Either a value is found that is smaller and so the ordering is established or the value is swapped clear to the start of the array 2 3 4 579 1 8 6 0 l 2 3 4 539 l9 l8 l6 W Chapter 4 Measuring Execution Time 7 Since we are using a while loop the analysis of execution time is not as easy as it was for selection sort Question What type of value will make your loop execute the fewest number of iterations What type of value will make your loop execute the largest number of times If there are n elements to the left of p how many times will the loop iterate in the worst case Based on your observations can you say what type of input will make the insertion sort algorithm run most quickly Can you characterize the running time as bigOh What type of input will make the insertion sort algorithm run most slowly Can you characterize the running time as bigOh We describe this difference in execution times by saying that one value represents the best case execution time while the other represents the worst case time In practice we are also interested in a third possibility the average case time But averages can be tricky 7 not only can the mathematics be complex but the meaning is also unclear Does average mean a random collection of input values Or does it mean analyzing the sorting time for all permutations of an array and computing their mean Most often one is interested in a bound on execution time so when no further information is provided you should expect that a bigOh represents the worst case execution time Shell Sort In 1959 a computer scientist named Donald Shell argued that any algorithm that sorted by exchanging values with a neighbor must be 0n2 The argument is as follows Imagine the input is sorted exactly backwards The rst value must travel all the way to the very end which will requires n steps Mil Ill The next value must travel almost as far taking nl steps And so on through all the values The resulting summation is l 2 n which we have seen earlier results in 0n2 behavior To avoid this inevitable limit elements must jump more than one location in the search for their final destination Shell proposed a simple modification too insertion sort to accomplish this The outermost loop in the insertion sort procedure would be surrounded by yet another loop called the gap loop Rather than moving elements one by one the outer loop would in effect perform an insertion sort every gap values Thus elements could jump gap steps rather than just a single step For example assume that we are sorting the following array of ten elements Chapter 4 Measuring Execution Time 8 8171915121416111013l Imagine that we are sorting using a gap of 3 We rst sort the elements with index positions 0 3 6and 9 placing them into order 3171915 ZIMBMOW Next we order the elements with index positions 1 4 and 7 3111915121416 710W Finally values with index positions 2 5 and 8 are placed in order Mm l3l1l0l5l2l4l6l7l9l8l Next we reduce the gap to 2 Now elements can jump two positions before nding their nal location First sort the elements with odd numbered index positions l o 6 12534 719W Next do the same with elements in even numbered index positions lol1lz 4 31516171918l The nal step is to sort with a gap of 1 This is the same as our original insertion sort However remember that insertion sort was very fast if elements were roughly in the correct place Note that only two elements are now out of place and they each move only one position Chapter 4 Measuring Execution Time 9 WW 0123456789 end 1 shell n 4 n8 l 39 dlfferent sequences Hovvever dlvldmg tlne gap m halfhas tlne advantage ofbelng extremely easy to program algontlnm see questrons attlne enol othe elnapter Remember tlns ls slmply an lnsemon sort vvrtln tlne adjacent elementberng tlne value gap elements avvay n H r A L result of one expenment sortang ranolom data values ofvarlous slzes Tlm2ms 2700 lnsemon 39 Shell mam Merge Son Whlle easy to are om vvorst ease Many somng algontlnms ean do better In tlns lesson we wlll explore one ofthese Chapter 4 Measunng Bltecuuon Tlme 10 As with many algorithms the intuition for merge sort is best understood if you start in the middle and only after having seen the general situation do you examine the start and nish as special cases For merge sort the key insight is that two already sorted arrays can be very rapidly merged together to form a new collection All that is necessary is to walk down each of the original lists in order selecting the smallest element in turn Divide and Conquer The general idea of dividing a problem into two roughly equal problems of the same form is known as the divide and conquer heuristic We have earlier shown that the number of time a collection of size n can be repeatedly split in halfis log n Since log n is a very small value this leads to many ef cient algorithms We will see a few of these in later lessons I5I9I10l12178112032H1I lS IQI101217I8112032H1I5 4591o121713112o32l158 ISI39Q I1OI1ZI17H1 I8I112032H1I5I8I9l IS39I39Q39I tel12l17II1I398I11I2032 158I910 I I I I39Q39I l39el12l178391 t2032 1 5 3 91011 a5e3e1217e 2o32 1 5 8 9101112 lslelrehzl l 181r2032 1 s 8 9 l10l11l1217 59 e2 erl2632 1 5 8 I 9101112I1720U 59 e12 1 1 e12632H1 5 8 9 1o1112172o32 When you reach the end of one of the arrays you cannot in general predict which list will end rst you must copy the remainder of the elements from the other Based on this description you should now be able to complete the implementation of the merge method This you will do in worksheet 12 Let n represent the length of the result At each step of the loop one new value is being added to the result Hence the merge algorithm is On Chapter 4 Measuring Execution Time A Recursive Sorting Algorithm So how do you take the observation that it is possible to quickly merge two ordered arrays and from this produce a fast sorting algorithm The key is to think recursively Imagine sorting as a threestep process In the rst step an unordered array of length n is will have one more element than Combine to form the original i i i characteristic of all recursive broken into two unordered arrays each containing approximately half the elements of the original Approximately because ifthe size ofthe original is odd one of the two Break the other Next each of these smaller lists is sorted by means I sort ecuriwely I of a recursive call Finally the two sorted lists are merged back Notice a key feature here that is algorithms We have solved a problem by assuming the ability to solve a smaller problem of the same form The meaning of smaller will vary from task to task Here smaller means a smaller length array The algorithm demonstrates how to sort an array of length n assuming you know how to sort an array actually two arrays of length n2 A function that calls itself must eventually reach a point where things are handled in a different fashion without a recursive call Otherwise you have an infinite cycle The case that is handled separately from the general recursive situation is called the base case For the task of sorting the base case occurs when you have a list of either no elements at all or just one element Such a list is by definition already sorted and so no action needs to be performed to place the elements in sequence With this background you are ready to write the mergeSort algorithm The only actions are to separate the array into two parts recursively sort them and merge the results If the length of the input array is sufficiently small the algorithm returns immediately However the merge operation cannot be performed in place Therefore the merge sort algorithm requires a second temporary array the same size as the original The merge operation copies values into this array then copies the array back into the original location We can isolate the creation of this array inside the mergeSort algorithm which simply invokes a second internal algorithm for the actual sorting The internal algorithm takes as arguments the lowest and highest index positions void mergeSort double data int n double temp double malloc n sizeofdoube assert temp O I make sure allocation worked mergeSortlnternal data 0 n1 temp free temp Chapter 4 Measuring Execution Time 12 void mergeSortlhterhal double data int low int high double temp int i mid if low gt high return base case mid low high 2 mergeSortlhterhadata low mid temp first recursive ca mergeSortIhterhadata mid1 high temp second recursive ca mergedata low mid high temp merge into temp for i low i lt high i copy merged values back datai tem pi All that remains is to write the function merge which you will do in Worksheet 12 Algorithmic Analysis of Merge Sort Recall that the analysis of recursive algorithms involves de ning the execution time as a recurrence relation Merge sort is breaking an array of size n into two smaller arrays and then sorting the smaller arrays So the equation is roughly TN 2 TN 2 c1n c You will remember that the solution to this relation is approximately n log n Another way to think about this is the recursive calls on merge sort will be approximately Olog n levels deep and at each level it will be doing approximately On operations n elements wide An On log n algorithm is a vast improvement over an Onz one To illustrate you can try executing the merge sort algorithm on arrays of various sizes and comparing the execution times to that of selection sort The following table shows some of the values in milliseconds that you would typically discover lsize 5000 I6000 7000 I8000 9000 10000 selection sort I 104 165 230 317 402 500 Imerge sort 11 12 15 15 19 21 Chapter 4 Measuring Execution Time 13 Is it possible to do better The answer is yes and no It is possible to show although we will not do so here that any algorithm that depends upon a comparison of elements must have at least an On log n worst case In that sense merge sort is about as good as we can expect On the other hand merge sort does have one annoying feature which is that it uses extra memory It is possible to discover algorithms that while not asymptotically faster than merge sort do not have this disadvantage We will examine one of these in the next section Quick Sort In this section we introduce quick sort Quick sort as the name suggests is another fast sorting algorithm Quick sort is recursive which will give us the opportunity to once again use the recursive analysis techniques introduced earlier in this chapter Quick sort has differing best and worst case execution times similar in this regard to insertion sort Finally quick sort presents an unusual contrast to the merge sort algorithm The quick sort algorithm is in one sense similar to and in another sense very different from the merge sort algorithm Both work by breaking an array into two parts recursively sorting the two pieces and putting them back together to form the final result Earlier we labeled this idea divide and conquer way that the array is broken Where they differ is in the into pieces and hence the Break way that they are put back together Merge sort devotes Sort ecuriively I very little effort to the breaking apart phase simply Combine selecting the first half ofthe array for the first list and the second half for the second This means that relatively little can be said about the two subarrays and significant work must be performed to merge them back together Quick sort on the other hand spends more time on the task of breaking apart Quick sort selects one element which is called the pivot It then divides the array into two sections with the following property every element in the first half is smaller than or equal to the pivot value while every Chapter 4 Measuring Execution Time 14 element in the second half is larger than or equal to the pivot Notice that this property does not guarantee sorting Each of the smaller arrays must then be sorted by recursively calling quick sort But once sorted this property makes putting the two sections back together much easier No merge is necessary since we know that elements in the first part of the array must all occur before the elements in the second part of the array Because the two sections do not have to be moved after the recursive call the sorting can be performed inplace That is there is no need for any additional array as there is when using the merge sort algorithm As with the merge sort algorithm it is convenient to have the main function simply invoke an interior function that uses explicit limits for the upper and lower index ofthe area to be sorted void quickSort double storage int n quickSortlnternal storage 0 n1 void quickSortlnternal double storage int low int high if low gt high return base case int pivot low high2 one of manytechniques pivot partitionstorage low high pivot quickSortlnternal storage low pivot1 first recursive call quickSortlnternal storage pivot1 high second recursive call There is however a danger in this N process In merge sort it was easy to guarantee that the two halves were roughly equal size yielding N39l a fast On log n process In quick sort this is much more difficult to guarantee If we are unlucky then m N2 in the worst case one partition contains no values and the other is just one element smaller This 2 D 1 N N12 which is 0n2 not good leads 0 Poor 00 Pedomance Following the discussion of the partition algorithm we will describe some of the techniques that are used to try and avoid this bad behavior Partitioning The process of dividing a portion of an array into two sections is termed partitioning The limits of the partition are described by a pair of values low and high The first represents the lowest index in the section of interest and the second the highest index In addition there is a third element that is selected termed the pivot The first step is to swap the element at the pivot location and the first position This moves the pivot value out of way of the partition step The variable i is set to the next position and the variable j to high The heart of the partition algorithm is a while loop The invariant that is going to be preserved is that all the elements with index values smaller than i are themselves smaller than or equal to the pivot while all the elements with index values larger than j are Chapter 4 Measuring Execution Time 15 themselves larger than the pivot At each step of the loop the value at the i position is compared to the pivot If it is smaller or equal the invariant is preserved and the i position can be advanced Pivot lt Pivot Unknown gt Pivot I J Otherwise the location of the j position is compared to the pivot If it is larger then the invariant is also preserved and the j position is decremented If neither of these two conditions is true the values at the i and j positions can be swapped since they are both out of order Swapping restores our invariant condition The loop proceeds until the values of i and j meet and pass each other When this happens we know that all the elements with index values less than i are less than or equal to the pivot This will be the first section All those elements with index values larger than or equal to i are larger than or equal to the pivot This will be the second section The pivot is swapped back to the top of the first section and the location of the pivot is returned lt Pivot iPivoti gt Pivot i The execution time of quicksort depends upon selecting a good pivot value Many heuristics have been proposed for this task These include 39 Selecting the middle element as we have done 39 Selecting the first element This avoids the initial swap but leads to 0n2 performance in the common case where the input is already sorted 39 Selecting a value at random Selecting the median of three randomly chosen values From the preceding description you should be able to complete the partition algorithm and so complete the quick sort algorithm You will do this in worksheet 13 Study Questions 1 What is a linear search and how is it different from a binary search 2 Can a linear search be performed on an unordered list Can a binary search Chapter 4 Measuring Execution Time 16 V39 9 E 4 V39 0 gt1 9 gt0 If you start out with n items and repeatedly divide the collection in half how many steps will you need before you have just a single element Suppose an algorithm is On where n is the input size If the size of the input is doubled how will the execution time change Suppose an algorithm is Olog n where n is the input size If the size of the input is doubled how will the execution time change Suppose an algorithm is Onz where n is the input size If the size of the input is doubled how will the execution time change What does it mean to say that one function dominates another when discussing algorithmic execution times Explain in your own words why any sorting algorithm that only exchanges values with a neighbor must be in the worst case Onz Explain in your own words how the shell sort algorithm gets around this limitation Give an informal description in English of how the merge sort algorithm works What is the biggest advantage of merge sort over selection sort or insertion sort What is the biggest disadvantage of merge sort In your own words given an informal explanation of the process of forming a partition Using the process of forming a partition described in the previous question give an informal description of the quick sort algorithm Why is the pivot swapped to the start of the array Why not just leave it where it is Give an example where this would lead to trouble In what ways is quick sort similar to merge sort In what ways are they different What does the quick sort algorithm do if all elements in an array are equal What is the bigOh execution time in this case Chapter 4 Measuring Execution Time 17 Suppose you selected the first element in the section being sorted as the pivot What advantage would this have What input would make this a very bad idea What would be the bigOh complexity of the quick sort algorithm in this case 18 Compare the partition median finding algorithm to binary search In what ways are they similar In what ways are they different Exercises 1 Suppose a algorithm takes 5 second to handle an input of 1000 elements Fill in the following table with the approximate execution times assuming that the algorithm has the given bigOh execution time 2 Suppose you have an n2 algorithm that for n 80 runs slightly longer than one hour One day you discover an alternative algorithm that runs in time n log n If you assume the constants of proportionality are about the same about how long would you expect the new program to run 3 Can you write the insertion portion of the insertion sort algorithm as a recursive routine Rewrite the insertion sort function to use this new routine 4 There is one previous algorithm you examined that also had different best and worst case execution times What can you say about the execution times for the function isPrime int isPrime int n for int i 2 i i lt n i if 0 z n i return 0 false I return 1 true I 5 Analysis Exercises 1 The interface file named timeh provides access to a millisecond timer as well as a number of userful symbolic constants You can use these to determine how long some actions takes as follows Chapter 4 Measuring Execution Time include lttimehgt double getMilliseconds return 10000 clock CLOCKSPERSEC int main double elapsed elapsed getMilliseconds perform a task elapsed getMilliseconds elapsed printf Elapsed milliseconds gn elapsed Using this idea write a program that will determine the execution time for selectionSort for inputs of various sizes Sort arrays of size n where n ranges from 1000 to 5000 in increments of 500 Initialize the arrays with random values Print a table of the input sizes and execution times Then plot the resulting values Does the shape of the curve look like what you would expect from an n2 algorithm 2 Recall the function given in the previous chapter that you proved computed aquot You can show that this function takes logarithmic number of steps as a function of n This may not be obvious since in some steps it only reduces the exponent by subtracting one First show that the function takes a logarithmic double exp double 8 int n number of steps ifn is a power ofn Do you see if n 2 return 1 0 why Next argue that every even number works by if n 1 return a cutting the argument in half and so should have this if 0 02 return eXPa39ay 02 logarithmic performance Finally argue that every else return a 39 eXPay 0391 odd number will subtract one and become an even number and so the number of times the function is called with an odd number can be no larger than the number of times it is called with an even number 3 A sorting algorithm is said to be stable if the relative positions of two equal elements are the same in the final result as in the original vector Is insertion sort stable Either give an argument showing that it is or give an example showing that it is not 4 Once you have written the merge algorithm for merge sort provide invariants for your code and from these produce a proof of correctness 5 Is merge sort stable Explain why or why not 6 Assuming your have proved the partition algorithm correct provide a proof of correctness for the quick sort algorithm Chapter 4 Measuring Execution Time 19 7 Is quick sort stable Programming Projects N E 4 Experimentally evaluate the running time of Shell Sort versus Insertion sort and Selection Sort Are your results similar to those reported here Experimentally evaluate the running time of Merge sort to that of shell sort and insertion sort Rewrite the quick sort algorithm to select a random element in the section being sorted as the pivot Empirically compare the execution time of the middle element as pivot version of quick sort to this new version Are there any differences in execution speed Experimentally compare the execution time of the partition median nding algorithm to the naive technique of sorting the input and selecting the middle element Which one is usually faster On the Web Wikipedia has an excellent discussion of bigOh notation and its variations The Dictionary of Algorithms and Data Structures provided by the National Institute of Standards and Technology httpwwwnistgovdads has entries on binary and linear search as well as most other standard algorithms The standard C library includes a version of quick sort termed qsort However the interface is clumsy and difficult to use Chapter 4 Measuring Execution Time 20

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.