Ошибка 'stack overflow' в алгоритме 'quicksort'

Рейтинг: 0Ответов: 1Опубликовано: 08.04.2023

Алгоритм должен был, через рекурсию, упорядочить массив методом быстрой сортировки. Но, при первом же шаге, поялвляется ошибка stack overflow на 29 строке.

void quicsort(char* items, int lem);

void qs(char* items, int left, int right);


int main() {
    char str[] = "jfjmckldoelazlkper";
    int i;

    cout << "origin mass: " << str << "\n";

    quicsort(str, strlen(str));

    cout << "New mass: " << str << "\n";

    return 0;
}


void quicsort(char *items, int len) {
    cout << *items;
    qs(items, 0, len - 1);
}

void qs(char *items, int left, int right) {
    int i, j;
    int x, y;

    i = left; j = right;
    x = items[(left + right) / 2];

    do {
        while ((items[i] < x) && (i < right)) i++;
        while ((x < items[j]) && (j > left)) j--;

        if (i <= j) {
            y = items[i];
            items[i] = items[j];
            items[j] = y;
            i++; y--;
        }
    } while (i <= j);

    if (left < j) qs(items, left, j);
    if (i < right) qs(items, i, right);
}

Ответы

▲ 0Принят

У вас пара ошибка/опечатка в коде. Вы вместо того чтобы уменьшать j уменьшаете y.

        if (i <= j) {
            y = items[i];
            items[i] = items[j];
            items[j] = y;
//       Вот тут: 
            i++; y--;
        }

        if (i <= j) {
            y = items[i];
            items[i] = items[j];
            items[j] = y;
// Должно быть так:
            i++; j--;
        }