Question

that tells how many swaps are done in the worst case given n elements Consider this modification of the partition algorithm. Randomly choose three potential pivots. Partition around the median of the three pivots 3. a) Write the pseudocode for this algorithm b) If this use the quicksort algorithm, what is the running time for the worst-case scenario? When will this happen? c) Why is this algorithm better than the regular quicksort algorithm? 4. Give the pseudocode of the counting sort algorithm 5. Give the nseudocode of an algorithm that finds the minimum and the second-minimumm

solve 3

Answer 1

(a) The process in this method is the same, just the last element which we usually take in normal quicksort is swapped with the random median of three pivots found using the random (rand()) function.

partition (arr[], low, high)
{
pivot = arr[high];

i = (low - 1) // Index of smaller element

for (j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap arr[i] and arr[j]
}
}
swap arr[i + 1] and arr[high])
return (i + 1)
}

quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is now
at right place */
pi = random_partition(arr, low, high);

quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}

random_partition(arr[], lo, hi) //choosing a random pivot using random pivot
pivot1 = rand()%arr.length()-1
pivot2 = rand()%arr.length()-1
pivot3 = rand()%arr.length()-1
int pivot = medianThree(pivot1, pivot2, pivot3)
Swap arr[pivot] and arr[hi]
return partition(arr, lo, hi)

int medianThree(int a, int b, int c) { //finding median
if ((a > b) != (a > c))
return a;
else if ((b > a) != (b > c))
return b;
else
return c;
}

(b) The running time would improve if the new approach can always pick a good split. Unfortunately, it can't. It makes it impossible for one of the splits to be empty, but it can still pick a 1-to-n−2 split. It improves the probability of a good split and adds some overhead to picking the pivot, but it makes no hard guarantees on the quality of the split. Thus, the worst-case complexity of the algorithm remains O( $n^{2}$ ).

(c) In normal quicksort, the worst case occurs when the partition process always picks the greatest or smallest element as the pivot. If we consider above partition strategy where the last element is always picked as the pivot, the worst case would occur when the array is already sorted in increasing or decreasing order.

The benefit of randomized quicksort is that the distribution on input order does not matter anymore: by adding our own randomness we ensure that, regardless of the input distribution, we obtain an expected runtime of O(n log n). So, if the array is already sorted in increasing or decreasing order, it wouldn't affect the randomized algorithm.