Riešenia (skupina D, 5. týždeň)

import java.util.Arrays;


public class BubbleSort extends TriediaciAlgoritmus {

        @Override
        protected void utried(int dlzkaPola) {
//              vypisPole();
                for (int i = 0; i < dlzkaPola; i++) {
                        for (int j = i+1; j < dlzkaPola; j++) {
                                if(porovnaj(i, j)>0) vymen(i,j);
                        }
                }
//              vypisPole();
                System.out.println(pocetPorovnani);
        }

        public static void main(String[] args) {
                int[] p = new int[]{5,687,4,987,3654,987,615,987,54,87};

                BubbleSort triediaciAlg = new BubbleSort();

                triediaciAlg.utried(p);
                System.out.println(Arrays.toString(p));
        }

}
 

public class Cvicenie05 {

        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] pole = { 2, 4, 7, 3, 22, 8, 1 };
                System.out.println(hodnotaVStrome(pole, "LR"));

        }

        public static int hodnotaVStrome(int[] pole, String cesta) {
                int idx = 0;
                if (!(cesta.equals(""))) {
                        for (int i = 0; i < cesta.length(); i++) {
                                if (cesta.charAt(i) == 'L') {
                                        idx = 2 * idx + 1;

                                }
                                if (cesta.charAt(i) == 'R') {
                                        idx = 2 * idx + 2;

                                }

                        }
                        return pole[idx];

                }

                return 0;
        }

}
 

import java.util.Arrays;

import sk.upjs.paz.calltree.CallTree;

public class QuickSort extends TriediaciAlgoritmus {

        static int[] q = new int[]{13,12,11,10,9,8,7};
        //static int[] q = new int[]{1,3,2,5,7,6,4};
        @Override
        protected void utried(int dlzkaPola) {
                // TODO Auto-generated method stub
                quickSort(0, dlzkaPola-1);
                System.out.println(pocetPorovnani);
        }



        public static void main(String[] args) {
                // TODO Auto-generated method stub

                int[] p = q;

                QuickSort triediaciAlg = new QuickSort();

                triediaciAlg.utried(p);
                System.out.println(Arrays.toString(p));

        }

        public int rozdel(int odIdx, int poIdx) {
                int pivot = poIdx;
                int idx = odIdx;
                for (int i = odIdx; i <= poIdx - 1; i++)
                        if (porovnaj(i,pivot)<0) {
                                vymen(i, idx);
                                idx++;
                        }
                vymen(idx, poIdx);
                return idx;
        }

        void quickSort(int odIdx, int poIdx) {
                 CallTree.markCall(odIdx,poIdx,Arrays.toString(q));

                if (odIdx >= poIdx)
                        return;
                int pivotIdx = rozdel(odIdx, poIdx);
                quickSort(odIdx, pivotIdx - 1);
                quickSort(pivotIdx + 1, poIdx);
        }

}
 

import java.util.Arrays;

public abstract class TriediaciAlgoritmus {

        /**
         * Aktualne usporiadavane pole
         */
        private int[] p;
        public int pocetPorovnani=0;

        /**
         * Porovna prvky v poli na zadanych indexoch
         *
         * @return vrati zaporne cislo, ak p[idx1] < p[idx2],
         *                 0, ak p[idx1]==p[idx2], a
         *         kladne cislo, ak p[idx1] > p[idx2]
         */
        protected int porovnaj(int idx1, int idx2) {
                        pocetPorovnani++;
                return p[idx1] - p[idx2];

                /*
                 * Alternativa:
                 * if (p[idx1] < p[idx2]) return -1;
                 * if (p[idx1] > p[idx2]) return 1;
                 * return 0;
                 */
        }

        /**
         * Vymeni prvky v usporiadavanom poli na zadanych indexoch
         */
        protected void vymen(int idx1, int idx2) {
                int pom = p[idx1];
                p[idx1] = p[idx2];
                p[idx2] = pom;
        }

        /**
         * Vypise pole
         */
        protected void vypisPole() {
                System.out.println(Arrays.toString(p));
        }

        /**
         * Usporiada prvky v poli od najmensieho po najvacsie
         *
         * @param p
         *            pole, ktoreho prvky maju byt usporiadane
         */
        public void utried(int[] p) {
                this.p = p;
                utried(p.length);
                this.p = null;
        }

        /**
         * Metoda, ktora implementuje triedenie podla urciteho algoritmu
         * @param dlzkaPola dlzka (pocet prvkov) usporiadavaneho pola
         */
        protected abstract void utried(int dlzkaPola);
}