Question

1. Below is the pseudocode for Quicksort and Partition that we talked about in class. As usual with recursive functions on arrays, we see the array indices s and e as arguments. Quicksort(A, s, e) sorts the part of the array between s and e inclusively. The initial call (that is, to sort the entire array) is Quicksort(A, 0, n − 1)

QuickSort(A, s, e)

  if s < e

p = Partition (A, s, e) // Partition the array and return the position of pivot after the partition

  QuickSort(A, s, p-1)    // Sort left side

  QuickSort (A, p+1, e)    // Sort right side

  end if

Partition(A, s, e)

pivot = A[s], i = s + 1, j = e; // Let the leftmost element be the pivot

while i<=j // Rearrange elements

       while i < e & A[i] < pivot,

              i = i + 1

       end while

       while j > s & A[j] >= pivot,

              j = j - 1

       end while

       if i >= j

              break

       end if            

       swap A[i] nd A[j]

end while

swap A[s] nd A[j]

return j; // Return the index of pivot after the partition

1. Let A = {11, 7, 6, 48, 30, 12, 75}, and assume we call Quicksort(A, 0, 6). Show what happens during the first invocation of Partition. What is the value of p returned, and what are the two recursive calls made?

Note: Credit will not be given only for answers - show all your work:

steps you took to get your answer.

your answer.

2. In the given Partition function, we let the first element A[s] be the pivot. How do you modify Partition(A, s, e) so that it chooses the pivot as the median of three elements randomly selected from the array? pseudocode to change Partition.

Answer 1

(a) During the first partition, array is splitting to to two sub arrays.It is shown in follwoing figure

Value returned during first partition is

here, array is divided in to two sub array based on pivot.First array is{ 6,7}and second array is {48,30,12,75}. Pivot 11 is placed in exact position in sorted array. First recursive call partitions the first array as shown above Similary second recursive call partitions the second array.

(b) Function partition uses a function named find_from_median(A,s,e) for finding pivot element from median of 3 elements in the array

Partition(A, s, e)

pivot = find_from_median(A,s,e), i = s + 1, j = e; // Let the leftmost element be the pivot

while i<=j // Rearrange elements

       while i < e & A[i] < pivot,

              i = i + 1

       end while

       while j > s & A[j] >= pivot,

              j = j - 1

       end while

       if i >= j

              break

       end if            

       swap A[i] nd A[j]

end while

swap A[s] nd A[j]

return j; // Return the index of pivot after the partition

find_from_median(A,s,e)

k1=rand()

while(!(k1>=s & k1<=e))

k1=rand()

end while

k2=rand()

while(!(k2>=s & k2<=e))

k2=rand()

end while

k3=rand()

while(!(k3>=s & k3<=e))

k3=rand()

end while  

if ((A[k1] < A[k2] && A[k2] < A[k3]) || (A[k3] < A[k2] && A[k2] < A[k1]))

            return A[k2]  

        else if ((A[2] < A[1] && A[1] < A[3]) || (A[3] < A[1] && A[1] < A[2]))

return A[k1]

        else

        return A[k3]

end if