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

public class Tester {

        public static void main(String[] args) {
//              System.out.println(jeUsporiadane(new int[]{3,2,3,4}));

                BubbleSort bs = new BubbleSort();
                bs.utried(new int[]{1,2,3,5,4});
                bs.vypisPole();

                SelectionSort ss = new SelectionSort();
                ss.utried(new int[]{5,4,3,2,1});
                ss.vypisPole();
        }

        public static boolean jeUsporiadane(int[] p) {

                for (int i = 0; i < p.length-1; i++) {
                        if(p[i]>p[i+1]) return false;
                }
                return true;
    }

/* ALTERNATIVA
        public static boolean jeUsporiadane(int[] p) {

                int iterator = 0;

                while ((iterator < p.length - 1) && (p[iterator] <= p[iterator + 1])) {
                        iterator++;
                }

                if (iterator == (p.length - 1))
                        return true;
                return false;
        }
*/

        public static int binarneHladajIndex(int[] p, int hodnota) {

                int odIndex = 0;
                int doIndex = p.length - 1;
                int stredIndex = 0;

                while (doIndex - odIndex >= 1) {
                        stredIndex = (odIndex+doIndex) /2;
                        if(p[stredIndex]==hodnota) {
                                return stredIndex;
                        } else if (p[stredIndex]<hodnota) {
                                odIndex = stredIndex+1;
                        } else {
                                doIndex = stredIndex - 1;
                        }
                }

                if (p[stredIndex + 1] == hodnota) {
                        return stredIndex + 1;
                }

                return -1;
        }
}

import java.util.Arrays;

public abstract class TriediaciAlgoritmus {

        /**
         * Aktualne usporiadavane pole
         */
        private int[] p;

        /**
         * 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) {
                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);
}

public class BubbleSort extends TriediaciAlgoritmus {

        @Override
        protected void utried(int dlzkaPola) {

                int pocetPorovnani = 0;
                int pocetVymen = 0;

                for (int i = 0; i < dlzkaPola-1; i++) {
                        for (int j = i+1; j < dlzkaPola; j++) {
                                pocetPorovnani++;
                                if(porovnaj(i, j)>0) {
                                        vymen(i, j);
                                        pocetVymen++;
                                }
                        }
                }
                System.out.println("Pocet porovnani: "+pocetPorovnani+"\t Pocet vymen: "+pocetVymen);
        }

}

public class SelectionSort extends TriediaciAlgoritmus {

        @Override
        protected void utried(int dlzkaPola) {

                int pocetPorovnani = 0;
                int pocetVymen = 0;

                for (int i = 0; i < dlzkaPola - 1; i++) {
                        int minIdx = i;
                        for (int j = i + 1; j < dlzkaPola; j++) {
                                pocetPorovnani++;
                                if (porovnaj(j, minIdx) < 0)
                                        minIdx = j;
                        }
                        vymen(i, minIdx);
                        pocetVymen++;
                }
                System.out.println("Pocet porovnani: " + pocetPorovnani
                                + "\t Pocet vymen: " + pocetVymen);
        }

}

public class Zlozitost {

        // Celkovy pocet zrealizovanych operacii
        public static int pocet = 0;

        // Elementarna operacia
        public static void operacia() {
                pocet++;
        }

        // Linearny pocet operacii v zavislosti od n
        public static void linearna(int n) {
                for (int i = 0; i < n; i++)
                        operacia();
        }

        // n.log(n) pocet operacii v zavislosti od n
        public static void nlogn(int n) {
                for (int i = 0; i < n; i++)
                        for (int j = 1; j < n; j = j * 2)
                                operacia();
        }

        // Kvadraticky pocet operacii v zavislosti od n
        public static void kvadraticka(int n) {
                for (int i = 0; i < n; i++)
                        for (int j = 0; j < n; j++)
                                operacia();
        }

        // Exponencialny pocet operacii v zavislosti od n
        public static void exponencialna(int n) {
                if (n <= 1) {
                        operacia();
                        return;
                }

                // 2^n = 2*2^(n-1)
                exponencialna(n - 1);
                exponencialna(n - 1);
        }

        public static void logaritmus(int n) {
                while (n>0) {
                        n = n/2;
                        operacia();
                }
        }

        public static void main(String[] args) {
                System.out.println("Zaciatok...");
                long zaciatok = System.nanoTime();

                linearna(1000000);
//                kvadraticka(1000000);
                logaritmus(1000000);
//                exponencialna(35);

                long koniec = System.nanoTime();
                System.out.println("Cas behu: " + ((koniec - zaciatok) / 1000000)
                                + " milisekund");
        }
}