Cvičenia: 5. týždeň - riešenia úloh

import javax.swing.JEditorPane;

public class Haldovanie {

        public static int hodnotaVStrome(int[] pole, String cesta) {
                char a;
                int index = 0;
                for (int i = 0; i < cesta.length(); i++) {
                        a = cesta.charAt(i);
                        if (a == 'R') {
                                index = 2 * index + 2;
                        } else {
                                index = index * 2 + 1;
                        }
                }
                if (index >= pole.length) {
                        return -1;
                }
                return pole[index];
        }

        public static boolean jeHaldou(int[] pole) {
                for (int i = 0; i < pole.length; i++) {
                        if (2 * i + 1 < pole.length) {
                                if (pole[i] != Math.max(pole[i], pole[2 * i + 1]))
                                        return false;
                        }

                        if (2 * i + 2 < pole.length) {
                                if (pole[i] != Math.max(pole[i], pole[2 * i + 2]))
                                        return false;
                        }
                }
                return true;

                /*
                 * if (2 * i + 1 >= pole.length || 2 * i + 2 < pole.length) if (pole[i]
                 * != Math.max(pole[i], Math.max(pole[2 * i + 1], pole[2 * i + 2])))
                 * return false;
                 */

        }

        public static void main(String[] args) {
                int[] halda = new int[] {28, 25, 23, 20, 18, 15, 19, 10, 8, 18 };
                System.out.println(hodnotaVStrome(halda, "RLL"));
                System.out.println(hodnotaVStrome(halda, "LRR"));
                System.out.println(hodnotaVStrome(halda, "LRL"));

                System.out.println(jeHaldou(halda));

        }

}
 

import java.util.Arrays;

public abstract class TriediaciAlgoritmus {

        /**
         * Aktualne usporiadavane pole
         */
        protected 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 Quisksort extends TriediaciAlgoritmus {

        @Override
        protected void utried(int dlzkaPola) {

                quicksort(0, dlzkaPola-1);
        }

        public void quicksort(int odIdx, int poIdx) {

                if(odIdx>poIdx) {
                        return;
                }

                int pivot = rozdel(odIdx, poIdx);
                quicksort(odIdx, pivot-1);
                quicksort(pivot+1, poIdx);

        }

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

                vymen(pivot, idx);
                return idx;
        }

        public static void main(String[] args) {
                Quisksort qs = new Quisksort();
                qs.p = new int[]{9, 8, 2, 4, 8, 11, 7, 5};
                qs.vypisPole();
                qs.utried(qs.p.length);
                qs.vypisPole();
        }
}
 

import java.util.Arrays;


public class MergSort {

        public static int[] zluc(int[] p1, int[] p2) {
                int[] novePole = new int[p1.length+p2.length];

                int index1 = 0;
                int index2 = 0;
                // index v novom poli
                int indexNP = 0;


                while(index1<p1.length &&
                                index2<p2.length) {
                        if(p1[index1] < p2[index2]) {
                                novePole[indexNP] = p1[index1];
                                index1++;
                                indexNP++;
                        }
                        else {
                                novePole[indexNP] = p2[index2];
                                index2++;
                                indexNP++;
                        }
                }

                if(index1 >= p1.length) {
                        for (int i = index2; i < p2.length; i++) {
                                novePole[indexNP] = p2[i];
                                indexNP++;
                        }
                }

                if(index2 >= p2.length) {
                        for (int i = index1; i < p1.length; i++) {
                                novePole[indexNP] = p1[i];
                                indexNP++;
                        }
                }

                return novePole;
        }

        public static void main(String[] args) {

                int[] p1 = new int[]{2, 4, 6, 7, 10};
//              int[] p2 = new int[]{3, 5, 8, 9, 11, 12, 13};
                int[] p2 = new int[]{8};
                System.out.println(Arrays.toString(zluc(p1, p2)));
        }

}