Analysis of Algorithms : An Active Learning Approach

3.6 MERGE SORT 83 3.5.3 Given the list of elements, [23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4], what would be their order after ...

84 SORTING ALGORITHMS last the index of the last element in the part of list to sort if first < last then middle = ( first + ...

3.6 MERGE SORT 85 finalEnd = end2 indexC = 1 while (start1 ≤ end1) and (start2 ≤ end2) do if list[start1] < list[start2] then ...

86 SORTING ALGORITHMS NA is the number of elements in list A. Notice that if all of the elements of list B are smaller than the ...

3.6 MERGE SORT 87 zero. Because middle is calculated to be exactly between first and last, we see that we are breaking the list ...

88 SORTING ALGORITHMS five N terms, the sum of the powers of 2 from 0 (1 = 2^0 ) through 4 (16 = 2^4 ) and W(N / 32) = W(N / 2^5 ...

3.7 QUICKSORT 89 3.7 Quicksort Quicksort is another recursive sorting algorithm. It picks an element from the list and uses it t ...

90 SORTING ALGORITHMS Splitting the List There are at least two versions of the PivotList function. The first is easy to program ...

3.7 QUICKSORT 91 PivotPoint = PivotPoint + 1 Swap( list[ PivotPoint ], list[ index ] ) end if end for // move pivot value into c ...

92 SORTING ALGORITHMS So, how does quicksort do in removing inversions? Consider a list of N ele- ments that the PivotList algor ...

3.7 QUICKSORT 93 This is a very complicated form of recurrence relation because it depends on not just one smaller value of A, b ...

94 SORTING ALGORITHMS 3.7.3 Trace the operation of Quicksort on the list [23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4]. Show the l ...

3.8 EXTERNAL POLYPHASE MERGE SORT 95 PivotValue = list[ first ] lower = first upper = last+1 do do upper = upper - 1 until list[ ...

96 SORTING ALGORITHMS It is also possible to be able to declare an array large enough to hold all of the data but that the logic ...

3.8 EXTERNAL POLYPHASE MERGE SORT 97 sorted list between file A and file B. An algorithm to accomplish this first step would be ...

98 SORTING ALGORITHMS PolyphaseMerge( S ) S is the size of the initial runs Size = S Input1 = A Input2 = B CurrentOutput = C whi ...

3.8 EXTERNAL POLYPHASE MERGE SORT 99 ■ 3.8.1 Number of Comparisons in Run Construction Because the algorithm used for the run co ...

100 SORTING ALGORITHMS because the above summation begins at 1, where the summation in Equation 1.18 begins at 0. The run merge ...

3.9 ADDITIONAL EXERCISES 101 The process is repeated for a list one element smaller that doesn’t include the element just put in ...

102 SORTING ALGORITHMS c. Shellsort d. Radix sort e. Heapsort f. Merge sort g. Quicksort 3.10 Programming Exercises You can test ...