Question

4-1- Let array locations A[0], ..., A[7] hold numbers A = {9,8,7,6,5,4,3,2}. Carry out by hand one call of the partition function of Quick Sort on the array A above. You must trace the actions of partition on this array carefully. After this single call to partition, answer the questions:

1. What is the initial index of the pivot element? What is its value?

2. Where does the pivot end up? (What is its index at the end?)

3. How many non-trivial interchanges are there? (Interchanges of two distinct elements.)

4. How many empty interchanges are there? (Interchanges of an element with itself.)

5. What value is returned by this call to partition?

6. What is the result after this single call to partition? Identify the left sub-array of the partition and the right sub-array of the partition.

7. Suppose we continue with the quicksort algorithm beyond this initial call to partition. Briefly describe with this specific example how the rest of the sorting goes, until the array is sorted

Answer 1

1. What is the initial index of the pivot element? What is its value?

answer: [Init pivot index: 7, Init pivot value: 2 ]

2. Where does the pivot end up? (What is its index at the end?)

answer:   [Pivot ends up in index 0, at the far left; there's nowhere else it could be.]

3. How many non-trivial interchanges are there? (Interchanges of two distinct elements.)

answer: [During execution, i is never incremented inside the loop, so there are no interchanges inside the loop.

At t he end there is a single non-trivial interchange of A[0] with A[7], putting 2 at the beginning

and 9 at the end.]

4. How many empty interchanges are there? (Interchanges of an element with itself.)

answer: [ 0, see above ]

5. What value is returned by this call to partition?

answer: [ returns the index of the final location of the pivot, namely 0 ]

6. What is the result after this single call to partition? Identify the left sub-array of the partition and the right  sub-array of the partition.

answer: [ left sub-array empty, pivot is in location A[0], and right sub-array is A[1] to A[7]: {8,7,6,5,4,3,9} ]

7. Suppose we continue with the quicksort algorithm beyond this initial call to partition.

Briefly describe with this specific example how the rest of the sorting goes, until the array

is sorted.

answer: [ Below, the underlined numbers are input to the next call to partition
{9,8,7,6,5,4,3,2} (1st call, moves 2 to beginning, 1 non-empty interchange)
   {2,8,7,6,5,4,3,9} (2nd call, drops 9 from consideration, empty interchanges)
{2,8,7,6,5,4,3,9} (3rd call, moves 3 to left, 1 non-empty interchange)
{2,3,7,6,5,4,8,9} (4th call, drops 8 from consideration, empty interchanges)
{2,3,7,6,5,4,8,9} (5th call, moves 4 to left, 1 non-empty interchange)
{2,3,4,6,5,7,8,9} (6th call, drops 7 from consideration, empty interchanges)
{2,3,4,5,6,7,8,9} (7th call, moves 5 to left, 1 non-empty interchange) ]