Pratybos
Penkios užduotys.
1. Suskaičiuok k Title raktui
Šešto žingsnio lentelėje paskutinė eilutė buvo palikta tuščia.
Tarkim, pavadinimas — iki 20 simbolių iš 32 raidžių abėcėlės. Kiek galimų
reikšmių? Kiek baitų užimtų count masyvas su int32 elementais?
Palygink su Žemės mase gramais (≈6×10²⁷). Užrašyk abu skaičius.
2. CountingSortByYear
Skaičiavimo rikiavimas pagal Year vienu perėjimu, k = 131.
Palygink su RadixSortByYear — keturiais perėjimais po k = 10. Kuris greitesnis
šiam intervalui? Nuo kokio intervalo pločio skaitmeninis pradėtų laimėti?
3. Kai k didesnis už n
Sugeneruok 100 įrašų. Surikiuok pagal Year skaičiavimo rikiavimu.
Kiek vietų turi count masyvas? Kiek įrašų? Kokia O(n + k) dalis dominuoja?
Tada padidink MaxYear iki 1 000 000 ir pakartok. Kada tampa juokinga?
4. Neigiami ir ne sveikieji raktai
Rating yra 0–100. O jei būtų −50…+50? O jei būtų float64 nuo 0 iki 5?
Pritaikyk CountingSortByRating pirmam atvejui. Antram — paaiškink, kodėl
tiesiogiai neįmanoma, ir pasiūlyk, ką reikėtų padaryti su raktu.
5. Sulaužyk skaitmeninį rikiavimą kitaip
7 žingsnis sugadino vidinį perėjimą. Sugadink tvarką: rikiuok skaitmenis nuo svarbiausio prie mažiausiai svarbaus (MSD vietoj LSD), paliekant stabilų vidinį perėjimą.
Ar rezultatas teisingas? Kodėl LSD veikia, o šis ne — ir ką MSD skaitmeniniam rikiavimui reikėtų daryti papildomai, kad veiktų?