• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

mierzenie czasu sortowania - "program przestal dzialac".

Object Storage Arubacloud
0 głosów
269 wizyt
pytanie zadane 8 kwietnia 2018 w C i C++ przez piotrrussw Nowicjusz (240 p.)

Witam, mam problem, miałem za zadanie zrobić program, który mierzy czas sortowania liczb z pliku za pomocą sortowania przez wstawianie oraz sortowania przez scalanie i w każdym rozważyć po 3 przypadki (najgorszy, losowy, najlepszy). Wszystko mi działa, ale jeżeli próbuje sortować ponad 5000 liczb, to konsola się bugguje i wyskakuje "Program przestał działać". Jest to niewątpliwie problem dla mnie, gdyż ciężko mi jest pokazać różnice na tak małej ilości liczb. Zerknie ktoś okiem i powie, czy mogę w jakiś sposób to zmienić?

 

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <windows.h>

const int N = 7000;

void Scalaj(int T[], int p, int mid, int k)
// p - poczatek, k - koniec, mid - srodek

{
int T2[N];        // tablica pomocnicza
int p1 =  p,     k1  = mid; // podtablica 1
int p2 =  mid+1, k2  = k;   // podtablica 2

int i = p1;
while((p1 <= k1) && (p2 <= k2))
{
  if(T[p1] < T[p2])
   {
    T2[i] = T[p1];
    p1++;
	}
	else
		{
		T2[i] = T[p2];
		p2++;
		}
		i++;
}

while(p1 <= k1)
{
 T2[i] = T[p1];
 p1++;
 i++;
}
while(p2 <= k2)
{
 T2[i] = T[p2];
 p2++;
 i++;
}
// skopiuj z tablicy tymczasowej do oryginalnej
 for(i = p; i <= k; i++)
    T[i] = T2[i];
}

void MergeSort(int T[], int p, int k)
{
  if(p < k)
  {
    int mid = (p + k) / 2;  // srodek
    MergeSort(T, p, mid);   // sortuj lewa polowe
    MergeSort(T, mid+1, k); // sortuj prawa polowe
    Scalaj(T, p, mid, k);
  }
}
void InsertSort(int T[])
{
for(int i=1; i<N; i++)
 {
 int j=i; // 0..i-1 jest juz posortowane
 int temp = T[j];
 while ((j>0) && (T[j-1]>temp))
    {
    T[j]=T[j-1];
    j--;
    }
 T[j]=temp;
 }
}
void RandomCaseFile() {
srand(time(NULL));
std::ofstream FileRandom("random.txt");
int temp = N;
while(temp) {
    FileRandom << rand()%10000 << std::endl;
    temp--;
FileRandom.close();
}
}
void SortedCaseFile() {
std::ofstream FileBest("sorted.txt");
int temp = N;
for(int i=1; i<=N; i++) {
    FileBest << i << std::endl;
}
FileBest.close();
}
void UnsortedCaseFile() {
std::ofstream FileWorst("unsorted.txt");
int temp = N;
for(int i=N; i>=0; i--) {
    FileWorst << i << std::endl;
}
FileWorst.close();
}
void SortedFileCreator(int T[],std::string FileName) {

std::ofstream f(FileName.c_str());
for(int i=0; i<N; i++) f << T[i] << std::endl;
f.close();
}

int FileToBoard(int T[], std::string FileName) {
std::fstream f;
f.open(FileName.c_str(), std::ios::in);
if(!f.good()) {std::cout<<"Nie udalo sie otworzyc"; exit(0);}
int i = 0;
while(f) {
    f >> T[i] ;
    i++;
}
f.close();
return *T;
}


int main()
{
    using namespace std;
clock_t start, stop;

double RandomMergeTime = 0, RandomInsertTime = 0;
double SortedMergeTime = 0, SortedInsertTime = 0;
double UnsortedMergeTime = 0, UnsortedInsertTime = 0;

RandomCaseFile(); //nazwa pliku: "random.txt"
int *MergeBoard = new int [N];
FileToBoard(MergeBoard, "random.txt");
start = clock();
MergeSort(MergeBoard,0,N-1);
stop = clock();
RandomMergeTime = (double)(stop - start) / CLOCKS_PER_SEC;
SortedFileCreator(MergeBoard, "merge_sorted_random.txt");
delete [] MergeBoard;

int *InsertBoard = new int [N];
RandomCaseFile();
FileToBoard(InsertBoard, "random.txt");
start = clock();
InsertSort(InsertBoard);
stop = clock();
RandomInsertTime = (double)(stop - start) / CLOCKS_PER_SEC;
SortedFileCreator(InsertBoard,"insert_sorted_random.txt");
delete [] InsertBoard;

SortedCaseFile(); //nazwa pliku: "sorted.txt"
int *MergeBoard2 = new int [N];
FileToBoard(MergeBoard2,"sorted.txt");
start = clock();
MergeSort(MergeBoard2,0,N-1);
stop = clock();
SortedMergeTime = (double)(stop - start)/CLOCKS_PER_SEC;
SortedFileCreator(MergeBoard2, "merge_sorted_sorted.txt");
delete [] MergeBoard2;

int *InsertBoard2 = new int [N];
SortedCaseFile();
FileToBoard(InsertBoard2, "sorted.txt");
start = clock();
InsertSort(InsertBoard2);
stop = clock();
SortedInsertTime = (double)(stop - start) / CLOCKS_PER_SEC;
SortedFileCreator(InsertBoard2,"insert_sorted_sorted.txt");
delete [] InsertBoard2;

UnsortedCaseFile(); //nazwa pliku: "unsorted.txt"
int *MergeBoard3 = new int [N];
FileToBoard(MergeBoard3,"unsorted.txt");
start = clock();
MergeSort(MergeBoard3,0,N-1);
stop = clock();
UnsortedMergeTime = (double)(stop - start)/CLOCKS_PER_SEC;
SortedFileCreator(MergeBoard3, "merge_sorted_unsorted.txt");
delete [] MergeBoard3;

int *InsertBoard3 = new int [N];
SortedCaseFile();
FileToBoard(InsertBoard3, "unsorted.txt");
start = clock();
InsertSort(InsertBoard3);
stop = clock();
UnsortedInsertTime = (double)(stop - start) / CLOCKS_PER_SEC;
SortedFileCreator(InsertBoard3,"insert_sorted_unsorted.txt");
delete [] InsertBoard3;

cout << "Czas sortowania przez scalanie (losowa kolejnosc): " << RandomMergeTime << "s" << endl;
cout << "Czas sortowania przez wstawianie(losowa kolejnosc): " << RandomInsertTime << "s" << endl;
cout << "Czas sortowania przez scalanie(najlepszy przypadek): " << SortedMergeTime << "s" << endl;
cout << "Czas sortowania przez wstawianie(najlepszy przypadek): " << SortedInsertTime << "s" << endl;
cout << "Czas sortowania przez scalanie(najgorszy przypadek): " << UnsortedMergeTime << "s" << endl;
cout << "Czas sortowania przez wstawianie(najgorszy przypadek): " << UnsortedInsertTime << "s" << endl;
}

 

komentarz 9 kwietnia 2018 przez j23 Mędrzec (194,920 p.)

Po co dla każdego testu przydzielasz nową pamięć, skoro jej rozmiar jest za każdym razem stały (N)?

 

void Scalaj(int T[], int p, int mid, int k)
{
      int T2[N];
      ...  

Duża tablica lokalna + rekurencja to ryzykowne połączenie. Aplikacja jest jednowątkowa, zatem możesz dać static int T2[N];

1 odpowiedź

0 głosów
odpowiedź 8 kwietnia 2018 przez RafalS VIP (122,820 p.)
Po pierwsze - sugeruje następnym razem poszukać choć odrobinę błędu samemu chociażby głupim komentowaniem kodu, żeby sprawdzić co wysypuje program a nie wrzucać 200 linijek, których nikomu się nie chce czytać.

Klasyczna korupcja sterty - wychodzisz poza tablice, MSVC (kompilator visual studio C++) to łyknął, ale przy próbie zwolnienia pamięci delete[] wywalał błąd.
Funkcja FileToBoard w pętli while(f) czytała N + 2 liczb, a tablice miałeś na N. Bardzo nie polecam takiej metody wczytywania danych z pliku do tablicy, bo jest totalnie nieodporna na błędy. Miałeś tablicę na 50 liczb, to trzeba było wczytać 50 liczb a nie while(f). W pliku unsorted.txt są liczby 0-N włącznie czyli N + 1 liczb + pusta linia.

Podobne pytania

0 głosów
1 odpowiedź 206 wizyt
+1 głos
0 odpowiedzi 1,174 wizyt
pytanie zadane 20 kwietnia 2016 w C i C++ przez nodo12221 Obywatel (1,100 p.)
0 głosów
0 odpowiedzi 278 wizyt

92,578 zapytań

141,426 odpowiedzi

319,653 komentarzy

61,961 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...