Homework answers / question archive / Homework 6: Show the steps of the first partition of QuickSort on the list [10,6,7,2,4,3]

Homework 6: Show the steps of the first partition of QuickSort on the list [10,6,7,2,4,3]

Computer Science

Share With

---

Homework 6:

1. Show the steps of the first partition of QuickSort on the list [10,6,7,2,4,3]. Use the final [10 pts] index as the initial pivot index.

Solution:

2. Consider the theoretical case where the resultingpivotindex consistently ends up 1/2 of the way through the list and the theoretical case where the resultingpivotindex consistently ends up 1/4 of the way through the list. Essentially the corresponding recurrence relations would be something like:

T_1/2(n) = T (bn/2c) + T (bn/2c) + Θ(n)

T_1/4(n) = T (bn/4c]) + T (b3n/4c) + Θ(n)

Suppose in addition that:

• • • The Θ(n) term is actually 5n + 2.
    • You know that T(0) = 0 and T(1) = 2.
  • Find each time complexity for values n = 0,10,20,...,100. (You are welcome to do this [5 pts] in recursive code and if you do, include your code. It’s not hard - each is six simple lines of Python, for example.) Solution:
  • Plot the corresponding data.            [5 pts]

Solution:

2. 3. Which of these does your data suggest has a better Θ time complexity? Explain. [5 pts] Solution:
3. Give a specific example which illustrates the fact that QuickSort is not stable. Illustrate where [10 pts] in the process the stability breaks down. You don’t need to show the entire implementation, just enough to justify.

Solution:

4. Suppose a list has n = 2^k − 1 elements for some k and suppose that somehow, magically, the index of the median is chosen at every stage for the initial pivot index. In this case we can explicitly calculate the number of calls to quicksort, the length of each list it is called on, and the number of subsequent calls to partition. Remember that quicksort only calls partition in the case lso when l==r (list of length 1) quicksort exits.

Consider the case where n = 2⁴− 1 = 15. Observe there will be:

• • • 1 initial call to quicksort with a list of length 15, resulting in 1 call to partition and then ...
    • a total of 2 calls to quicksort with lists of length 7, resulting in a total of 2 calls to partition and then ...
    • a total of 4 calls to quicksort with lists of length ???, resulting in a total of ??? calls to partition and then ...
    • and so on, until it ends.
  • Complete the counting argument above - finish the third bullet point and then the re- [5 pts] maining bullet points until the argument ends. There should be only four bullet points total.

Solution:

1. 2. What would the counting argument be for n = 2^k−1 for an arbitrary k? It’s not terribly [10 pts] hard, just generalize the pattern in ( a ).

Solution:

1. 3. Suppose that each call to partition on a list of length i takes time c₁i. Ignoring all [10 pts] other time requirements (the call to partition is the important one) write down and evaluate the sum which gives the total time requirement of the algorithm. Does the time complexity of this result correspond to the best-case analysis?

Solution:

5. As discussed for QuickSort, ideally we would use a pivot value at or close to the median. A reasonable substitute would be to use a pivot value close to the mean. Let’s do this and integrate it into QuickSort. For all of what follows you are only allowed O(1) auxiliary space.
   1. Write the pseudocode for an algorithm mean(A) which returns the mean in Θ(n) time. [5 pts] Solution:
   2. Write the pseudocode for an algorithm closest(A) which returns the index of the value [5 pts] in A closest to the mean in Θ(n) time. If there are several such indices, return the smallest index. You can call mean(A) from here.

Solution:

1. 3. Modify the QuickSort pseudocode to use this index for pivot selection. [5 pts]

Solution:

6. Consider the following modification of BubbleSort: [12 pts]

for i = 0 to n−1 for j = n−2 down to i i f A[ j ] < A[ j +1] nothing

else

A[ j ] <−> A[ j +1] end

end

end

Write down the decision tree for this algorithm as applied to the set {X,Y,Z}.

Solution:

7. Consider the following pseudocode for InsertSort: [13 pts]

for i = 0 to n−1 key = A[ i ]

j = i−1

while j >= 0 and key < A[ j ] A[ j +1] = A[ j ] j = j − 1

end

A[ j +1] = key

end

Write down the decision tree for this algorithm as applied to the set {X,Y,Z}.

Solution: