Mierzenie czasu algorytmów sortowania

Hej mam za zadanie zmierzyć czas wykonywania algorytmów sortowania takich jak quick sort i bubble sort zmierzyć ich czas a potem na podstawie tego wykres. Napisany przeze mnie program działa, ale czas w którym podobno się algorytm quick sort wykonuje jest po mojemu aż za krótki. Czas dla 200000 elementów to 32 dla quick sorta, zaś bąbelkowe to ponad 140 000. Odpalałem to na linuxie i różnice były duże ale nie aż tak. Teraz nie będę miał niestety dostępu do tego komputera a muszę to skończyć na windowsie. Na takich czasach co pokazuje to nie ma nawet jak tego na sekundy zamienić.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
const int n=200000;

void wypelnij(int tab[]);
void bubble(int tab2[],int n);
void Sortuj_szybko(int lewy, int prawy,int tab[]);
int main()
{
    int tab[200000];//zmiennne
    int tab2[200000];//
    clock_t start;//
    clock_t end;//
    clock_t start2;//
    clock_t end2;//

    wypelnij(tab);//zapelnia tablice liczbami pseudolosowymi
    wypelnij(tab2);

    start=clock ();
    Sortuj_szybko(0,n-1,tab);
    end=clock();
    start2=clock ();
    bubble(tab2,n);
    end2=clock();

    printf("czas szybkiego %ld",(end-start));
    printf("czas babelkowoego %ld",(end2-start2));

    return (0);
}

To pokazuj w milisekundach :P

Zlozonosc bubble to O(n) = n^2, a quicksorta to O(n)=log_2(n), więc róznica ogromna.

Tak btw. to czy Ty przypadkiem nie testujesz ich na 2 róznych tablicach?

Pomyłka wcześniej w main'ie to zapełniałem forami a teraz funkcję dałem bez sensu. Ale to nie zmieni wiele. Wcześniej było na tych samych tablicach i też quick 32 a bubble 140 000. A quick sort to raczej jest n*log2 n ? Czyli wolniej jak n^2 sporo ale nie powinno być aż tak.

No masz racje, quick to O(n)=nlog_2(n) (pomylka ;D).
Ale wciąż jest to o wiele szybciej niż bubble.

Dla n=200000.
Zlozonosc quicksorta = 200000*log_2(200000) = 3.5 * 10^6
Zlozonosc bubble = 200000^{2 = 4 * 10}10

Zobacz sobie np. tutaj porownanie czasow -> http://ddeville.me/2010/10/sorting-algorithms-comparison/

Dzięki wielkie czyli chociaż to jest ok :) Zerknął byś jeszcze na to ? Ma zapisywać czasy po prostu do pliku ale po wypisaniu jednego czasu w konsoli przestaje działać i tworzy pusty plik. Nie wiem co czynię źle, ale zawsze bez problemu zapisywałem do plików :/
Edit : lamersko strasznie mam już, omyłkowo dałem podwójny nawias :)

int main()
{
    int n=1000;
    FILE *plik;
    plik=fopen("data.txt","w");
    if(plik==NULL)
        {
        return -2;
        }
    int i=0;
    for(i=0;i<100;i++)
    {
    int tab[n];//zmiennne
    int tab2[n];//
    clock_t start;//
    clock_t end;//
    clock_t start2;//
    clock_t end2;//
    wypelnij(tab,tab2,n);//zapelnia tablice liczbami pseudolosowymi
    // start=clock ();
    //Sortuj_szybko(0,n-1,tab);
    //end=clock();
    start2=clock ();
    bubble(tab2,n);
    end2=clock();
    float pom=1000*(end2-start2)/CLOCKS_PER_SEC;//mierzymy w ms
    printf("liczba elementow: %d czas babelkowoego %f ms\n",n,pom);
    fprintf(plik, "%d \t", n);////po dodaniu program sie kompiluje ale przestaje dzialac po wypisaniu jedego printfa 
    fprintf(plik, "%f \n", pom);
    n=n+100;
    }

    fclose(plik);
    return (0);
}

tak już trochę poza tematem znasz może program który wczytuje z pliku txt dane i potem robi z tego wykres ? Bo chciałem zobrazować to co mi wyszło. Ale nie Excel :D

http://dplot.en.softonic.com/

Dobra oczywiscie kolejne problemy przede mną :D
Chcę posortować tablicę 1000000 heapsortem i quicksortem, zaczynam od mniejszej w miarę jak zwiększam rozmiar tablicy w pewnym momencie przestaje działać, tablica ma wtedy chyba coś ponad 300 000 pozycji. Domyślam się że to jest problem z pamięcią a raczej jej brakiem, po użyciu tablicy powinienem ją zwolnić ? Tylko jak ?

{

        int i=0;
        for(i=0;i<2;i++)
        {
        //
        float suma_quick=0;
        float suma_heap=0;
        int j=0;
        for(j=0;j<5;j++)
        {


            int tab_quick[n];//
            int tab_heap[n];

            clock_t start_quick;//
            clock_t end_quick;//
            clock_t start_heap;//
            clock_t end_heap;//

            int j=0;
            for(j=0;j<n;j++)//wypelnianie pseudolosowymi liczbami
            {
            tab_quick[j]=rand();
            tab_heap[j]=tab_quick[j];
            }



            start_quick=clock ();
            Sortuj_szybko(0,n-1,tab_quick,n);
            end_quick=clock();

            start_heap=clock ();
            heapsort(tab_heap,n);
            end_heap=clock();

            float quick_time=1000*(end_quick-start_quick)/CLOCKS_PER_SEC;//
            float heap_time=1000*(end_heap-start_heap)/CLOCKS_PER_SEC;//
            suma_quick=suma_quick+quick_time;
            suma_heap=suma_heap+heap_time;
            //free(tab_quick);
            //free(tab_heap);

        }



        float av_time_quick=suma_quick/5.0;
        float av_time_heap=suma_heap/5.0;

        fprintf(plik2, "%d ", n);
        fprintf(plik2, "%f \n", av_time_quick);
        fprintf(plik3, "%d ", n);
        fprintf(plik3, "%f \n", av_time_heap);
        printf("%d %%\n",2*(i+1));
        n=n+300000;

    }



    }


    fclose(plik1);
    fclose(plik2);
    fclose(plik3);
    return (0);

Edit : jednak mam :) zrobiłem dynamicznie i przydzieliłem malloc'iem i trybi :)