0

Доброго времени суток. Изучаю алгоритмы и в качестве задания реализовал быструю сортировку(см. код ниже). Сравниваю с алгоритмами в мировой паутине, ничем кардинально не отличается, но мой вызывает Stack Overflow, подскажите, почему?

void my_qsort(vector<int>& arr, int l, int r)
{
    int left = l;
    int right = r;
    int mid = left + (right - left) / 2;

    while (left <= right) {
        while (arr[left] < mid) {
            left++;
        }
        while (arr[right] > mid) {
            right--;
        }
        if (left <= right) {
            swap(arr[left++], arr[right++]);
        }
    }
    if (l < right) {
        my_qsort(arr, l, right);
    }
    if (r > left) {
        my_qsort(arr, r, left);
    }
}
8
  • 2
    Во-первых, центральный элемент (mid) неправильный, он должен быть элементом из массива, то есть mid = arr[eft + (right - left) / 2]; а проще mid = arr[(left+right)/2]; 25 апр 2017 в 16:54
  • Да ваш код вообще делает черт знает что. Одно сравнение arr[left] < mid чего стоит - вот что оно делает, по-вашему?...
    – Harry
    25 апр 2017 в 16:55
  • 2
    Во-вторых, второй рекурсивный вызов со странными границами. Должно быть my_qsort(arr, left, r) 25 апр 2017 в 16:56
  • @Harry сравнивает текущий элемент с опорным, если он меньше, переходит к следующему, верно? 25 апр 2017 в 16:59
  • 1
    @ТарасСус я их делал после беглого осмотра. Под отладкой где проблема возникает? Еще одну ошибку только что увидел: swap(arr[left++], arr[right--]) 25 апр 2017 в 17:13

1 ответ 1

1
void my_qsort(vector<int>& arr, int l, int r)
{
    int left = l;
    int right = r;
    int mid = arr[(left + right) / 2];

    while (left <= right) {
        while (arr[left] < mid) {
            left++;
        }
        while (arr[right] > mid) {
            right--;
        }
        if (left <= right) {
            swap(arr[left++], arr[right--]);
        }
    }
    if (l < right) {
        my_qsort(arr, l, right);
    }
    if (r > left) {
        my_qsort(arr, left, r);
    }
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.