Subset maxim

[•freak93]

Si eu am incercat si am ajuns la aceeasi concluzie. std::sort chiar se comporta la fel de bine, chiar mai bine uneori.

[•blasterz]

Hmm, cred ca am incercat radix sort pentru suffix arrays si tin minte ca std::sort() mergea mai repede. (http://infoarena.ro/siruri-de-sufixe) Ar trebui sa incerc din nou.

La suffix arrays foloseam o combinatie de radix cu stl::sort, si anume sortam cu radix dupa prima valoare si apoi sortam cu sort dupa a 2a.
Stiu ca in felul asta obtineam timpi semnificativi mai buni decat daca as fi folosit doar una din metode.
http://infoarena.ro/job_detail/285375?action=view-source

[•rgrig]

La mine pe calculator asta văd:

      size  std::sort     rsort0     rsort1     rsort2     rsort3     rsort4
       100      0.000    x13.500     x7.000     x6.500    x55.500  x7996.250
      1000      0.000    x55.778     x4.417     x2.306     x4.889  x1649.028
     10000      0.000    x10.685     x3.476     x1.813     x1.121   x116.789
    100000      0.006     x5.298     x2.667     x1.344     x0.734    x10.838
   1000000      0.067     x4.733     x2.393     x1.223     x0.667     x2.037
  10000000      0.753     x4.668     x2.360     x1.205     x0.645     x1.247
 100000000      8.600     x4.269     x2.163     x1.112     x0.598     x1.150


Adică radix sort merge mai repede dacă grupează pe octeți (rsort3 înseamnă că grupează câte 2³ biți) și vectorul are peste 10⁵ elemente. (Dar nu așa de repede cum am zis mai devreme.)

Am generat vectorul cu rand() și am compilat cu -O3, g++-4.4.

[•claudiumihail]

@Mihai Patrascu

Super explicatia! (recunosc am recitit-o de cateva ori pana s-o inteleg cat de cat calumea). Am cam aberat grav la complexitate, heh. De acum inainte o sa las comentariile despre teoria fundamentala in informatica in mainile celor care se pricep.

[•Opportunity]

putem deodata de la citire sa il sortam

Cod:

for i:=1 to n do begin
read(k); a[k]:=k end;

[•rgrig]

putem deodata de la citire sa il sortam

Counting sort a fost deja mentionat.