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 first element of the array to be split (i. e., A[lo]).

Construct an infinite sequence of numbers for n and 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

Algorithm:-

Step 1. Choosing the Pivot Element

->>>pivot element can determine the complexity of the algorithm i.e. whether it will be n*logn or quadratic time:

(i). we choose the low element as pivot.
This can harm us badly as the pivot might end up to be the smallest or the largest element, thus leaving one of the partitions empty.

(ii). We should choose the Median of the first, last and middle elements.
->If there are N elements, then the ceiling of N/2 is taken as the pivot element.

Example:

8, 3, 25, 6, 10, 17, 1, 2, 18, 5

First element: 8
Middle element: 10
Last element: 5

Therefore the median on [8,10,5] is 8.

Step 2. Partitioning

a. First thing is to get the pivot out of the way and swapping it with the last number.

Example: (shown using the above array elements)

5, 3, 25, 6, 10, 17, 1, 2, 18, 8

b. Now we want the elements greater than pivot to be on the right side of it and similarly the elements less than pivot to be on the left side of it.

For this we define 2 pointers, namely index1 and index2.
->>>index1 being at the first index and index2 being at the last index of the array.

   * While index1 is less than index2 we keep in incrementing index1 until we find an element    greater than pivot.
   * Similarly, while index2 is greater then index1 keep decrementing index2 until we find an element less than pivot.
   * After both index1 and index2 stop we swap the elements at the indexes of index1 and index2 respectively.

c. Restoring the pivot

When the above steps are done correctly we will get this as our output:

[5, 3, 2, 6, 1] [8] [10, 25, 18, 17]

Step 3. Recursively Sort the left and right part of the pivot.