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:

  1. i konstans és j csökken eggyel
  2. i nő eggyel és j konstans

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 rende­zett 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