Program sortowania przez zliczanie przestaje działać dla ciągów powyżej 300 000 elementów.

Question

Testowałam algorytm na złożoność czasową. Do 200 00 elementów ciągu działał sprawnie, jednak zwiększając do 300 000 odmawia i wyskakuje "returned -1073741571" W czym może tkwić problem? Nie sądzę że w typie int, bo limit jest wyższy. Oto kod:

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <ratio>
#include <chrono>
#include <fstream>

using namespace std;

void generuj_ciag (int T[], int N, int min_zakres, int max_zakres)
{
    int zakres = max_zakres - min_zakres + 1;
    for (int i = 0; i < N; i++)
        T[i] = min_zakres + (rand()%zakres);
}

void zapisz_ciag_do_pliku (fstream& wyjscie, int T[], int N)
{
    for (int i = 0; i < N; i++)
        wyjscie << T[i] << " ";
    wyjscie << endl << endl;
}

void sortowanie_przez_zliczanie (int T[], int N, int min_zakres, int max_zakres)
{
    int zakres = max_zakres - min_zakres + 1;
    int* L = new int [zakres]();
    int P[N] = {0};
    for (int i = 0; i < N; i++)
        L[T[i]-min_zakres]++;
    for (int i = 1; i < zakres; i++)
        L[i] += L[i-1];
    for (int i = N-1 ; i >= 0 ; i--)
        P[L[T[i]]--] = T[i];
    for (int i = 0; i < N; i++)
        T[i] = P[i];
}

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

    fstream wyjscie;
    fstream obliczenia;

    wyjscie.open ("wyniki.txt", ios::app); //plik z wylosowanym ciagiem i rozwiazaniem
    obliczenia.open ("obliczenia.txt", ios::app); //plik z dlugoscia obliczen w zaleznosci od dlugosci ciagu

//Wygenerowanie i zapisanie ciagu do pliku

    int N = 1000000; //dlugosc losowanego ciagu
    int T[N] = {0}; //wyzerowanie tablicy
    int min_zakres = 0; //wartosc minimalna
    int max_zakres = 100; //wartosc maksymalna

    generuj_ciag (T, N, min_zakres, max_zakres); //funkcja losujaca elementy ciagu
    wyjscie << "Dlugosc ciagu: " << N << endl << endl;
    zapisz_ciag_do_pliku (wyjscie, T, N); //funkcja zapisujaca wylosowany ciag do pliku

//Wykonanie sortowania i zmierzenie czasu - tu przestaje dzialac

    std::chrono::high_resolution_clock::time_point start;
    std::chrono::high_resolution_clock::time_point stop;
    std::chrono::duration <double> czas;

    start = std::chrono::high_resolution_clock::now();
    sortowanie_przez_zliczanie (T, N, min_zakres, max_zakres); //sortowanie
    stop = std::chrono::high_resolution_clock::now();
    czas = stop-start;

//Zapisanie wynikow

    zapisz_ciag_do_pliku (wyjscie, T, N);
    wyjscie << endl << "Czas obliczen: " << setw(9) << czas.count() << " s."<< endl << "_________________________" << endl << endl;
    obliczenia << N << "; " << setw(9) << czas.count() << endl;

    wyjscie.close();
    obliczenia.close();

    return 0;
}

 

Comments

podejrzewam, że operując na tablicach int ... kończysz ich zakres

---

Racja, ilość danych w tablicy była za ciężka... Deklarując tablicę dynamiczną działa. Dzięki