реализация quicksort с разбиением на срединную область в C++

Question

Я изо всех сил пытался решить эту проблему самостоятельно, но это еще больше смутило меня. Я смотрю на эти образцы кода для quicksort, которые использовали медиану для создания раздела на ней, и я попробовал это на одном массиве образцов, например A = {1,8,4,6,7,10,11}, и я не получил правильное разбиение. Код раздела ниже:

void swap(int &x, int &y){ 
    int temp=x; 
    x=y; 
    y=temp; 
} 
// 
int partition(int arr[],int low,int high){ 
int pivot=arr[(low+high)/2]; 
while(low<=high){ 
    while(arr[low]<pivot) low++; 
    while(arr[high]>pivot) high--; 
    if(low<=high){ 
     swap(arr[low],arr[high]); 
     low++; 
     high--; 
    } 
} 
return low; 
} 

Для моего примера шарнира 6 так что код первого свопы 8 и 6 в массиве А, а затем останавливается. Он не ставит все меньшие значения, чем pivot = 6 до этого и большие выше. Я предполагаю, что проблема заключается в том, что мы предполагаем, что мы всегда можем найти два значения слева и справа от поворота для замены, но в этом примере правая сторона в порядке. Будут оценены любые комментарии или идеи.
Всего несколько обновлений: (1) мое внимание здесь сосредоточено на части быстрого сортировки, и я знаю следующие шаги, которые делают рекурсивный метод. (2) Я видел эти методы во многих ссылках даже на этом сайте Quick Sort - Middle Pivot implementation strange behaviour (или в книге «взломать книгу кодирования», стр. 119, написанной в java), и они утверждают, что она работает, но я сомневаюсь в этом (я имею в виду раздел раздел, он может каким-то образом получить отсортированный массив по любой причине, но правильный раздел должен быть реализован таким образом, чтобы все числа, которые меньше, чем элемент разбиения, приходили ко всем элементам, которые больше его.) В моем массиве выборки A он заканчивается A = {1,6,4,8,7,10,11 }, который не является правильным разделом, поскольку 4 - после 6 (наш стержень).

Answer 1

В вашей реализации разделов есть некоторые очевидные ошибки. Один из самых больших состоит в том, что вы не повторно сравниваете элемент, который вы используете swap.

Когда вы переходите в Quicksort, вам нужно только перемещать элементы, превышающие опорный элемент, после элемента поворота. Таким образом, простая реализация будет ...

int partition(int arr[], int begin, int end) { 

    int pivot = arr[begin + ((end - begin)/2)]; 

    while (begin != end) { 

    if (arr[begin] < pivot) 
     begin++; 
    else 
     swap(arr[begin], arr[end--]); 
    } 

    return end; 
} 

Обратите внимание, сложность зависит от качества шарнира, поэтому медиана будет идеальной. Однако это потребует итерации по всем элементам O(n).

Имейте в виду, что выбор середины массива не всегда даст хороший поворот. Существует несколько стратегий для выбора хорошего стержня (рандомизация, выборка и медиана и т. Д.).