Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Sortowanie cpp

Ostatnio zmodyfikowano 2015-11-18 10:56
Autor Wiadomość
krzychumg
Temat założony przez niniejszego użytkownika
Sortowanie cpp
» 2015-11-17 23:41:20
C/C++
#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: //WYPELNIANIE TABLICY NIEMALEJACO
                for( int j = 0; j < rozmiar; j++ )
                {
                    A[ j ] =( j + 1 );
                }
                break;
            case 1: //WYPELNIANIE TABLICY LOSOWO
                for( int j = 0; j < rozmiar; j++ )
                {
                    x = rand() % 100 + 1;
                    A[ j ] = x;
                }
                break;
            case 2: //WYPELNIANIE TABLICY NIEROSNACO
                for( int j = 0; j < rozmiar; j++ )
                {
                    A[ j ] = rozmiar - j;
                }
                break;
            }
            //WYPISANIE PRZED SORTOWANIEM
            if( i == 0 )
            {
                cout << endl;
                for( int j = 0; j < 10; j++ )
                {
                    cout << A[ j ] << " ";
                }
            }
            //QUICKSORT
            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;
            }
            //WYPISANIE PO SORTOWANU
            if( i == 0 )
            {
                cout << endl;
                for( int j = 0; j < 10; j++ )
                {
                    cout << A[ j ] << " ";
                }
            }
            if( i < 4 )
            {
                switch( rodzaj )
                {
                case 0: //WYPELNIANIE TABLICY NIEMALEJACO
                    for( int j = 0; j < rozmiar; j++ )
                    {
                        A[ j ] =( j + 1 );
                    }
                    break;
                case 1: //WYPELNIANIE TABLICY LOSOWO
                    for( int j = 0; j < rozmiar; j++ )
                    {
                        x = rand() % 100 + 1;
                        A[ j ] = x;
                    }
                    break;
                case 2: //WYPELNIANIE TABLICY NIEROSNACO
                    for( int j = 0; j < rozmiar; j++ )
                    {
                        A[ j ] = rozmiar - j;
                    }
                    break;
                }
                //BUBBLESORT
                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.
P-140324
carlosmay
» 2015-11-18 00:24:17
Jeśli dla mniejszych tablic działa prawidłowo, to może być przepełnienie stosu.
P-140326
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ę :)
P-140331
« 1 »
  Strona 1 z 1