„Algoritmuselmélet - PZH, 2013.04.24.” változatai közötti eltérés
| 75. sor: | 75. sor: | ||
}} | }} | ||
===5. Feladat=== | ===5. Feladat (Van megoldás)=== | ||
Egy <math>n</math> soros és kettő oszlopos táblázatban adott <math>n</math> számpár (egy sor egy számpárt tartalmaz, a számok mind különböző egész számok a táblázatban). Szeretnénk a táblázat sorait úgy átrendezni, hogy a 2. oszlop szerint növekvő sorrendben legyenek a sorok (számpárok). Egy fajta műveletet hajthatunk végre: kijelölhetünk néhány egymást alatti sort (számpárt) és ezeket rendezhetjük az első oszlop szerint növekvően vagy csökkenően. Adjon algoritmust, ami csak ezt a fajta műveletet használva <math>O(n)</math> lépésben megoldja a feladatot! | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*Rendezzük a tömböt az 1. oszlop szerint növekvően. | |||
*A továbbiakban minden <math>i.</math> lépésben megkeressük az <math>i.</math> legkisebb elemet, és a helyére tesszük. | |||
**Megkeressük a 2. oszlopban az <math>i.</math> legkisebbet, az ő helye a tömbben legyen <math>k</math> | |||
**Mivel az 1. oszlop szerint növekvően vannak a számpárok, így ahhoz, hogy a <math>k.</math> elem az <math>i.</math> helyre kerüljön, a számokat csökkenő sorrendbe kell rendezni az <math>[i \rightarrow k] </math> intervallumon. | |||
**Ha ezt megcsináltuk, akkor az első <math>i</math> helyen már rendezve lesz a tömb. | |||
**Az <math>[i+1 \rightarrow n]</math> intervallumon rendezzük a számokat növekvő sorrendben. | |||
**Ezt addig folytatjuk, míg nincs minden számpár a helyén. | |||
*A műveletet minden lépésben <math>\approx 2n</math> alkalommal használjuk: | |||
**Először növekvő sorrendbe rendeztük az egész tömböt. | |||
**Utána minden <math>i.</math> lépésben 2x: | |||
***Egyszer a helyére rakjuk az elemet azzal, hogy csökkenő sorrendbe rakjuk a számpárokat (persze csak a megfelelőket). | |||
***Majd újra növekvőbe a maradék számpárokat. | |||
*Így az algoritmus <math>O(n)</math> lépéssel rendezi a számpárokat a 2. oszlop szerint. | |||
[[File:algel_pzh_2013tavasz_5_1.PNG|400px]] | |||
}} | }} | ||