CODEWITHSUNDEEP
sortingquicksortrandomized-algorithm
ken adams
ken adams

Reputation: 1

Can we optimize randomized quicksort by tail recursion?

I know we can optimize quicksort by leveraging tail recursion by removing more than 1 recursion calls and reducing it to once single recursion call:-

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);
 
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void quickSort(int arr[], int low, int high)
{
start:
    if (low < high)
    {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
 
        low = pi+1;
        high = high;
        goto start;
    }
}

But can we optimize randomized quicksort with tail recursion?

Upvotes: 0

Views: 82

Answers (1)

dkprio_13
dkprio_13

Reputation: 11

Tail stack recursion focuses on optimizing recursive calls. The only difference between randomized quicksort and normal quicksort is the partition function which selects a random pivot in case of randomized quicksort. Note that this partition function is non-recursive. As the recursive part of both randomized quicksort and normal quicksort is same, same optimization can be done in both cases. So, yes.

Upvotes: 1

Related Questions