Sortowanie cpp
Ostatnio zmodyfikowano 2015-11-18 10:56
krzychumg Temat założony przez niniejszego użytkownika |
Sortowanie cpp » 2015-11-17 23:41:20 #include<iostream> #include<ctime> #include<cstdlib> #include<math.h> using namespace std; void QUICKSORT( int tab[], int left, int right ) { int i = left; int j = right; int x = tab[( left + right ) / 2 ]; do { while( tab[ i ] < x ) i++; while( tab[ j ] > x ) j--; if( i <= j ) { swap( tab[ i ], tab[ j ] ); i++; j--; } } while( i <= j ); if( left < j ) QUICKSORT( tab, left, j ); if( right > i ) QUICKSORT( tab, i, right ); } void BUBBLESORT( int tab[], int size ) { for( int i = 0; i < size; i++ ) { for( int j = 0; j < size - 1; j++ ) { if( tab[ j ] > tab[ j + 1 ] ) swap( tab[ j ], tab[ j + 1 ] ); } } } int main() { clock_t start, stop; double czas; int rozmiar, x; cout.precision( 2 ); for( int rodzaj = 0; rodzaj < 3; rodzaj++ ) { for( int i = 0; i < 7; i++ ) { rozmiar = int( pow( 10, i + 1 ) ); int A[ rozmiar ]; switch( rodzaj ) { case 0: for( int j = 0; j < rozmiar; j++ ) { A[ j ] =( j + 1 ); } break; case 1: for( int j = 0; j < rozmiar; j++ ) { x = rand() % 100 + 1; A[ j ] = x; } break; case 2: for( int j = 0; j < rozmiar; j++ ) { A[ j ] = rozmiar - j; } break; } if( i == 0 ) { cout << endl; for( int j = 0; j < 10; j++ ) { cout << A[ j ] << " "; } } start = clock(); QUICKSORT( A, 0, rozmiar ); stop = clock(); czas =( stop - start ) /( double ) CLOCKS_PER_SEC; switch( rodzaj ) { case 0: cout << endl << "Czas QUICK-SORT dla tablicy posortowanej niemalejaco 10^" << i + 1 << ": " << fixed << czas << "."; break; case 1: cout << endl << "Czas QUICK-SORT dla tablicy posortowanej losowo 10^" << i + 1 << ": " << fixed << czas << "."; break; case 2: cout << endl << "Czas QUICK-SORT dla tablicy posortowanej nierosnaco 10^" << i + 1 << ": " << fixed << czas << "."; break; } if( i == 0 ) { cout << endl; for( int j = 0; j < 10; j++ ) { cout << A[ j ] << " "; } } if( i < 4 ) { switch( rodzaj ) { case 0: for( int j = 0; j < rozmiar; j++ ) { A[ j ] =( j + 1 ); } break; case 1: for( int j = 0; j < rozmiar; j++ ) { x = rand() % 100 + 1; A[ j ] = x; } break; case 2: for( int j = 0; j < rozmiar; j++ ) { A[ j ] = rozmiar - j; } break; } start = clock(); BUBBLESORT( A, rozmiar ); stop = clock(); czas =( stop - start ) /( double ) CLOCKS_PER_SEC; switch( rodzaj ) { case 0: cout << endl << "Czas BUBBLE-SORT dla tablicy posortowanej niemalejaco 10^" << i + 1 << ": " << fixed << czas << "."; break; case 1: cout << endl << "Czas BUBBLE-SORT dla tablicy posortowanej losowo 10^" << i + 1 << ": " << fixed << czas << "."; break; case 2: cout << endl << "Czas BUBBLE-SORT dla tablicy posortowanej nierosnaco 10^" << i + 1 << ": " << fixed << czas << "."; break; } } } } return 0; } Problem polega na tym, że program wywala po przesortowaniu tablicy o wielkości 10^5. Jest ktoś w stanie pomóc? edit: Proszę o przeniesienie, niechcący założyłem temat w złym dziale. |
|
carlosmay |
» 2015-11-18 00:24:17 Jeśli dla mniejszych tablic działa prawidłowo, to może być przepełnienie stosu. |
|
elradziu |
» 2015-11-18 10:56:48 Kiedyś bawiłem się coś z tablicami. Też program się wysypywał przy dużych tablicach. I z tego co pamiętam rozwiązaniem było dynamiczne zarządzanie pamięcią (operatory new i delete). Spróbuj tego i daj znać czy dało radę :) |
|
« 1 » |