Question

Consider QuickSort on the array A[1:n] and assume that the pivot element x (used to split the array A[lo:hi] into two portions such that all elements in the left portion A[lo:m] are ≤x and all elements in the right portion A[m:hi] are ≥x) is the second element of the array to be split (i. e., A[lo+1]).

For a specific value of n at least 13 (your choice), construct an assignment of the numbers 1...n to the n array elements that causes QuickSort, with the stated choice of pivot, to

(a) execute optimally (that is A[lo:m] and A[m:hi] are always of equal size)

(b) execute in the slowest possible way.

Answer 1

Answer : Given data

* It is given that the pivot element (x) is always chosen to be the first element of the array to be sorted using quicksort.

* If you want the algorithm for the method given in the question just use the regular quicksort where the pivot element is chosen the very first element passed to it (as mentioned by you initially). Else if you want the solution to the question follow :

* a - > In this part we are asked to give a sequence of numbers that makes the algorithm work optimally. So only input to the quicksort is asked and no algorithm in both parts.

* please note that the definition of optimality is total elements smaller than pivot element (x) should be equal to the total elements greater than pivot element (x).

* Let us take n = 15 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

the most optimal assignments of numbers is :

[8,4,2,1,3,6,5,7,12,10,9,11,14,13,15[

* Initiall we take pivot element (x) = first element of array i.e; 8 So, elements in the left side are [4,2,1,3,6,5,7)]and elements in the right side are[12,10,9,11,14,13,15)]i.e; both are 7 in number.

* Similarly when in the left subarray [4,2,1,3,6,5,7] pivot is 4 and division is as follows left = [2,1,3] right [6,5,7]

and right sub array [12,10,9,11,14,13,15] pivot is 12, left sub array[10,9,11] right sub array = [14,13,15]

* Similarly for all smaller sub arrays :

[2,1,3] pivot = 2 left sub array = [1] right sub array = [3]

[6,5,7] pivot = 6 left sub array = [5] right sub array = [7]

[10,9,11] pivot = 10 left sub array = [9] right sub array = [11]

[14,13,15] pivot = 14 left sub array = [13] right sub array = [15]

* So, we can see always the number of elements in the left and right sub array is always equal.

b - > the input for which the quicksort performs worst

* The worst case for quicksort (in this case ) and for any other case :

a. When array is already sorted i.e; 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

b. When array is sorted in reverse order i.e; 15,14,13,12,11,10,9,8,7,6,5,4,3,2,1.

c. When all elements are same.

* So let us take first case:

* array = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15], pivot = 1, left sub array = [ ] (empty), right sub tree = [2,3,4,5,6,7,8,9,10,11,12,13,14,15]

* array = [2,3,4,5,6,7,8,9,10,11,12,13,14,15], pivot = 2, left sub tree = [ ] (empty), right sub tree = [3,4,5,6,7,8,9,10,11,12,13,14,15] and the process goes on dividing the array into two arrays left = 0 elements and right = n-1 arrays. And each process will take O(n) * so total time complexity = (n-1)O(n) i.e; O(n²) assymptotically.

________________THE END________________-