Реализация быстрой сортировки не работает для дубликата ключа - PullRequest
Новая
       7

Реализация быстрой сортировки не работает для дубликата ключа

0 голосов
/ 27 апреля 2020

Я пытался реализовать Quicksort. Он работает нормально, за исключением случаев, когда есть дублирующий ключ, и в этом случае бесконечный l oop, и он никогда не завершается. Можете ли вы помочь мне понять, что я делаю неправильно? 

// quick sort
void quickSort(int arr[], const unsigned size)
{
    // base case
    if (size < 2)
        return;

    int pivot = arr[size / 2];
    unsigned L = 0, U = size - 1;

    // partitioning
    while (L < U) {
        while (arr[L] < pivot)
            L++;
        while (arr[U] > pivot)
            U--;

        swap(&arr[L], &arr[U]);
    }

    quickSort(arr, L); // sort left array
    quickSort(&arr[U + 1], size - L - 1); // sort right array
}
...