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

Porównanie metod sortowania liniowego

Ostatnio zmodyfikowano 2016-12-16 18:04
Autor Wiadomość
Janusz11
Temat założony przez niniejszego użytkownika
Porównanie metod sortowania liniowego
» 2016-12-16 16:24:23
Witam. Dlaczego gdy odpalam program w takiej formie czas przy sortowaniu przez wstawianie wynosi 0, a kiedy wykomentuję inne sortowania w funkcji main to normalnie wyświetla około 80 cykli? Głowię się już nad tym pewien czas i się poddaję. Z góry dzięki za pomoc :)

C/C++
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int n = 10000;

void losuj( int t[], int n )
{
    for( int i = 0; i < n; i++ )
         t[ i ] = rand() % 9999;
   
}

void wypisz( int t[], int n )
{
    for( int i = 0; i < n; i++ )
         cout << t[ i ] << " ";
   
}

void babelkowe( int t[], int n )
{
    for( int j = 0; j < n - 1; j++ )
    for( int i = 0; i < n - 1; i++ )
    {
        if( t[ i ] > t[ i + 1 ] )
        {
            int tmp = t[ i ];
            t[ i ] = t[ i + 1 ];
            t[ i + 1 ] = tmp;
        }
    }
}

void babelkowe_ulepszone( int t[], int n )
{
    for( int j = 0; j < n - 1; j++ )
    for( int i = 0; i < n - 1 - j; i++ )
    {
        if( t[ i ] > t[ i + 1 ] )
        {
            int tmp = t[ i ];
            t[ i ] = t[ i + 1 ];
            t[ i + 1 ] = tmp;
        }
    }
}

void wybieranie( int t[], int n )
{
    int tmp, k;
    for( int i = 0; i < n; i++ )
    {
        k = i;
        for( int j = i + 1; j < n; j++ )
        if( t[ j ] < t[ k ] )
             k = j;
       
        tmp = t[ k ];
        t[ k ] = t[ i ];
        t[ i ] = tmp;
    }
}

void wstawianie( int t[], int n )
{
    int i, k, elem;
    for( i = 1; i < n; i++ )
    {
        elem = t[ i ];
        k = i - 1;
        while( k >= 0 && t[ k ] > elem )
        {
            t[ k + 1 ] = t[ k ];
            --k;
        }
        t[ k + 1 ] = elem;
    }
}

void zliczanie( int t[], int n )
{
    int m = 0, i;
    for( i = 0; i < n; i++ )
    if( m < t[ i ] )
         m = t[ i ];
   
    int P[ m + 1 ] = { 0 };
    for( int i = 0; i < n; i++ )
         P[ t[ i ] ] ++;
   
    int k = 0;
    for( int i = 0; i <= m; i++ )
    for( int j = P[ i ]; j >= 1; j-- )
    {
        t[ k ] = i;
        k++;
    }
}


int main()
{
    srand( time( NULL ) );
    double start, stop, czas;
    int t[ 10000 ], T[ 10000 ];
    losuj( t, n );
   
    cout << "Sortowanie babelkowe:" << endl;
    for( int i = 0; i < n; i++ )
         T[ i ] = t[ i ];
   
    start = clock();
    babelkowe( t, n );
    stop = clock();
    czas =( stop - start ); //CLOCKS_PER_SEC;
    cout << czas << endl;
   
    cout << "Sortowanie babelkowe ulepszone:" << endl;
    for( int i = 0; i < n; i++ )
         T[ i ] = t[ i ];
   
    start = clock();
    babelkowe_ulepszone( t, n );
    stop = clock();
    czas =( stop - start ); //CLOCKS_PER_SEC;
    cout << czas << endl;
   
    cout << "Sortowanie przez wybieranie:" << endl;
    for( int i = 0; i < n; i++ )
         T[ i ] = t[ i ];
   
    start = clock();
    wybieranie( t, n );
    stop = clock();
    czas =( stop - start ); //CLOCKS_PER_SEC;
    cout << czas << endl;
   
    cout << "Sortowanie przez wstawianie:" << endl;
    for( int i = 0; i < n; i++ )
         T[ i ] = t[ i ];
   
    start = clock();
    wstawianie( t, n );
    stop = clock();
    czas =( stop - start ); //CLOCKS_PER_SEC;
    cout << czas << endl;
   
    cout << "Sortowanie przez zliczanie:" << endl;
    for( int i = 0; i < n; i++ )
         T[ i ] = t[ i ];
   
    start = clock();
    zliczanie( t, n );
    stop = clock();
    czas =( stop - start ); //CLOCKS_PER_SEC;
    cout << czas << endl;
   
    return 0;
}
P-155050
czaffik
» 2016-12-16 16:57:35
Ponieważ tablica została już posortowana, jak zakomentujesz inne wywołania sortowań do funkcji sortującej przez wstawianie trafia nieposortowana tablica i czas jej wykonania się wydłuża. Pewno myślałeś że funkcja sortująca nie zmodyfikuje tablicy z funkcji głównej?
U mnie np wyszło że czas sortowania tym algorytmem nieposortowanej tablicy wynosi ok 140 a posortowanej 0.
Dla porównania czas sortowania metodą bąbelkową nieposortowanej tablicy to 700, natomiast posortowanej spada do 400.
Po co ci tablica T i przepisywanie do niej wartości z tablicy t?
P-155051
mateczek
» 2016-12-16 17:07:47
Po prostu do funkcji powinien wysłać "T" a nie "t"
P-155053
Janusz11
Temat założony przez niniejszego użytkownika
» 2016-12-16 17:09:30
Tablica "t" jest to pierwotna tablica, w której zostały wylosowane liczby. Przed każdym wywołaniem funkcji sortującej przepisuje liczby z tablicy "t" do "T", aby liczby były nieposortowane. W wyżej przywołanych tablicach ta metoda się sprawdza, a na sortowaniu przez wstawianie przestaje spełniać swoją funkcję.
P-155054
Janusz11
Temat założony przez niniejszego użytkownika
» 2016-12-16 17:11:19
W którym miejscu mam to zmienić?
P-155055
czaffik
» 2016-12-16 17:18:52
Po prostu powinieneś wysyłać do funkcji sortujących T a nie t, czyli zamiast np:
C/C++
wstawianie( t, n );
zrobić to:
C/C++
wstawianie( T, n );
i tak dla każdego wywołania funkcji sortującej.
P-155056
mateczek
» 2016-12-16 17:22:12
W którym miejscu mam to zmienić?

zbijasz się ?? po odpowiedzi "Czaffika" myślałem, że zwyczajnie literówka w kodzie i posyłasz nie te tablicę do sortowania przez pomyłkę :P
P-155057
Janusz11
Temat założony przez niniejszego użytkownika
» 2016-12-16 18:04:24
Dobra, czaję :P
Nie zauważyłem tak prostego błędu. Dzięki :>
P-155058
« 1 »
  Strona 1 z 1