tömb rendezés + összehasonlítások száma

2009.12.05. 10:18 stack

Az elmúlt hetekben több helyen is találkoztam ehhez hasonló mintakóddal, mivel az eredményeken jót mosolyogtam, gondoltam én is kiteszem. Nagy jelentősége persze nincsen, csupán érdekesség.

Adott egy 1000 elemű tömb, benne az elemek növekvő sorrendben. Vajon az egyes böngészők hány összehasonlítást használnak rendezés közben?

var list = [];
for (var i = 0; i < 1000; i++) {
    list.push(i);
}
var count = 0;

list.sort(function(a, b){
    ++count;
    if (a < b) {
        return -1;
    }
    if (a > b) {
        return 1;
    }
    return 0;
});

alert(count);

Az eredmények:

Firefox: 999 (n-1, ennél kevesebb vizsgálattal elméletileg sem lehetne)
Opera: 7498
Safari: 8977
Chrome: ~10000 (nem determinisztikus az eredmény, plusz-mínusz ezer)
IE: 17583

Kísérletképpen megnézhető még az is, hogy mi van, ha a tömbben minden elem egyenlő: list.push(1);
Chrome nulla lépéssel megoldotta mindezt. Na, ezzel nehéz versenyezni. :) Opera viszont majdnem hozta a buborékrendezésnél használt értéket a 499485 összehasonlítással. Buborékrendezés: (n-1)*n/2.

Végül, ha fordított a sorrend: list.push(1000-i); Firefox: 5681, Opera: 8550, Safari 8977, Chrome: ~11000 végül IE 15965

Szólj hozzá!

Címkék: sort array nem extjs

A bejegyzés trackback címe:

https://extjs.blog.hu/api/trackback/id/tr151575432

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Nincsenek hozzászólások.

ExtJS blog, mi ez?

Az ExtJS egy JavaScript keretrendszer, melyet a blog írója elfogultan a legjobbnak tart, és ez a blog olyan apróságok gyűjteménye, melyek ExtJS használata közben felmerültek, eszébe jutottak...

Címkék

ajax (4) alignto (1) állás (3) analytics (1) anchorto (1) android (4) animate (2) array (9) auto (1) back button (1) beautifier (1) beforeevent (1) benchmark (1) blur (1) budapest.js (1) button (1) canvas (1) capture (1) case sensitive (1) center (1) change (1) cikkajánló (1) class (2) closure compiler (1) collapse (1) combobox (3) comment (1) console.log (2) contextmenu (2) core (2) count (1) css (15) csv (1) dataview (1) date (4) datefield (3) datepicker (1) debug (1) doksi (1) dragdrop (1) easing (1) eclipse (1) editor (1) element (5) error (5) eval (2) event (1) fejtörő (1) field (2) fieldset (1) filter (1) firefox (4) firefox extension (2) focus (3) fonts (1) fun (1) function (1) google (2) google chrome (1) grayscale (1) grid (4) group contact (1) header (3) height (2) hidden (1) hirek (2) history (1) htaccess (1) html5 (2) htmleditor (2) https (1) icon (3) id (2) ie (2) ie6 (1) ie9 (1) iframe (3) image (2) indexof (1) javascript (1) jquery (2) jslint (2) jsmin (1) json (7) keymap (1) kipróbálom (2) könyvajánló (2) label (1) layout (1) lint (1) log (1) loop (1) magyar (2) mandelbrot (1) mask (1) math (1) maxlength (1) mistake (1) mysql (5) napi szívás (16) nem extjs (12) node (1) nth child (1) number (1) off (5) offline (1) operator (1) override (20) pagesize (1) paging (2) panel (2) php (7) picker (1) plugin (3) pozicionálás (2) preload (1) print (1) propertygrid (1) pseudo (3) readonly (2) record (1) regexp (1) replace (1) resizable (1) rotate (1) round (1) scale (1) sencha touch (2) server (1) shuffle (1) slider (1) sort (3) sortable (1) store (2) string (7) sum (1) tabchange (1) tabpanel (1) tab key (2) tdd (1) template (1) textarea (2) textfield (1) textitem (1) theme (2) throw (1) timer (1) timestamp (1) title (2) toggle (1) toolbar (6) tools (1) total count (1) transparent (1) tree (1) treenode (1) trigger (1) truncate (1) try (1) ucfirst (1) undefined (2) unique (1) unload (1) urlencode (1) utf8 (2) verzió (1) video (1) viewer (1) viewport (2) visible (2) vtype (1) window (2) xtype (1) zindex (2)

Extjs.blog.hu - RSS

Kérdés?