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

public class Cvicenie {

        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;
        }

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

                int od = 0;
                int po = p.length - 1;

                while (od <= po) {
                        int stred = (od + po) / 2;

                        if (p[stred] == hodnota)
                                return stred;
                        else if (p[stred] < hodnota)
                                od = stred + 1;
                        else
                                po = stred - 1;
                }

                return -1;
        }
}

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 faktorial(int n) {
                if (n <= 1) {
                        operacia();
                        return;
                }

                for (int i = 0; i < n; i++)
                        faktorial(n - 1);
        }

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

                faktorial(12);

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

import java.util.Arrays;
import java.util.Comparator;

public abstract class TriediaciAlgoritmus<E> {
        protected E[] p;
        private Comparator<E> comparator;
        private int pocetPorovnani;
        private int pocetVymen;

        protected int porovnaj(int idx1, int idx2) {
                pocetPorovnani++;

                if (comparator != null)
                        return comparator.compare(p[idx1], p[idx2]);
                else
                        return ((Comparable<E>) p[idx1]).compareTo(p[idx2]);
        }

        protected void vymen(int idx1, int idx2) {
                pocetVymen++;

                E pom = p[idx1];
                p[idx1] = p[idx2];
                p[idx2] = pom;
        }

        protected void vypisPole() {
                System.out.println(Arrays.toString(p));
        }

        public void utried(E[] p) {
                utried(p, null);
        }

        public void utried(E[] p, Comparator<E> comparator) {
                if (p == null)
                        throw new NullPointerException("p");
                if (comparator == null && p.length > 0 && !(p[0] instanceof Comparable<?>))
                        throw new NullPointerException("comparator");

                this.comparator = comparator;

                this.p = p;
                vypisPole();

                pocetPorovnani = 0;
                pocetVymen = 0;

                utried(p.length);

                vypisPole();
                this.p = null;
        }

        protected abstract void utried(int dlzkaPola);

        public int getPocetPorovnani() {
                return pocetPorovnani;
        }

        public int getPocetVymen() {
                return pocetVymen;
        }
}

public class BubbleSort<E> extends TriediaciAlgoritmus<E> {

        @Override
        protected void utried(int dlzkaPola) { 

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

public class SelectionSort<E> extends TriediaciAlgoritmus<E> {

        @Override
        protected void utried(int dlzkaPola) {

                for (int j = 0; j < dlzkaPola - 1; j++) {
                        int minIdx = j;

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

                        if (porovnaj(minIdx, j) < 0)
                                vymen(minIdx, j);
                }
        }
}