Pratybos
Penkios užduotys.
1. Kur dingsta stabilumas
Pakeisk Merge sąlygą iš a[i].Title <= b[j].Title į <.
Paleisk dcsort_test.go. Kuris testas nukrenta? O algo dc skaičiai —
pasikeitė? Paaiškink, kodėl vienas simbolis nekeičia nei sudėtingumo, nei
palyginimų skaičiaus, bet keičia rezultatą.
2. Kodėl mediana iš trijų nepakanka atvirkštinei tvarkai
7 žingsnis parodė: mediana iš trijų atvirkščiai surikiuotiems duomenims lieka kvadratinė.
Rask priežastį. Įrašinėk kiekvieno Partition grąžinamą p ir pažiūrėk, kaip
dalijasi masyvas pirmuose dešimtyje lygių. Ar pirmasis padalijimas geras? O
antrasis?
(Užuomina: pirmasis padalijimas yra idealus. Problema atsiranda tame, ką
Partition palieka po savęs.)
3. Hoare skaidymas
Realizuok PartitionHoare — skaidymą su dviem rodyklėmis, einančiomis iš abiejų
galų viena kitos link.
Paleisk medianą iš trijų su juo, atvirkštinei tvarkai. Ar kvadratas dingo? Jei taip — antros užduoties atsakymas patvirtintas.
4. Trijų dalių skaidymas
Sugeneruok biblioteką su -dup-rate 0.9: dešimt procentų skirtingų pavadinimų,
visa kita — pasikartojimai.
Paleisk visus keturis algoritmus. Kuris nukenčia labiausiai ir kodėl?
Tada realizuok skaidymą į tris dalis (mažesni / lygūs / didesni) ir pamatuok dar kartą.
5. Rekursijos gylis
QuickSortNaive surikiuotiems duomenims rekursija leidžiasi n lygių.
Penktoje pamokoje išmatavai, kad Go stekas laiko apie 8 milijonus kadrų.
Kokio dydžio surikiuotas masyvas nulaužtų QuickSortNaive?
Apskaičiuok, tada patikrink. Ir pagalvok, kodėl sort.Slice niekada taip
nepasielgia — atsakymas yra limit := bits.Len(uint(length)) jos kode.