Kodėl rikiuoti — ir kas keičiasi
Šeštos pamokos namų darbo ketvirtas klausimas prašė suskaičiuoti, kiek kainuoja vienas rikiavimas ir kiek dvejetainių paieškų reikia, kad jis atsipirktų.
Tai ir yra šios pamokos priežastis. Dvejetainė paieška reikalauja surikiuotų
duomenų, o rikiuoti tu dar nemoki — iki šiol naudojai sort.Slice, nežinodamas,
kas viduje.
Nuo šios pamokos rikiuoji pats.
Kas keičiasi nuo šiol
Iki šiol dešiniajame skydelyje matydavai visą failą — ir tai buvo pamoka.
Nuo šios pamokos ten rasi tik karkasą: paketą, importus, parašus, sutartis
ir panic("not implemented"). Algoritmus aprašo tekstas ir pseudokodas kitame
žingsnyje. Testas pasako, ar pataikei.
Priežastis paprasta: iki šiol kodas buvo įrankis, kuriuo mokeisi. Nuo dabar kodas yra užduotis. Parodyti jį reikštų atiduoti atsakymą.
Trys algoritmai, viena sudėtingumo klasė
Visi trys šios pamokos algoritmai yra O(n²). Visi trys yra „blogi" ta prasme, kuria vadovėliai vartoja šį žodį.
Ir vis dėlto vienas iš jų yra Go standartinės bibliotekos rikiavimo dalis — apie tai 6 žingsnyje.
Geriausias, vidutinis, blogiausias — dabar trys skaičiai
Pirmoje pamokoje apibrėžėm tris atvejus ir pamatavom juos tiesinei paieškai. Rikiavime jie tampa daug ryškesni, nes įvesties tvarka keičia darbo kiekį šimtus kartų.
algo gen tam jau paruoštas. Pirmoje pamokoje parašei vėliavėles
-sorted ir -reverse ir tekste buvo parašyta, kad jos atsipirks tris kartus.
Šis yra pirmas iš tų trijų.
Spėk prieš skaitydamas toliau
Trys algoritmai — burbuliukų (bubble), išrinkimo (selection) ir įterpimo (insertion) rikiavimas. Visi O(n²).
Užsirašyk du dalykus:
- Kuris iš trijų greičiausias su 10 000 atsitiktinai išmėtytų įrašų?
- Kuris greičiausias, jei duomenys jau beveik surikiuoti?
Antrasis atsakymas skiriasi nuo pirmojo. Ir jis skiriasi labiau, negu tikiesi.