Quicksort не работает с большими массивами - PullRequest
Новая
       12

Quicksort не работает с большими массивами

1 голос
/ 11 декабря 2019

Я пытаюсь отсортировать большие массивы с помощью Quicksort и Mergesort для оценки производительности.

У меня проблема: если я навязываю большое количество элементов в массиве, программа не начинает генерироватьзначения случайным образом. В приведенном ниже коде, если N=500000, это работает очень хорошо. Если N > 500000, например 1000000, это не работает. С MergeSort ограничение составляет 200000. Я пробовал на нескольких устройствах C ++ в Eclipse IDE.

Кто-то знает, как решить проблему? 

#define N 800000
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <chrono>

using namespace std;

void Exchange(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int Partition(int A[], int p, int r) {
     int x = A[r];
     int i = p - 1;
     for (int j = p; j <= r; j++) {
         if (A[j] < x) {
             i++;
             Exchange(&A[i], &A[j]);
         }

    }
    Exchange(&A[i + 1], &A[r]);
    return i + 1;
}

int RPartition(int A[], int p, int r) {
    srand(time(NULL));
    int i = p + rand() % (p - r);
    Exchange(&A[i], &A[r]);
    return Partition(A, p, r);
}

void QuickSort(int A[], int p, int r) {
    if (p < r) {
        int q = RPartition(A, p, r);
        QuickSort(A, p, q - 1);
        QuickSort(A, q + 1, r);
    }
}

void Stampa(int A[], int n) {
    for (int i = 0; i < n; i++) {
        cout << A[i] << "\n";
    }
}

int main() {
    srand(50000);
    int A[N];
    for (int i = 0; i < N; i++) {
        A[i] = rand();
    }

    cout << "Array non ordinato\n";
    Stampa(A, N);
    auto start = std::chrono::system_clock::now();
    QuickSort(A, 0, N - 1);
    auto end = std::chrono::system_clock::now();
    cout << "\nArray ordinato\n";
    Stampa(A, N);
    std::chrono::duration<double> elapsed = end - start;
    cout << "Elapsed time: " << elapsed.count() << "s";
}

1 Ответ

0 голосов
/ 13 декабря 2019

Объяснение очень простое: вы выделяете массив как локальную переменную с автоматическим хранением (он же в стеке ), следовательно, если размер слишком велик, вы получите переполнение стека .

Вы должны либо выделить массив из кучи, либо определить его как статические данные.

Вот модифицированная версия: 

int main() {
    srand(time(NULL));

    int *A = new int[N];
    for (int i = 0; i < N; i++) {
        A[i] = rand();
    }

    cout << "Array non ordinato\n";
    Stampa(A, N);

    auto start = std::chrono::system_clock::now();
    QuickSort(A, 0, N - 1);
    auto end = std::chrono::system_clock::now();

    cout << "\nArray ordinato\n";
    Stampa(A, N);

    std::chrono::duration<double> elapsed = end - start;
    cout << "Elapsed time: " << elapsed.count() << "s";
    delete[] A;
}
...