Megoldások az második gyakorlathoz 1. A teljes feladatsorban szerepel a megoldás a Rendezés 21. feladatnál. 2. A teljes feladatsorban szerepel a megoldás a Rendezés 10. feladatnál. 3. Vegyünk $\lfloor {\log}_2 n \rfloor$ elemet, ezeket rendezzük. Ez $O(\log n\cdot \log \log n)$ lépés. Az így kiválasztott elemek lesznek a keresett Si halmazok első elemei. Most hogy már megvannak a halmazok, azt kell csak eldönteni, hogy a többi elemek mely halmazokba kerüljenek. Ehhez vegyünk egyet a maradék elemek közül és határozzuk meg, hogy melyik két alapítóelem közé esik. Ez $O(\log\log n)$ lépés bináris kereséssel. Tegyük ezután annak az alapítóelemnek a halmazába, amelyik éppen nagyobb nála, vagy ha nincsen ilyen ( nagyobb a legnagyobbnál is), akkor a legnagyobbéba. Az így kapott felosztás teljesíti a feladat feltételét, az elemek elhelyezése pedig n darab bináris kersés, azaz $O(n\cdot \log \log n)$ lépés. 4. A teljes feladatsorban szerepel a megoldás a Rendezés 18. feladatnál. 5. Az összefésüléshez hasonlóan járunk el, most m darab halmazt fésünk össze. Ezt úgy tesszük, hogy felveszünk egy mk méretű B tömböt a végeredménynek, ebbe írjuk majd ki az elemeket rendezetten, az Ai tömbök még fel nem dolgozott legkisebb elemeit pedig egy kupacban tartjuk. Az elején a B üres, a kupacba pedig minden Ai-ből a legkisebb elemet tesszük. Egy lépés a következő: töröljük a minimális elemet a kupacból és áttesszük a B-be, aztán pedig abból az Ai-ből, ahonnan a most kirakott elem jött beszúrjuk a következőt a kupacba. Összesen kell mk ilyen lépés, minden lépés egy MINTÖR és egy BESZÚR művelet, ez összesen $mk\log m$ lépés, mert a kupac mérete m. Ez optimális, mert már az Ai tömbök j-edik elemeinek rendezéséhez is kell $m\log m$ lépés, ezek pedig rendezetten kiolvashatók mk idôben a rendezett B tömbből. 6. A teljes feladatsorban szerepel a megoldás a Rendezés 37. feladatnál. 7. A teljes feladatsorban szerepel a megoldás a Rendezés 40. feladatnál. 8. A teljes feladatsorban szerepel a megoldás a Rendezés 27. feladatnál. 9. A teljes feladatsorban szerepel a megoldás a Rendezés 29. feladatnál. 10. Keressük meg a legnagyobb x koordinátával rendelkező pontot, legyen ez mondjuk a Pi, ezt n lépésben megtehetjük. Számoljuk ki minden másik Pj pontra a Pi-Pj egyenes meredekségét, ez egyenesenként konstans lépés, összesen O(n). Ezen meredekségek közül válasszuk ki a legnagyobbat (O(n) lépés), az így kapott egyenes jó lesz. 11. A teljes feladatsorban szerepel a megoldás a Rendezés 53. feladatnál. 12. A teljes feladatsorban szerepel a megoldás a Rendezés 16. feladatnál. 13. Tessék gondolkodni.