複数の再帰呼び出しを削除し、1 回の再帰呼び出しに減らすことで末尾再帰を活用することで、クイックソートを最適化できることはわかっています。
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;
}
}
しかし、末尾再帰を使用してランダム化されたクイックソートを最適化できますか?