Как изменить итеративную quicksort с фиксированным шарниром на итеративную quicksort со случайным стержнем?

Question

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

void swap (int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 


int partition (int arr[], int l, int h) 
{ 
    int x = arr[h]; 
    int i = (l - 1); 
    for (int j = l; j <= h- 1; j++) 
    { 
     if (arr[j] <= x) 
     { 
      i++; 
      swap (&arr[i], &arr[j]); 
     } 
    } 
    swap (&arr[i + 1], &arr[h]); 
    return (i + 1); 
} 

void quickSortIterative (int arr[], int l, int h) 
{ 
    int stack[ h - l + 1 ]; 
    int top = -1; 

    stack[ ++top ] = l; 
    stack[ ++top ] = h; 

    while (top >= 0) 
    { 
     h = stack[ top-- ]; 
     l = stack[ top-- ]; 

     int p = partition(arr, l, h); 

     if (p-1 > l) 
     { 
      stack[ ++top ] = l; 
      stack[ ++top ] = p - 1; 
     } 
     if (p+1 < h) 
     { 
      stack[ ++top ] = p + 1; 
      stack[ ++top ] = h; 
     } 
    } 
} 

Я попытался изменить линии

int x = arr[h]; 

и

swap(&arr[i+1], &arr[j]); 

к

int r = l+rand()%(h-l); 
int x = arr[r]; 

, а затем

swap(&arr[i+1], &arr[r]); 

, но это не сортировка должным образом. Очевидно, что я делаю что-то не так. Пожалуйста помоги.

Answer 1

Ваша функция перегородки предполагает, что стержень находится в конце раздела. Рассмотрим сначала перемещение вашего случайного стержня в конец раздела.

т.е. добавить

swap(&arr[r], &arr[h]); 

после выбора шарнира.

Answer 2

Проблема в том, что теперь функция «partition» перемещает ось вращения, поэтому она не остается в индексе r. И функция также пропускает последний элемент (по индексу h). Самым простым решением было бы поместить стержень в крайнее правое положение только после его выбора, и остаются все другие то же самое: положить swap(&arr[r], &arr[h]); до первого цикла в partition() и восстановить последнюю подкачку swap (&arr[i + 1], &arr[h]);