Быстрая сортировка результатов в бесконечном цикле - PullRequest
Новая
       25

Быстрая сортировка результатов в бесконечном цикле

0 голосов
/ 30 сентября 2019

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

template<typename T>
void quickSort(T list[], int lowerBound, int upperBound)
{
    cout.setf(ios::fixed | ios::showpoint);
    cout.precision(16);

    TimerSystem timer;
    timer.startClock();

    upperBound = upperBound - 1;

    long int i = lowerBound;
    long int j = upperBound;
    long int pivot = list[(lowerBound + upperBound) / 2];
    T temp;

    while (i <= j)
    {
        while (list[i] < pivot)
        {
            i += 1;
        }

        while (list[j] > pivot)
        {
            j -= 1;
        }

        if (i <= j)
        {
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
            i += 1;
            j -= 1;
        }
    }

    if (lowerBound < j)
    {
        quickSort(list, lowerBound, j);
    }

    if (i < upperBound)
    {
        quickSort(list, i, upperBound);
    }


    cout << "USE FINAL TIME RECORDING!! QuickSort took " << timer.getTime() << "seconds to sort" << endl;
    cout << endl;
}

Ответы [ 2 ]

0 голосов
/ 30 сентября 2019

Поскольку в коде используется cout.precision (16), я предполагаю, что list [] - это массив чисел с плавающей запятой или двойных чисел. Однако pivot определяется как тип long int, тогда как он должен иметь тип T: 

    T pivot = list[(lowerBound + upperBound) / 2];

Если тип pivot указан как long int, это объясняет бесконечный цикл, поскольку внутренние циклы while полагаются на остановку, если любой из списков [i] == pivot и / или list [j] == pivot, что не произойдет, если фактический pivot: list [(lowerBound + upperBound) / 2] точно не равен целому числу.

Еще одна проблема - upperbound = upperbound - 1;Это будет происходить в начальном и каждом рекурсивном экземпляре быстрой сортировки. Вместо этого этот оператор должен быть удален, и начальный вызов для списка размера N должен быть 

    quickSort(list, 0, N-1);

. Нет необходимости вводить i и j как long int, просто набирается как int, это хорошодостаточно, но это не вызывает никаких проблем.

0 голосов
/ 30 сентября 2019

С первого взгляда 

while (i <= j)

выглядит подозрительно, замените его на 

while (i < j)

и повторите попытку.

...