Answer the following questions on sorting algorithms Complet

Answer the following questions on sorting algorithms. Complete the quicksort method given below. selectPivot method given above does nothing in its current form. Will this quick sort algorithm work even with this version of selectPivot method? Answer yes or no, and give a brief reason for your answer. How can you improve the selectPivot method to enhance the overall performance? Write your code for selectPivot method.

Solution

1)

public static void quickSort(Comparable[] A, int s, int e){

if(s >= e) return;

int pi = divide(A, s, e);

quickSort(A, s, pi-1);

quickSort(A, pi+1, e);

}

2) Yes quicksort will work as , currently as leftmost element is currently used as pivot in divide function.

3) We can improve selectPivot method to randomly select pivot element to enhance overall performance. It reduce the chance that the worse case does not happen often, which is diving the array into 1 and n-1 elements. It ensures that equal elements are there in both the parts when dividing.