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

import java.util.Arrays;

public class Main {

        public static void main(String[] args) {
                Integer[] pole = nahodnePole(15);
                TriediaciAlgoritmus<Integer> algQS = new QuickSort<Integer>();

                System.out.println(Arrays.toString(pole));
                algQS.utried(pole);
                System.out.println(Arrays.toString(pole));
        }

        private static Integer[] nahodnePole(int dlzka) {
                Integer[] pole = new Integer[dlzka];
                for (int i = 0; i < pole.length; i++)
                        pole[i] = (int) (Math.random() * 100);

                return pole;
        }
}

import java.util.Arrays;

public abstract class TriediaciAlgoritmus<T extends Comparable<T>> {
        protected T[] p;
        private int pocetPorovnani;
        private int pocetVymen;

        protected int porovnaj(int idx1, int idx2) {
                pocetPorovnani++;
                return p[idx1].compareTo(p[idx2]);
        }

        protected void vymen(int idx1, int idx2) {
                pocetVymen++;
                T pom = p[idx1];
                p[idx1] = p[idx2];
                p[idx2] = pom;
        }

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

        public void utried(T[] p) {
                pocetPorovnani = 0;
                pocetVymen = 0;

                this.p = p;
                utried(p.length);
                this.p = null;
        }

        protected abstract void utried(int dlzkaPola);

        public int getPocetPorovnani() {
                return pocetPorovnani;
        }

        public int getPocetVymen() {
                return pocetVymen;
        }
}

public class QuickSort<T extends Comparable<T>> extends TriediaciAlgoritmus<T> {

        @Override
        protected void utried(int dlzkaPola) {
                quickSort(p, 0, p.length - 1);
        }

        private void quickSort(T[] p, int odIdx, int poIdx) {
                if (poIdx <= odIdx)
                        return;

                int pivotIdx = rozdel(p, odIdx, poIdx);
                quickSort(p, odIdx, pivotIdx - 1);
                quickSort(p, pivotIdx + 1, poIdx);
        }

        private int rozdel(T[] p, int odIdx, int poIdx) {

                int pivotIdx = poIdx;
                int idx = odIdx;

                for (int i = odIdx; i < poIdx; i++) {
                        if (porovnaj(i, pivotIdx) < 0) {
                                vymen(i, idx);
                                idx++;
                        }
                }

                vymen(idx, pivotIdx);
                return idx;
        }
}

import java.security.InvalidParameterException;

public class TakmerUplnyBinarnyStrom {

        public static <T> T hodnotaVStrome(T[] pole, String cesta) {

                int idx = 0, i = 0;     // koren stromu
                while (idx < pole.length && i < cesta.length()) {
                        if (cesta.charAt(i) == 'L')
                                idx = 2 * idx + 1;
                        else if (cesta.charAt(i) == 'R')
                                idx = 2 * idx + 2;
                        else
                                throw new InvalidParameterException(cesta);
                        i++;
                }

                if (idx >= pole.length || i < cesta.length())
                        return null;
                else
                        return pole[idx];
        }

        public static <T extends Comparable<T>> boolean jeHaldou(T[] pole) {
                for (int i = 0; i < (pole.length - 2) / 2; i++) {
                        int idxLavy = 2 * i + 1;
                        int idxPravy = 2 * i + 2;

                        if (idxLavy < pole.length && pole[i].compareTo(pole[idxLavy]) < 0)
                                return false;
                        if (idxPravy < pole.length && pole[i].compareTo(pole[idxPravy]) < 0)
                                return false;
                }

                return true;
        }

        public static void main(String[] args) {
                Integer[] pole = new Integer[] { 100,34,20,18,10,5,15,16,12,9};
                System.out.println(hodnotaVStrome(pole, "LRLR"));
                System.out.println(jeHaldou(pole));
        }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class MergeSort {

        public static <T extends Comparable<T>> List<T> zluc(List<T> p1, List<T> p2) {
                List<T> vysledok = new ArrayList<T>(p1.size() + p2.size());
                int idx1 = 0, idx2 = 0;
                while (idx1 < p1.size() && idx2 < p2.size()) {
                        if (p1.get(idx1).compareTo(p2.get(idx2)) < 0)
                                vysledok.add(p1.get(idx1++));
                        else
                                vysledok.add(p2.get(idx2++));
                }

                while (idx1 < p1.size())
                        vysledok.add(p1.get(idx1++));
                while (idx2 < p2.size())
                        vysledok.add(p2.get(idx2++));

                return vysledok;
        }

        public static void main(String[] args) {
                List<Integer> p1 = Arrays.asList(0, 2, 4, 6, 8);
                List<Integer> p2 = Arrays.asList(1, 3, 5, 7, 9);

                System.out.println(zluc(p1, p2));
        }
}