Question

1. What is the running time of QUICKSORT on an array A of length n containing all the same values? What is the running time if A contains distinct elements sorted in decreasing order? Explain your answers in detail, referring to the source code for PARTITION and QUICKSORT.

Answer 1

Solution

QUICKSORT(A[], low, high)

{

if (low < high);

p = PARTITION(A, low, high);

//p is the partitioning index and A[p] is in the correct position.

QUICKSORT(A[], low, p - 1);

QUICKSORT(A[], p + 1, high);

}

PARTITION(A[], low, high)

{

pivot = A[high];

i = (low - 1) // i is the index of element smaller than pivot element

for (j = low; j <= high- 1; j++)

{

if (A[j] < pivot)

{

i++;

swap A[i] and A[j]

}

}

swap A[i + 1] and A[high]

return (i + 1)

}

All the elements have same value

When all elements in the array A[p..r] have the same value value returned by PARTITION is r.

Let array A has n elements. Index of the first element is 0 and index of the last element is n-1.

The first call to QUICKSORT is with low = 0 and high = n-1.

QUICKSORT(A[], 0, n-1) calls PARTITION(A[], 0, n-1).

Since all the elements have same value as pivot element A[n-1] , so i = n-2. In the return statement in PARTITION procedure the value returned is i+1 = n-1.

So the pivot elemnt A[n-1] is at correct position.

Next call to QUICKSORT is with low = 0 and high = n-2.

QUICKSORT(A[], 0, n-2) calls PARTITION(A[], 0, n-2).

Since all the elements have same value as pivot element A[n-2] , so i = n-3. In the return statement in PARTITION procedure the value returned is i+1 = n-2.

So the pivot elemnt A[n-2] is at correct position.

So the PARTITION procedure is called n times for n elements and each time the size of the array we are working with reduces with just one.

So the time complexity of the Quicksort algorithm in this case is: T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1) = O(n²)

It is the most unbalanced case, in which a single quicksort call involves O(n) work and two recursive calls on lists of size 0 and n−1.

Different elements in decreasing order.

Let array A has n elements. Index of the first element is 0 and index of the last element is n-1.

The first call to QUICKSORT is with low = 0 and high = n-1.

QUICKSORT(A[], 0, n-1) calls PARTITION(A[], 0, n-1).

All the elements are scanned from index 1 to n-2. Since none of the elements have value less than pivot element A[n-1] so A[0] and A[n-1] are swapped.

Index value returned to calling QUICKSORT is 0, so p = 0.

Now the size of the array we have to scan is n-1.(from index 1 to index n - 1)

The second call to QUICKSORT is with low = 1 and high = n-1.

QUICKSORT(A[], 1, n-1) calls PARTITION(A[], 1, n-1).

All the elements are scanned from index 2 to n-2. Since none of the elements have value less than pivot element A[n-1] so pivot element A[n-1] remains at same index.

Index value returned to calling QUICKSORT is n-1, so p = n-1.

Now the size of the array we have to scan is n-2.(from index 1 to index n - 2)

So for each call to QUICKSORT, we are partitioning the array of size n to 2 subarrays.One subarray has size 0 and another subarray has size n-1

This is also an unbalanced case.

So the time complexity of the Quicksort algorithm in this case is: T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1) = O(n²)