Pratybos
Penkios užduotys.
1. Kada burbuliukų rikiavimas praranda savo vėliavėlę
Išimk swapped vėliavėlę iš savo BubbleSort ir paleisk su -order sorted.
Kiek palyginimų dabar? Susiek skaičių su n. Vienu sakiniu paaiškink, kodėl viena loginė kintamoji pakeičia sudėtingumo klasę geriausiu atveju.
2. InsertionSortBinary
Įterpimo rikiavimas ieško vietos tiesiškai, stumdamas po vieną. Pakeisk
paiešką 6 pamokos LowerBound.
Palyginimų turėtų smarkiai sumažėti. O sukeitimų? Pamatuok abu ir paaiškink, kodėl bendras laikas beveik nepasikeičia.
(Tai vienas iš svarbiausių šio kurso rezultatų: sumažinęs vieną kainą, kitos nepajudinai.)
3. Stabilumo kaina
Padaryk SelectionSort stabilų: vietoj sukeitimo įterpk mažiausią elementą
į vietą, pastumdamas likusius.
Kiek dabar sukeitimų? Palygink su n−1. Ar tai vis dar išrinkimo rikiavimas?
4. Kur riba tavo mašinoje
6 žingsnyje riba tarp įterpimo ir sort.Slice beveik surikiuotiems duomenims
buvo ~2 000.
Rask savąją. Pamatuok su 0 %, 1 % ir 5 % netvarkos. Kaip riba slenka, kai netvarkos daugėja?
5. Kada rikiuoti apskritai neverta
Turi 1 000 000 įrašų ir reikia rasti dešimt geriausiai įvertintų.
Palygink du kelius: (a) surikiuoti viską ir paimti dešimt; (b) vieną kartą pereiti sąrašą, laikant dešimt geriausių.
Suskaičiuok abu. Skirtumas turi būti didžiulis. Devinta pamoka pastatys struktūrą, kuri (b) daro tvarkingai.