QuickSort with Random Pivot

Question

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

Однако, когда я это делаю, код работает очень медленно. Если я попытаюсь отсортировать массив с 29 элементами, он будет работать с 2 секундами, но как только я увеличу размер до 30+, включая (30), алгоритм работает очень медленно. Сортировка массива с 30 элементами занимает около 10 секунд +, и если я пойду выше, вы получите идею.

Это не проблема, если у меня есть фиксированная точка поворота. Я могу сортировать массив размером 100 000 без каких-либо проблем.

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

С уважением!

protected int Partition(int[] v, int low, int high, boolean FixedPivot) 
{ 
    int pivot = 0; 
    if(!FixedPivot) 
     pivot = RandomPivot(v, low, high); //If I pick a random pivot point then it runs extremly slow for some reason. 
    else 
     pivot = FixedPivot(v, low, high); //This one works fine, I can sort quickly without any problem. 

    int i = low - 1; 
    int j = high + 1; 
    while(true) 
    { 
     do j--; while(v[j] > pivot); 
     do i++; while(v[i] < pivot); 
     if(i < j) 
      Swap(v, i, j); 
     else 
      return j; 
    } 
} 
protected int FixedPivot(int[] v, int low, int high) 
{ 
    int average = (low + high)/2; 
    return Math.max(Math.min(v[low], v[average]), Math.min(Math.max(v[low], v[average]), v[high])); 
} 
protected int RandomPivot(int[] v, int low, int high) 
{ 
    int X = 0; 
    int Y = 0; 
    int Z = 0; 
    Random random = new Random(); 
    int range = (high - low) + low; 
    if(range > 0) 
    { 
     X = random.nextInt(range); 
     Y = random.nextInt(range); 
     Z = random.nextInt(range); 
    } 
    return Math.max(Math.min(v[X], v[Y]), Math.min(Math.max(v[X], v[Y]), v[Z])); 
} 

Answer 1

Я думаю, что проблема в том, что random.nextInt(range); между 0 и high и вы хотите, чтобы это было между low и high. Вот как это исправить:

int range = (high - low); 
if(range > 0) 
{ 
    X = random.nextInt(range) + low; 
    Y = random.nextInt(range) + low; 
    Z = random.nextInt(range) + low; 
}