Tehnici de sortare

Cerința

Completezi patru funcții în fișierul solutie.c. Fiecare primește un tablou v de n evenimente și trebuie să-l lase sortat pe loc, după regula ei:

Ce sortezi: structura Eveniment

Toate cele patru funcții sortează același tip de date, definit în sortlab.h — 16 octeți pe eveniment.

typedef struct {
    uint32_t id;          /* identificator unic          */
    uint32_t timestamp;   /* secunde Unix (UTC)          */
    uint32_t ip;          /* IPv4 sursă, ca număr        */
    uint16_t port;        /* portul destinație           */
    uint8_t  severitate;  /* 0 (informativ) … 9 (critic) */
    uint8_t  categorie;   /* tipul evenimentului, 0..15  */
} Eveniment;

void sorteaza_loguri(Eveniment *v, size_t n);

Sortezi evenimente întregi: când muți unul, se mută cu toate câmpurile lui. Algoritmii îi scrii tu — fără qsort sau alte sortări din biblioteci; poți folosi malloc/free și orice funcții ajutătoare. În exemplele de mai jos, timestamp-urile sunt scurtate, ca să se citească ușor.

Cum lucrezi

1. Descarcă și dezarhivează kitul

   Din browser — sortlab.zip — sau din terminal:

   curl -O /kit/sortlab.zip
   unzip sortlab.zip
   cd sortlab

   solutie.c	aici scrii tu — cele patru funcții, marcate cu TODO
   sortlab.h	restul programului: descărcarea testelor, cronometrul, verificarea, trimiterea, main. Nu-l modifica.
   README.md	pe scurt, ce e pe pagina asta

2. Scrie funcțiile în solutie.c

   Completezi corpul celor patru funcții. Funcțiile ajutătoare (comparatoare, interschimbări…) le scrii deasupra lor, în același fișier, și le poți folosi la mai multe cerințe. Nu scrie main — e deja în sortlab.h.

   #include "sortlab.h"
   
   void sorteaza_loguri(Eveniment *v, size_t n) {
       /* TODO: v[0..n-1] crescător după timestamp */
   }

3. Compilează

   gcc -O2 solutie.c -o lab

   -O2 contează: fără el timpii ies de câteva ori mai mari, iar programul te avertizează.

4. Verifică local, fără server

   ./lab --local --n 20              # toate cerințele, 20 de evenimente aleatoare
   ./lab --local --cerinta 2         # doar cerința 2, cu 100.000 de evenimente

   Nimic nu pleacă la server. Dacă rezultatul e greșit, programul îți arată primul eveniment pus greșit și regula pe care o încalcă.

5. Rulează pe server și intră în clasament

   ./lab "Numele Tău"                # toate cele 4 cerințe × 5 teste
   ./lab "Numele Tău" --cerinta 2    # doar cerința 2
   ./lab "Numele Tău" --cerinta 2 --test lyra

   Numele îl alegi tu. Programul descarcă fiecare test, îți apelează funcția, cronometrează doar apelul ei și trimite rezultatul. Arată cam așa:

   Cerința 2 — Alertele, pe severitate: sorteaza_alerte().
   Regula: severitate descrescător, stabil.
     test cygnus
           descărcat 1.0 MB comprimat în 0.4 s (nu intră în timp)
           sortez 100000 evenimente cu sorteaza_alerte()...  (blocat? Ctrl+C)
           [ OK ]  4.812 ms — Corect, în 4.812 ms.  (locul 3 în clasament)
     test draco
           ...

6. Citește rezultatul și reia

   [ OK ]	sortat corect, în limita de timp
   [GREȘIT]	nu respectă regula — programul îți spune primul eveniment greșit
   [TIMP DEPĂȘIT]	corect, dar peste limita de timp
   [EXPIRAT]	rezultatul n-a mai ajuns: programul a crăpat (Segmentation fault) sau l-ai oprit

   Dacă o sortare se blochează, oprește-o cu Ctrl+C — serverul marchează singur testul. Apoi modifici, recompilezi și rulezi din nou: în clasament contează cea mai bună rulare pe fiecare cerință.

Cum se evaluează

API

Kitul face exact cererile de mai jos, prin curl. Le poți repeta de mână, dintr-un alt limbaj sau dintr-un script. Erorile vin ca {"eroare": "…"} cu status 4xx.

curl -X POST /api/rulari \
     -H 'Content-Type: application/json' \
     -d '{"utilizator": "Ion P.", "cerinta": "prioritati"}'

→ 201 {"rulare": "9f2c41…", "teste": ["cygnus", "draco", "lyra", "orion", "vega"],
       "regula": "severitate-,timestamp+", "stabil": false, "n": 100000, "limita_ms": 400, …}

curl --compressed -o date.bin /api/rulari/9f2c41…/lyra

SORTLAB3 prioritati lyra 100000 400\n      ← magic, cerință, test, n, limita_ms
id:         n octeți 0 · n octeți 1 · n octeți 2 · n octeți 3
timestamp:  n octeți 0 · … · n octeți 3
ip:         n octeți 0 · … · n octeți 3
port:       n octeți 0 · n octeți 1
severitate: n octeți
categorie:  n octeți                        ← în total 16 · n octeți

curl -X POST /api/rulari/9f2c41…/lyra \
     -H 'Content-Type: application/json' \
     -d '{"hash": "00c3f1a29b7e4d10", "timp_ms": 84.512}'

→ 200 {"status": "acceptat", "mesaj": "Corect, în 84.512 ms.", "loc": 3, "rezolvate": 1, "total": 5}

/* cerința 3: cheile sunt severitate, apoi timestamp */
uint64_t h = 0;
for (size_t i = 0; i < n; ++i) {
    h = h * 1000003ULL + v[i].severitate + 1;
    h = h * 1000003ULL + v[i].timestamp + 1;
}
h ^= amprenta(v, n);                /* Σ mix64(eveniment), modulo 2^64 */
printf("%016llx", (unsigned long long)h);