Program C- sortowanie-zasieg tablic

Question

Cześć,

Mam problem z programem do sortowania w języku C. Program ma za zadanie posortować 3 różne tablice liczb określoną metodą i co 10 tys elementów zapisuje uzyskany czas do pliku. Program działa i z nim nie ma problemu do 500 000 elementów, lecz gdy inicjuję tablice składającą się z więcej niż 500 000 elementów w ogóle nie startuje, zamyka się po 3 sekundach, testowałem na dwóch różnych laptopach i to samo. Zawszę gdy deklaruję tablicę z ilością większą niż 500 000 elementów występuje ten problem, a potrzebuję przeprowadzić analizę czasów do 1 000 000 elementów. Ktoś ma jakiś pomysł?

Oto kod:

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
void wypelnij_losowymi(int tab[],int pomocnicza)
{
	srand(time(NULL));
	for(int i=0;i<pomocnicza;i++)
	{
		tab[i]=rand();
	}
}
void wypelnij_posortowanymi(int tab[], int pomocnicza)
{
	int a=0;
	for(int i=0;i<pomocnicza;i++)
	{
		tab[i]=a;
		a++;
	}
}
void wypelnij012(int tab[], int pomocnicza)
{
	int a=0;
	for(int i=0;i<pomocnicza;i++)
	{
		tab[i]=a;
		a++;
		if(a==2)
		a=0;
	}
}
void sortowanie(int tab[], int pomocnicza)
{
int min,i,j,temp;
for (i=0;i<pomocnicza-1;i++)
{
min=i;
for (j=i+1;j<pomocnicza;j++)
if (tab[j]<tab[min]) min=j;
temp=tab[min];
tab[min]=tab[i];
tab[i]=temp;
}
}

int main()
{	
	FILE *zapis;
	zapis=fopen("losowe.txt", "w");
	if(zapis==NULL)
	{
		printf("Cos poszlo nie tak z otwarciem pliku");
		exit(1);
	}	
	FILE *zapis2;
	zapis2=fopen("posortowane.txt", "w");
	if(zapis2==NULL)
	{
		printf("Cos poszlo nie tak z otwarciem pliku");
		exit(1);
	}
		FILE *zapis3;
	zapis3=fopen("Z_zakresu0-1-2.txt", "w");
	if(zapis3==NULL)
	{
		printf("Cos poszlo nie tak z otwarciem pliku");
		exit(1);
	}
	int ilosc=1000000;        // Tutaj deklaruje wielkość tablicy
	int tab[ilosc];
	int pomocnicza=0;
	double duration;
	clock_t start,stop;
	start=clock();	
	
	printf("Tablica wypelniona losowymi: \n");
	do
		{
		pomocnicza+=10000;
		wypelnij_losowymi(tab,pomocnicza);
		sortowanie(tab,pomocnicza);
		stop=clock();
		printf("%2.3f, przy %d\n",(double)(stop-start)/ CLOCKS_PER_SEC,pomocnicza);
		fprintf(zapis,"%d \t %2.3f\n",pomocnicza, (double)(stop-start)/ CLOCKS_PER_SEC);
		}while(pomocnicza<1000000);
	fprintf(zapis,"\n");
	printf("\n");	
	pomocnicza=0;
	start=clock();
	
	printf("Teraz tablica wypelniona posortowanymi\n");
	do
		{
		pomocnicza+=10000;
		wypelnij_posortowanymi(tab,pomocnicza);
		sortowanie(tab,pomocnicza);
		stop=clock();
		printf("%2.3f, przy %d\n",(double)(stop-start)/ CLOCKS_PER_SEC,pomocnicza);
		fprintf(zapis2,"%d \t %2.3f\n",pomocnicza, (double)(stop-start)/ CLOCKS_PER_SEC);
		}while(pomocnicza<1000000);
		fprintf(zapis2,"\n");
		printf("\n");
		
	pomocnicza=0;
	start=clock();
	printf("Teraz tablica wypelniona liczbami 0,1,2\n");
	do
		{
		pomocnicza+=10000;
		wypelnij012(tab,pomocnicza);
		sortowanie(tab,pomocnicza);
		stop=clock();
		printf("%2.3f, przy %d\n",(double)(stop-start)/ CLOCKS_PER_SEC,pomocnicza);
		fprintf(zapis3,"%d \t %2.3f\n",pomocnicza, (double)(stop-start)/ CLOCKS_PER_SEC);
		}while(pomocnicza<1000000);
		
	fclose(zapis);
	fclose(zapis2);
	fclose(zapis3);
	return 0;
}

 

Answer 1

Przepełniasz stos. Nie wiem czym kompilujesz ale w MSVC domyślna wielkość stosu to 1.5 MB. Int zajmuje 4B (lub 8, ale zakładam mniejszy). Oznacza to, że sama tablica miliona intów zajmuje 4 MB :P Troszke więcej niż 1 :P

Do alokowania tak dużych tablic lepiej nadaje się sterta. Użyj dynamicznej alokacji:

int *very_large_array = malloc(sizeof(int) * 1000000);

 

Comments

Tego brakowało, dzięki

---

Sprawdzałem, ja na stercie moge 2GB zaalokować :P