Logarithmic worst case Stack depth and linearithmic average running time in modified quicksort algorithm
  • linearithmictime
  • sorting
  • quicksort
  • logarithmictime
  • timecomplexity
  • array
  • stack
  •   
  • Posted: 4 years ago
  • Updated: 3 years ago
  • Edit
  • answers (1)
  • views (2384)

How will you modify the algorithm in modified Quicksort algorithm so that the worst case stack depth is \( \theta(logn) \) maintaining \( O(nlogn) \) expected running time.


Posted Answers




MODIFIED_Quicksort_NEW(A,p,r)
while(p < r)
/* Partition and sort the small subarray first */
do
q = PARTITION(A,p,r);
If(q-p+1 < r-q)
MODIFIED_Quicksort_NEW(A,p,q);
p = q+1;
else
MODIFIED_Quicksort_NEW(A,q+1,r);
r = q;

Since same partitions are done and same subarrays are sorted, expected running time is same - \( O(nlogn) \).

You need to Sign In to post your solution.