Kodėl log n

Septinta pamoka baigėsi pusantros minutės burbuliukų rikiavimo šimtui tūkstančių įrašų — ir vienu rezultatu, kurio nesitikėjai: įterpimo rikiavimas beveik tvarkingiems duomenims aplenkė visus.

Ši pamoka pakeičia patį metodą. Iš O(n²) į O(n log n), ir su tuo pačiu šimtu tūkstančių įrašų skirtumas bus dviejų šimtų kartų.

Kodėl log n

Skaidyk masyvą pusiau, pusiau, pusiau — kiek kartų, kol liks po vieną? log₂ n kartų. 100 000 įrašų — septyniolika padalijimų.

Kiekviename gylyje sutvarkomi visi n elementai, tad viso darbo n·log₂ n. Šimtui tūkstančių tai maždaug 1,7 milijono vietoj penkių milijardų.

Tas pats skaičius, kurį matei šeštoje pamokoje: dvejetainė paieška surado įrašą per 17 palyginimų, nes 2¹⁷ > 100 000. Ta pati riba, kitas pritaikymas.

Ką pastatysi

Du algoritmus, ir jie skiriasi labiau nei atrodo:

• suliejimo rikiavimas — stabilus, neturi blogo atvejo, bet reikalauja antro masyvo;
• greitasis rikiavimas — vietoje, dažniausiai greitesnis, nestabilus, ir su neteisingu pivotu grįžta į O(n²).

Trys iš šių savybių turės pasekmių, kurias pamatuosi: stabilumas 5 ir 6 žingsniuose, pivotas — 7.

Kas lieka kaip septintoje

Karkasas dešinėje, algoritmai tekste ir pseudokode, testas — nuosprendis. dcsort.go bus tavo.