Можем ли мы оптимизировать рандомизированную быструю сортировку с помощью хвостовой рекурсии?

Question

Я знаю, что мы можем оптимизировать быструю сортировку, используя хвостовую рекурсию, удалив более одного вызова рекурсии и сократив его до однократного одного вызова рекурсии: -

      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;
    }
}

Но можем ли мы оптимизировать рандомизированную быструю сортировку с помощью хвостовой рекурсии?

Answer 1

Рекурсия хвостового стека направлена ​​на оптимизацию рекурсивных вызовов. Единственное различие между рандомизированной быстрой сортировкой и обычной быстрой сортировкой - это функция разделения, которая выбирает случайный поворот в случае рандомизированной быстрой сортировки. Обратите внимание, что эта функция распределения нерекурсивна. Поскольку рекурсивная часть как рандомизированной быстрой сортировки, так и обычной быстрой сортировки одинакова, одинаковая оптимизация может выполняться в обоих случаях. Так да.