028 Sortare prin comparare

[•AlexandruValeanu]

Nu neaparat...gandeste-te ca pe un sir aproape sortat MergeSort-ul e O(NlogN) pe cand BubbleSort-ul e aprope liniar....Nu exista un cel mai bun algoritm de sortare ...toate au cazuri particulare pe care nu sunt cele mai bune

PS: MergeSort-ul este sigur O(NlogN) pe orice tip de sir asa ca da...e destul de bun

[•reking]

Mersi ca m-ai luminat! ^_^
 

[•rares96cheseli]

Din cate stiu eu, BubbleSort-ul are complexitate n^2. Are complexitate liniara doar cand sirul este deja sortat.

[•PlayLikeNeverB4]

Acelasi lucru l-a zis si Alexandru 

[•rares96cheseli]

Greseala mea  . Nu citisem partea aia 

[•contnou]

A reusit cineva sa ia 100 cu un quick sort cu pivot random implementat de mana?

[•Djok]

adaugă

Cod:

ios_base::sync_with_stdio(0);

în funcția main
ar trebui să ei 100.

[•AlexandruValeanu]

@contnou Vezi ca nu ai chiar pivot random.
Pentru a folosi rand() ar trebui sa ai si srand(time(...)) pe undeva prin cod.

[•contnou]

http://www.infoarena.ro/job_detail/1712585?action=view-source

Am ascultat sfaturile voastre si nu reusesc sa iau 100.

A reusit cineva sa ia 100 cu un quick sort cu pivot random implementat de mana?

[•Bodo171]

La problema asta nu ar trebui sa fie acces liber la surse?E singura din arhiva educationala la care nu sunt sursele vizibile pentru toata lumea

[•sulzandrei]

Am 3 surse cu arbori care pica din cauza memoriei prea mici(au nevoie de aprox 12mb) , oare se poate modifica limita de memorie ca sa se accepte si solutii cu arbori?

[•fluture.godlike]

Salut, a bagat cineva problema asta cu Shell Sort? Daca da, cu ce valori de gap?
Eu am incercat cu {701, 301, 132, 57, 23, 10, 4, 1} si iau TLE
Multumesc anticipat!

[•AlexandruValeanu]

Eu am luat punctaje foarte variate cu Shellsort (de la 40p pana la 100p).
100p : http://www.infoarena.ro/job_detail/1477734  | Gaps : 1, 9, 34, 182, 836, 4025, 19001, 90358, 428481
100p : http://www.infoarena.ro/job_detail/1477742  | Gaps : 1, 2, 4, 8, 21, 56, 149, 404, 1098, 2982, 8104, 22027, 59875, 162756, 442414

N.B. Ar trebui sa nu se poata lua 100p cu Shellsort, dar este destul de greu de facut teste pentru toate secvențele 'celebre'.

[•fluture.godlike]

Multumesc pentru ajutor !