Qsort при компиляции выдает переполнение стека

@Kvmensku · Регистрация: 24.11.2017

Author24 — интернет-сервис помощи студентам

Помогите найти ошибку(при компиляции выдает переполнение стека). Заранее спасибо

C++

void sort(int *arr, int first, int last) {
    int i = first; int j = last; int tmp; int mid = arr[(first + last) / 2];
    while (i <= j) {
        while (arr[i] > mid)
            i++;
        while (arr[j] < mid)
            j--;
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        if (j>first) sort(arr, first, j);
        if (i<last) sort(arr, i, last);
    }
}

@Kuzia domovenok · 30.11.2017, 16:31

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

Добавлено через 1 минуту

Сообщение от Kvmensku

if (j>first) sort(arr, first, j);
if (i<last) sort(arr, i, last);

это должно быть не в цикле, а в конце, за его пределами.

@Kvmensku · 30.11.2017, 17:20 **[ТС]**

Сообщение от Kuzia domovenok

это должно быть не в цикле, а в конце, за его пределами.

Исправил, ошибка пропала, но программа не заработала.
Тело главной функции:

C++

int main() {
    srand(time(NULL));
    int n;
    cin >> n;
    int *arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100 + 1;
        if (i % 6 == 0) cout << endl;
        cout << "[" << setw(2) << i << "] -" << setw(3) << arr[i] << " ";
    }
    sort(arr, 0, n - 1);
    cout << endl << endl;
    for (int i = 0; i < n; i++) {
        if (i % 6 == 0) cout << endl;
        cout << "[" << setw(2) << i << "] -" << setw(3) << arr[i] << " ";
    }
    system("pause");
    return 0;
}

Добавлено через 37 минут
нашел решение, рабочий вариант:

C++

 #include <cstdlib>
#include <iomanip>
using namespace std;
 
void sort(int *arr, int first, int last) {
    int i = first; int j = last; int tmp; int mid = arr[(first + last) / 2];
    while (i <= j) {
    
        while (arr[i] > mid)
            i++;
        while (arr[j] < mid)
            j--;
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++; j--;
        }
    }
    
    if (j > first) sort(arr, first, j);
    if (i < last) sort(arr, i, last);
}
int main() {
    srand(time(NULL));
    int n;
    cin >> n;
    int *arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100 + 1;
        if (i % 6 == 0) cout << endl;
        cout << "[" << setw(2) << i << "] -" << setw(3) << arr[i] << " ";
    }
    sort(arr, 0, n - 1);
    cout << endl << endl;
    for (int i = 0; i < n; i++) {
        if (i % 6 == 0) cout << endl;
        cout << "[" << setw(2) << i << "] -" << setw(3) << arr[i] << " ";
    }
    system("pause");
    return 0;
}

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	30.11.2017, 16:31	2
	переполнение стека в рекурсивной программе обычно означает что программа ушла в бесконечную рекурсию и не может остановиться, проверь условие остановки рекурсии. Добавлено через 1 минуту Сообщение от Kvmensku if (j>first) sort(arr, first, j); if (i<last) sort(arr, i, last); это должно быть не в цикле, а в конце, за его пределами. 0

	30.11.2017, 17:20