SDA Tema 1

Cerințe

1. Realizați o implementare a algoritmului Bubble-sort în limbajul C, pentru valori de tip float, cu datele de intrare citite din fișier.
2. Realizați o funcție care să genereze o secvență de n numere aleatoare de tip float și să le scrie într-un fișier care poate fi citit de programul de la punctul 1.
3. Utilizați funcțiile anterioare pentru a măsura timpul de sortare pentru fișiere de dimensiuni variabile (porniți de la 1000 de numere până la 25000 de numere cu increment de 1000).
4. Realizați un grafic al timpului de execuție raportat la numărul de valori de intrare, și determinați exeprimental funcția de complexitate în timp (notație big O).

Observații

• Formatul fișierului de intrare (respectiv al fișierului scris de funcția de la punctul 2) este:

n

v₀ v₁ v₂ ... v_n-1

unde n este numărul de valori, iar v este un vector de numere fracționare.

• Pentru generare de numere aleatoare, puteți folosi funcția rand().
• Pentru a măsura timpul de execuție pentru o funcție, puteți folosi funcția clock(). Orice altă soluție de măsurare este acceptată.

#include <time.h>
#include <stdio.h>

void measure(){
    clock_t begin, end;
    double time_spent;

    begin = clock();
    function_to_measure();
    end = clock();
    time_spent_in_milliseconds = (double)(end - begin) * 1000.0 / CLOCKS_PER_SEC;
    printf("Function function_to_measure took %lf milliseconds.\n", time_spent_in_milliseconds);
}

Livrabile

Tema submisă va conține: unul sau mai multe fișiere .cpp/.c/.h care să fie compilabile pe cel puțin o platformă (sistem de operare + compilator), și un document pdf care să conțină: rezultatele obținute (milisecunde pentru fiecare fișier de intrare și dimensiunea fișierelor), graficul cu timpul de rulare în funcție de cantitatea de date de intrare, împreună cu funcția de aproximare și coeficientul de precizie (R²), concluziile trase din experiment, configurația computerului (procesor, frecvență, memorie RAM și sistem de operare) și compilatorul folosit.

Modalitatea de submitere

Tema va fi submisă pe e-mail, la adresa homework@dcae.pub.ro. Subiectul va fi [SDA-1][NUME][GRUPA]. Fișierele vor fi atașate mesajului, NEARHIVATE.

Atenție: Singurul fișier binar va fi documentul pdf. Orice alt binar (executabil, dll, so, etc.) atașat mesajului va face ca acesta să fie respins de server-ul de e-mail și în consecintă să nu primiți nici un punct pe temă.

Atenție: Temele vor fi verificate anti-plagiat cu soft-uri specializate. Orice temă copiată va fi penalizată (atât sursa cât și copia) cu 100% din punctaj, fără posibilitate de refacere.