Nagy számok közelről · 3 perc olvasás
Egymillió adat rendezése: húszmillió vagy ötszázmilliárd összehasonlítás?
Ugyanazt az egymillió rekordot az egyik egyszerű eljárás közel ötszázmilliárd összehasonlítással rendezi át kedvezőtlen sorrendből. Egy másik eljárásnál húszmilliónál kevesebb kulcs-összehasonlítás is elegendő. Ekkora különbséget egy kisebb hardvercsere aligha tüntet el.
Ebben a cikkben
Csak a kulcsok összehasonlítását számoljuk
A saját feladatban egymillió különböző egész számot kell növekvő sorrendbe rendezni. Az összehasonlítás azt dönti el, két szám közül melyik kisebb. A memóriaolvasást, az elemek másolását és a program egyéb műveleteit most külön hagyjuk. Ez a közös mértékegység az eljárások nagyságrendi különbségét mutatja meg.
Az első módszer a szokásos beszúrásos rendezés: az új elemet visszafelé haladva beillesztjük a már rendezett részbe. A második az összefésüléses rendezés: kisebb részeket rendezünk, majd a rendezett részeket egyesítjük. Az MIT algoritmikai tananyaga ezt a váltást a négyzetes és az n log n jellegű növekedés összehasonlítására is használja.
A fordított sorrend minden új elemnek hosszú utat ad
A beszúrásos módszer számára a csökkenő sorrend kedvezőtlen. A második elemet egy korábbi számmal, a harmadikat kettővel, és így tovább, az utolsót n−1 korábbi számmal kell összevetni. Az összes kulcs-összehasonlítás 1 + 2 + … + (n−1) = n(n−1)/2.
Egymillió elemnél ez 1 000 000 × 999 999 / 2 = 499 999 500 000, vagyis csaknem ötszázmilliárd összehasonlítás. A négyzetes jelleg miatt nagy n mellett az adatmennyiség kétszerezése közel négyszerezi ezt a munkát. Az eljárás viszont már növekvő sorrendű adatokon kedvező lehet: ott a szokásos változatnak csak n−1 kulcs-összehasonlítás kell.
Minden szinten nagyjából egyszer dolgozunk végig az adatokon
Az összefésüléses módszernél két már rendezett listát az elejüktől hasonlítunk össze. Mindig a kisebb következő elemet tesszük az eredménybe. Két összesen m elemű lista egyesítéséhez legfeljebb m−1 kulcs-összehasonlítás kell, mert az egyik lista kiürülésekor a másik maradéka közvetlenül hozzáfűzhető.
A felezésekből egymillió elemnél legfeljebb húsz összefésülési szint adódik. Egy szinten az összes lista együttes hossza egymillió, ezért a 20 × 1 000 000 = 20 millió kényelmes felső becslés. A szokásos, felező változat pontos legrosszabb értéke ennél kisebb, 18 951 425. A cikk fő összevetéséhez a könnyen követhető húszmilliós korlát is elegendő.
Az ezerszeres adatmennyiség másképp nő a két módszernél
Egymillióról egymilliárd elemre a négyzetes munka közel egymilliószorosára nő. Az n log₂ n jellegű becslésben az elemszám ezerszereződik, a szintek száma körülbelül húszról harmincra változik. A húszmilliós becslésből harmincmilliárdos felső becslés lesz, ami 1500-szoros növekedés.
Tegyük fel kizárólag szemléltetésként, hogy másodpercenként százmillió kulcs-összehasonlítást tudnánk végezni, és minden egyéb költség nulla. Az egymilliós, fordított bemeneten a beszúrásos számítás ekkor körülbelül 5000 másodperc, a húszmilliós becslés 0,2 másodperc lenne. Ez mesterséges sebességmodell, mérésnek nem tekinthető. Valódi gépen a másolás és az adat-hozzáférés is számít.
Az adatok állapotát és a teljes feladatot is nézd
Kis vagy majdnem rendezett bemenetnél egy egyszerűbb eljárás jó választás lehet. Nagy, kedvezőtlen sorrendű adathalmaznál a növekedési ütem döntővé válik. A rendezési kulcs is lehet drága: hosszú szövegek, bonyolult összehasonlítás vagy lemezről olvasott rekordok esetén egyetlen összevetés költsége sem állandó apróság.
Tisztázd azt is, szükséges-e a teljes rendezés. A legkisebb tíz érték kiválasztása más feladat, mint egymilliárd rekord teljes sorrendjének előállítása. A műveletszám jó első szűrő a megoldások között; a végleges döntést az adatokra jellemző mérés és a memóriaigény együtt támasztja alá.
A példák és a források
A számpéldák saját, szemléltető feladatok; a megadott feltételezésekből és képletekből újraszámolhatók. Valós vállalkozásra, országos statisztikára vagy jövőbeli eredményre nem vonatkoznak.
Forrásellenőrzés: 2026-11-09. A hivatkozások a fogalmakat és a módszert támasztják alá; a példaszámítások a cikk részei.
Négy kérdés a cikkhez
A válaszokból kiderül, melyik összefüggést érted már, és melyik részt érdemes újraolvasnod. A válaszokat és a pontszámot nem mentjük.
