Question

Write your algorithm that run quick sort can be made to run O(n log n)time b) Write the recurrence that shows the running time of your algorithm in (a) above c) Briefly explain (no need to prove) how your recurrence records O(n log n)time in worst-case

Answer 1

Step-by-step explanation:

a) In random Pivot Quick Sort algorithm, a Central Pivot element is chosen. In this algorithm Pivot element is selected as it is not Central Pivot. It means the array is divided such that any part contains at-least ¼ elements.

Algorithm for Quick Sort using Random Pivot

randomQuick(num[ ],low,high)

Step 1 – if low index > = high index then Exit.

Step 2 – while pivot p is not the Central Pivot.

Step 3 – Choose any value randomly as the Pivot value. Assume it as p.

Step 4 – Count the elements smaller than num[p]. Store it as small.

Step 5 – Count the elements greater than num[p]. Store it as great.

Step 6 – Assume size = (high – low + 1) . if small > = size/4 and greater >=n/4, then p is Central Pivot.

Step 7 – Use pivot p to partition num [low…high].

Step 8 – randomQuick(num, low, small - 1)

Step 9 – randomQuick(num, great + 1, high)

b) As from the above algorithm the array is partitioned in such two parts that one part has at-least n/4 elements. Thus, it is possible that in worst case, array is partitioned in two parts such that one part has n/4 elements and other part has 3n/4 elements and its time complexity will be O(log N).

Whereas there is a loop in the above algorithm. So, complexity is O(n)

Now consider the following recurrence relation:

T(n) = T(n/4) + T(3n/4) + O(n)

= O(log n) + O(n)

= O(n log n).

c) In QuickSort as randomly Pivot is generated. Here, in the above algorithm one condition follows the array is divided in such two partitions that one part has n/4 elements and the other part has 3n/4 elements.

In worst case, the height of recursion tree is Log3/4 n.