A5

import java.util.Arrays;

public abstract class TriediaciAlgoritmus {

        /**
         * Aktualne usporiadavane pole
         */
        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);
}

import java.util.Arrays;

public class mergeSort extends TriediaciAlgoritmus {

        public void merge(int odIdx, int poIdx) {
                if (odIdx >= poIdx) {
                        return;
                }
                int stred = (odIdx + poIdx) / 2;
                merge(odIdx, stred);
                merge(stred + 1, poIdx);
                int index1 = odIdx;
                int index2 = stred + 1;
                int indexVPoli = 0;
                int p[] = new int[poIdx - odIdx + 1];
                while (index1 <= stred && index2 <= poIdx) {
                        if (porovnaj(index1, index2) < 0) {
                                p[indexVPoli] = this.p[index1];
                                index1++;
                        } else {
                                p[indexVPoli] = this.p[index2];
                                index2++;
                        }
                        indexVPoli++;
                }
                if (index1 <= stred) {
                        for (int i = index1; i <= stred; i++) {
                                p[indexVPoli] = this.p[i];
                                indexVPoli++;
                        }
                } else {
                        for (int i = index2; i <= poIdx; i++) {
                                p[indexVPoli] = this.p[i];
                                indexVPoli++;
                        }
                }
                System.arraycopy(p, 0, this.p, odIdx, p.length);

        }

        @Override
        protected void utried(int dlzkaPola) {
                merge(0, dlzkaPola - 1);

        }

        public static void main(String[] args) {
                int[] p = { 1, 3, 1 };
                System.out.println(Arrays.toString(p));
                mergeSort ms = new mergeSort();
                ms.utried(p);
                System.out.println(Arrays.toString(p));
        }

}
 

import java.util.Arrays;

public class Halda {
        private int[]p;


        public Halda(int[] p) {

                this.p = p;
        }

        public void halduj(int idxKorena, int idxKoniec) {
                while(true){
                int idxLavy = 2 * idxKorena + 1;
                int idxPravy = 2 * idxKorena + 2;
                int pozMax = idxKorena;
                if(idxLavy <= idxKoniec){
                        if(p[idxKorena] < p[idxLavy]){
                                pozMax = idxLavy;
                        }
                }

                if(idxPravy <= idxKoniec){
                        if(p[pozMax] < p[idxPravy]){
                                pozMax = idxPravy;
                        }
                }

                if(pozMax == idxKorena){
                        return;
                } else {
                        vymen(idxKorena, pozMax);
                        idxKorena = pozMax;
                }
        }
                }

        public void vymen(int idx1, int idx2) {
                int pom = p[idx1];
                p[idx1] = p[idx2];
                p[idx2] = pom;

        }

        public void vytvorHaldu() {
                for (int i = p.length -1; i >= 0; i--) {
                        halduj(i, p.length - 1);
                }

        }

        public void usporiadajHaldovanim() {
                vytvorHaldu();
                for (int i = p.length -1; i > 0; i--) {
                        vymen(i, 0);
                        halduj(0, i - 1);
                }

        }

        public static void main(String[] args) {
                int []p = {7,6,5,4,3,2,1};
                Halda h = new Halda(p);
                h.usporiadajHaldovanim();
                System.out.println(Arrays.toString(p));

        }

}