Egy
programozási feladat |
|
A feladat a következőképpen hangzik: az első i legkisebb elem
megkeresése egy n elemből álló valós sorozatban. A feladat első
elolvasásra nagyon egyszerűnek tűnik. És tényleg egyszerű,
mert rendezzük növekvő sorrendben a sorozatot, aminek eredményeként
rögtön meg van az első legkisebb i elem, vagyis a tényleges első i
elem. De annak érdekében, hogy a feladatot
érdekessé tegyük, azt kérjük, hogy a megoldásnak lineáris komplexitása legyen (nem feledjük, hogy Javaban
programozunk J). Ez lehetetlen a rendezéssel való megoldás
esetében, mivel a komplexitás szempontjából legjobb a rendezési algoritmus (Quicksort) komplexitása is nlogn. Ezért egy teljesen más ötletre van szükségünk. |
|
A feladat
megoldása |
|
A feladat
megoldásának lényege az úgynevezett particionálásban van. Ez a módszer még megtalálható a Quicksort algoritmusában is. A módszer célja, hogy a sorozat
első elemét egy k pozícióra helyezze a sorozat alsó (low) indexszáma és a sorozat felső (high) indexszáma között. Mindezt úgy kell
megtenni, hogy a sorozat minden eleme a low és k-1 pozíciók
között kisebb vagy egyenlő legyen, mint x[k] (x a
sorozat neve) és a sorozat minden eleme a k+1 és high
pozíciók között nagyobb legyen, mint x[k]. Ebben a módszerben két munkatípus van:
A
módszert implementáló függvény a következő: public static int partitionalas(int
low,int high,double[]
x) //a sztatikus particionalas
nevű függvény, melynek az //argumentumai két egész típusú változó low és high, valamint //az x valós sorozat és amely egy egész számot küld vissza, //ami a végső pozícióját jelenti az első elemnek a
sorozatból //az új particionált sorozatban //low és high az indexszámok, amelyek között történik a //sorozat első elemének particionálása { boolean
pozPivot=false; //a pozPivot nevű boolean típusú változó
deklarálása és //inicializálása a false logikai értékkel double aux; //az aux valós típusú változó
deklarálása, amelyet a //sorozat két elemének a kicserélésére használunk while(low<high) //egy while ciklus, amíg az alsó
indexszám kisebb mint a //sorozat felső indexszáma { if (x[low]>x[high]) //ha az alsó pozíción található elem
nagyobb mint a //felső pozíción található elem { aux=x[low]; x[low]=x[high]; x[high]=aux; //megtörténik a két elem felcserélése pozPivot=!pozPivot; //pozPivot értéke a tagadott érték lesz,
így //megtörténik a sorozat átjárási módszerének //a változtatása } if (pozPivot) //ha pozPivot logikai értéke true, akkor low++; //növelődik eggyel az alsó indexszám else high--; //másképp csökkenteni kell eggyel a felső
indexszámot } return low; //a függvény az alsó indexszám értékét
küldi vissza, ami //megadja a low pozícióban található elem pozícióját //a particionált
sorozatban } Példának álljon itt a (6,9,3,1,2)
sorozat, és kövessük végig az algoritmus lefutását erre a sorra: x=(6,9,3,1,2) low=1 high=5 pozPivot=false Első iteráció: x=(2,9,3,1,6) pozPivot=true low=2 Második iteráció: x=(2,6,3,1,9) pozPivot=false high=4 Harmadik iteráció: x=(2,1,3,6,9) pozPivot=true low=3 Negyedik iteráció: x=(2,1,3,6,9) low=4 A növekvő sorrendben rendezett sorozat: x=(1,2,3,6,9) A particionálás után az első elem,
vagyis a 6 a negyedik pozícióra került és ez a pozíciója a rendezett
sorozatban is. Az algoritmus komplexitása lineáris,
mert habár a particionalas függvény
többször is meghívásra kerül, de a sorozat amire meghívjuk mindig kisebb mint
az eredeti sorozat, ezért a komplexitás lineáris. |
|
Kiss-Jakab Kinga |