Quiz 4: October 1, 2004

1. Suppose A is the array given below
   

   8 2 1 4 11 7 17
   

   Also suppose that the function partition is called as follows:

   partition(A, 0, 6)
   

   1. What value does partition return?

      Answer: 4

   2. Draw the array A after the execution of partition.

      Answer: 2 1 4 7 8 11 17

   If you need to look at the code for partition, here it is:

           public static int partition(int[] data, int left, int right)
           {
                   int i, j;
                                                                                   
                   i = left;
                   for(j = left; j <= right; j++)
                   {
                           if(data[j] < data[i])
                           {
                                   swap(data, i, j);
                                   i++;
                                   swap(data, i, j);
                           }
                   }
                                                                                   
                   return i;
                                                                                   
           }
   

2. Here is my code for recursiveQuickSort.

           public static void recursiveQuickSort(int[] data, int left, int right)
           {
                   if (left < right)
                   {
                           int p = partition(data, left, right);
                           recursiveQuickSort(data, left, p-1);
                           recursiveQuickSort(data, p+1, right);
                   }
           }
   

   This code is slightly different from what I presented in class. In the above code, the element data[p] is not being included in either of the two recursive calls. My claim is that this code works fine, but if we replaced the p+1 by p in the second recursive call, our code would be incorrect. Specifically, we would have code that could recurse infinitely. Explain why this is so, in 1-2 sentences.

   Answer: Consider an array data in which the first element is the smallest element. For such an array, partition(data, left, right) returns the value left and does not change the positions of any elements in data. Thus the first call to recursiveQuickSort would send in an "empty" array, whereas the second call to recursiveQuickSort would be recursiveQuickSort(data, left, right), the same as the original call - implying that this recursion would go on forever.