Analysis of Algorithms : An Active Learning Approach

3.2 BUBBLE SORT 63 correct position to insert this new element. You should notice that for unique keys the standard binary searc ...

64 SORTING ALGORITHMS while swappedElements do numberOfPairs = numberOfPairs - 1 swappedElements = false for i = 1 to numberOfPa ...

3.2 BUBBLE SORT 65 to execute the for loop N
1 times. This indicates that an input data set that is in the reverse order does l ...

66 SORTING ALGORITHMS where, again, C(i) is the number of comparisons done in the first i passes of the for loop before we stop. ...

3.2 BUBBLE SORT 67 3.2.4 Show the results of each pass of BubbleSort applied to the list [7, 3, 9, 4, 2, 5, 6, 1, 8]. Show the ...

68 SORTING ALGORITHMS b. Write a short paragraph that explains exactly why this third version of bubble sort will work. c. Does ...

3.3 SHELLSORT 69 passes = lg N while (passes ≥ 1) do increment = 2passes - 1 for start = 1 to increment do InsertionSort ...

70 SORTING ALGORITHMS have. If our first sublist has the elements in locations 1 and 1 + increment, the last sublist has to star ...

3.3 SHELLSORT 71 list. Each swap of elements will remove one or more of these inversions. For example, when bubble sort does a c ...

72 SORTING ALGORITHMS If there are just two passes, it has been shown that using an increment of about for the first pass and 1 ...

3.4 RADIX SORT 73 can be removed by the exchange of two nonadjacent elements? Give an example for a list with 10 elements. 3.4 R ...

74 SORTING ALGORITHMS bucketNumber = (list[entry].key / shift) mod 10 Append( bucket[bucketNumber], list[entry] ) end for entry ...

3.4 RADIX SORT 75 ■FIGURE 3.2 The three passes of a radix sort Original list (a) Pass 1, Units Digit Pass 1 list (b) Pass 2, Ten ...

76 SORTING ALGORITHMS This is very efficient, and so you might wonder why any of the other sorting algorithms are even used. The ...

3.5 HEAPSORT 77 a. If the key is a number in the range of 0 to 2^64 , choose two options (one smaller and one larger) for the nu ...

78 SORTING ALGORITHMS of the list grows. We can, however, use the space for the list itself and do this sort without extra space ...

3.5 HEAPSORT 79 key the key value that needs to be reinserted in the heap bound the upper limit (index) on the heap vacant = roo ...

80 SORTING ALGORITHMS Final Algorithm Putting these pieces together, and adding the final details needed to move the elements fr ...

3.5 HEAPSORT 81 Using Equations 1.17 and 1.19, we get We now substitute D = lg N, giving So the heap construction phase is linea ...

82 SORTING ALGORITHMS Using Equation 1.19, we get Now, substituting lgN for d, we get Now, we have to add together the constru ...