package sk.upjs.cvicenie02;

import java.util.Arrays;

import sk.upjs.jpaz2.*;

public class Launcher {

        public static void main(String[] args) {
                int[] p = { 2, 3, 5, 7, 8, 11, 12, 15, 19, 22 };
//              System.out.println(p.length);
//              System.out.println(binarneHladajIndex(p, 3));

                int[] p2 = { 1, 2, 3, 4, 5, 6, 7, 8 };
                int[] p3 = p2.clone();
                BubbleSort bs = new BubbleSort();
                System.out.println(Arrays.toString(p2));
                bs.utried(p2);
                System.out.println(Arrays.toString(p2));

                SelectionSort ss = new SelectionSort();
                ss.utried(p3);
                System.out.println(Arrays.toString(p3));

        }

        public static int binarneHladajIndex(int[] p, int hodnota) {
                int odIdx = 0;
                int poIdx = p.length - 1;

                while (odIdx <= poIdx) {
                        int stredIdx = (odIdx + poIdx) / 2;

                        if (p[stredIdx] == hodnota)
                                return stredIdx;

                        if (hodnota < p[stredIdx]) {
                                // hladam vlavo
                                poIdx = stredIdx - 1;
                        } else {
                                // hladam vpravo
                                odIdx = stredIdx + 1;
                        }
                }
                return -1;
        }
}

package sk.upjs.cvicenie02;

import java.util.Arrays;

public abstract class TriediaciAlgoritmus {

        /**
         * Aktualne usporiadavane pole
         */
        private int[] p;
        private int pocetPorovnani = 0;
        private int pocetVymen = 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 Integer.compare(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) {
                pocetVymen++;
                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);
                System.out.println("pocet porovnani: " + pocetPorovnani);
                System.out.println("pocet vymen: " + pocetVymen);
                this.p = null;
        }

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

package sk.upjs.cvicenie02;

public class BubbleSort extends TriediaciAlgoritmus {

        @Override
        protected void utried(int dlzkaPola) {
                boolean bolaVymena;
                do {
                        bolaVymena = false;
                        for (int i = 0; i < dlzkaPola - 1; i++) {
                                if (porovnaj(i, i + 1) == 1) {
                                        vymen(i, i + 1);
                                        bolaVymena = true;
                                }
                        }
                } while (bolaVymena);
        }

}
 

package sk.upjs.cvicenie02;

public class SelectionSort extends TriediaciAlgoritmus {

        @Override
        protected void utried(int dlzkaPola) {

                for (int i = 0; i < dlzkaPola - 1; i++) {
                        int minIdx = i;
                        for (int j = i + 1; j < dlzkaPola; j++)
                                if (porovnaj(j, minIdx) < 0)
                                        minIdx = j;
                        vymen(i, minIdx);
                }
        }
}

package sk.upjs.cvicenie02;
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 main(String[] args) {
                System.out.println("Zaciatok...");
                long zaciatok = System.nanoTime();

                linearna(1000000000);

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