Efektivita.java

/**
 * Created by IntelliJ IDEA.
 * User: Milan
 * Date: Mar 25, 2010
 * Time: 2:51:22 PM
 */
import java.text.MessageFormat;

public class Efektivita {
    public static int[][] vysledky;
    public static int[] hodnoty = {10, 100, 1000, 10000, 10000, 100000};


    public static void inicializace () {
        vytvoritSoubory();
        provestRazeni();
        vypsatVysledky();
    }

    /**
     * Metoda, ktera vytvori potrebne soubory k mereni efektivity
     */
    private static void vytvoritSoubory () {
        int[] pole;

        vysledky = new int[6][hodnoty.length];      // pocet radku dan natvrdo poctem radicich metod

        for (int hodnota : hodnoty) {
            pole = Pole.vygenerovatPole(hodnota);
            Soubor.zapsatPole(MessageFormat.format("E{0}.txt", Integer.toString(hodnota)), pole);
        }
    }

    private static void provestRazeni () {
        int[] pole;
        long zacatek;

        for (int i = 0; i < vysledky.length; i++) {         // pocet radicich metod
            for (int j = 0; j < hodnoty.length; j++) {      // pocet prvku
                pole = Soubor.nacistPole("E" + hodnoty[j] + ".txt");
                zacatek = System.currentTimeMillis();
                Pole.seraditPole(pole, j);
                vysledky[i][j] = (int) (System.currentTimeMillis() - zacatek);
            }
        }
    }

    private static void vypsatVysledky () {
        for (int i = 0; i < vysledky.length; i++) {
            System.out.print("[");

            for (int j = 0; j < vysledky[i].length; j++) {
                System.out.print(vysledky[i][j]);
                if ((j + 1) != vysledky[i].length) {
                    System.out.print(", ");
                }
            }

            if ((i + 1) != vysledky.length) {
                System.out.println("]");
            } else {
                System.out.println("].");
            }
        }

    }
}

Pole.java

/**
 * Created by IntelliJ IDEA.
 * User: Milan
 * Date: Feb 23, 2010
 * Time: 12:04:11 PM
 */
public class Pole {
    public static int[] pole = new int[0];      // docasne mikro-policko, prepsane pri
                                                // prvnim nacteni/generaci
    /**
     * Vygeneruje jednorozmerne pole se zadanym poctem prvku
     * @param pocet pocet prvku pole
     * @return vygenerovane pole
     */
    public static int[] vygenerovatPole (int pocet) {
        int[] pole = new int[pocet];

        for (int i = 0; i < pole.length; i++) {
            pole[i] = (int) (Math.random() * 1000 + 1);
        }

        return pole;
    }

    /**
     * Vypise predane pole v pevne definovanem formatu
     * @param pole pole k vytisteni
     * @param hlaska popis pole:
     *  0 = vygenerovane pole
     *  1 = nactene pole
     *  2 = serazene pole
     */
    public static void vypsatPole (int[] pole, int hlaska) {
        switch (hlaska) {
            case 0:
                System.out.print("Vygenerovane pole: ");
                break;
            case 1:
                System.out.print("Nactene pole: ");
                break;
            case 2:
                System.out.print("Serazene pole: ");
                break;
            default:
                System.out.print("Pole: ");
                break;
        }

        System.out.print("[");

        for (int i = 0; i < pole.length; i++) {
            System.out.print(pole[i]);

            if ((i + 1) != pole.length) {
                System.out.print(", ");
            }
        }

        System.out.println("].");
    }

    /**
     * "Rozcestnik", ktery zavola zadanou radici metodu
     * @param pole pole k serazeni
     * @param metoda zvolena metoda:
     *  0 = SelectSort
     *  1 = InsertSort
     *  2 = BubbleSort
     *  3 = QuickSort
     *  4 = HeapSort
     *  5 = MergeSort
     */
    public static void seraditPole (int[] pole, int metoda) {
        switch (metoda) {
            case 0:
                provestSelectSort(pole);
                break;
            case 1:
                provestInsertSort(pole);
                break;
            case 2:
                provestBubbleSort(pole);
                break;
            case 3:
                provestQuickSort(pole, 0, (pole.length - 1));
                break;
            case 4:
                provestHeapSort(pole);
                break;
            case 5:
                provestMergeSort(pole);
                break;
            default:
                System.out.println("Nastala chyba, ktera se teoreticky nemuze stat!");
                break;
        }
    }

    /**
     * Seradi zadane pole metodou select sort
     * @param pole pole k serazeni
     */
    private static void provestSelectSort (int[] pole) {
        int poradiMaxima, maximum, zbyvaSeradit;

        for (zbyvaSeradit = (pole.length - 1); zbyvaSeradit >= 1; zbyvaSeradit--) {
            maximum = pole[zbyvaSeradit];
            poradiMaxima = zbyvaSeradit;

            for (int i = 0; i <= zbyvaSeradit; i++) {
                if (pole[i] > maximum) {
                    maximum = pole[i];
                    poradiMaxima = i;
                }
            }

            pole[poradiMaxima] = pole[zbyvaSeradit];
            pole[zbyvaSeradit] = maximum;       // umisteni maxima na "konec" pole
        }
    }

    /**
     * Seradi pole metodou insert sort (bez optimalizaci)
     * @param pole pole k serazeni
     */
    private static void provestInsertSort (int[] pole) {
        int pomocna, j;

        for (int i = 1; i < pole.length; i++) {
            pomocna = pole[i];
            j = i - 1;

            while (j != -1 && pomocna < pole[j]) {
                pole[j + 1] = pole[j];
                j--;
            }

            pole[j + 1] = pomocna;
        }
    }

    /**
     * Seradi pole metodou bubble sort (bez optimalizaci)
     * @param pole pole k serazeni
     */
    private static void provestBubbleSort (int[] pole) {
        int pomocna, zbyvaSeradit = pole.length - 1;

        for (int i = 1; i <= zbyvaSeradit; i++) {
            for (int j = 0; j <= (zbyvaSeradit - i); j++) {
                if (pole[j] > pole[j + 1]) {
                    pomocna = pole[j];
                    pole[j] = pole[j + 1];
                    pole[j + 1] = pomocna;
                }
            }
        }
    }

    /**
     * Seradi pole metodou quick sort
     * @param pole pole k serazeni
     * @param levaHranice leva hranice
     * @param pravaHranice prava hranice
     */
    private static void provestQuickSort (int[] pole, int levaHranice, int pravaHranice) {
        int i, j, pivot, pomocna;
        
        pivot = pole[(levaHranice + pravaHranice) / 2];
        i = levaHranice;
        j = pravaHranice;

        do {
            while (pivot > pole[i]) {
                i++;
            }
            
            while (pivot < pole[j]) {
                j--;
            }

            if (i <= j) {
                pomocna = pole[i];
                pole[i] = pole[j];
                pole[j] = pomocna;
                i++;
                j--;
            }
        } while (i < j);

        if (levaHranice < j) {
            provestQuickSort(pole, levaHranice, j);
        }

        if (i < pravaHranice) {
            provestQuickSort(pole, i, pravaHranice);
        }
    }

    /**
     * Seradi pole metodou heap sort
     * @param pole pole k serazeni
     */
    private static void provestHeapSort (int[] pole) {
        int r, k, pomocna;
        int n = (pole.length - 1);
        k = (n / 2) + 1;
        r = n;

        while (k > 0) {
            k--;
            provestZarazeni(pole, k, r);
        }
        
        while (r > 0) {
            pomocna = pole[0];
            pole[0] = pole[r];
            pole[r] = pomocna;
            r--;
            provestZarazeni(pole, k, r);
        }
    }
    
    private static void provestZarazeni(int[] pole, int k, int r) {
        int i, j, pomocna;
        i = k;
        j = (2 * i);

        if (j == 0) {
            j = 1;
        }

        pomocna = pole[i];

        while (j <= r) {
            if ((j < r) && (pole[j] < pole[j + 1])) {
                j++;
            }
            
            if (pomocna > pole[j]) {
                break;
            }

            pole[i] = pole[j];
            i = j;
            j = (2 * i);
        }

        pole[i] = pomocna;
    }

    /**
     * Seradi pole metodou merge sort
     * @param pole pole k serazeni
     */
    private static void provestMergeSort (int[] pole) {
        int i, j;   // indexy prvku ve zdrojovych polich
        int k, l;   // indexy prvku v cilovych polich
        int pocet;  // pocet prvku p-tice
        int q, r;   // pocty prvku, ktere zbyva sloucit v p-tici
        int m;      // kolik prvku zbyva celkem
        int h;      // smer ukladani v cilovem poli
        int pomocna;
        boolean nahoru;
        int[] pomocnePole = new int[2 * pole.length];  // pomocne pole

        System.arraycopy(pole, 0, pomocnePole, 0, pole.length);

        nahoru = true;
        pocet = 1;

        do {
            h = 1;
            m = pole.length;

            if (nahoru) {
                i = 0;
                j = pole.length - 1;        // pocatecni hodnoty indexu ve zdrojovem poli
                k = pole.length;
                l = 2 * pole.length - 1;    // pocatecni hodnoty indexu v cilovem poli
            } else {
                k = 0;
                l = pole.length - 1;        // pocatecni hodnoty indexu ve zdrojovem poli
                i = pole.length;
                j = 2 * pole.length - 1;    // pocatecni hodnoty indexu v cilovem poli
            }

            do {
                if (m >= pocet) {
                    q = pocet;
                } else {
                    q = m;
                }

                m -= q;

                if (m >= pocet) {
                    r = pocet;
                } else {
                    r = m;
                }

                m -= r;

                while ((q != 0) && (r != 0)) {
                    if (pomocnePole[i] < pomocnePole[j]) {
                        pomocnePole[k] = pomocnePole[i];
                        k += h;
                        i++;
                        q--;
                    } else {
                        pomocnePole[k] = pomocnePole[j];
                        k += h;
                        j--;
                        r--;
                    }
                }

                while (r != 0) {
                    pomocnePole[k] = pomocnePole[j];
                    k += h;
                    j--;
                    r--;
                }

                while (q != 0) {
                    pomocnePole[k] = pomocnePole[i];
                    k += h;
                    i++;
                    q--;
                }

                h = -h;
                pomocna = k;
                k = l;
                l = pomocna;
            } while (m != 0);

            nahoru = !nahoru;
            pocet *= 2;
        } while (pocet < pole.length);

        if (!nahoru) {
            for (i = 0; i < pole.length; i++) {
                pole[i] = pomocnePole[i + pole.length];
            }
        } else {
            for (i = 0; i < pole.length; i++) {
                pole[i] = pomocnePole[i];
            }
        }
    }
}

Projekt.java

/**
 * Created by IntelliJ IDEA.
 * User: Milan
 * Date: Feb 18, 2010
 * Time: 3:29:02 PM
 */
import java.util.Scanner;

public class Projekt1 {
    public static void main (String[] args) {
        char program;

        do {
            vytisknoutMenu();
            program = zvolitPodprogram();
            spustitPodprogram(program);
        } while ((Character.toLowerCase(program) != 'x'));
    }

    /**
     * Metoda zajistujici tisk hlavniho menu programu
     */
    private static void vytisknoutMenu () {
        // wall-o-text incoming
        System.out.print("1. Nacist textovy soubor s celymi cisly do pameti.\n" +
                "2. Generovat urcity pocet nahodnych celych cisel.\n" +
                "3. Ulozit vygenerovane nebo serazene pole do souboru\n" +
                "4. Seradit pole metodou SelectSort.\n" +
                "5. Seradit pole metodou InsertSort.\n" +
                "6. Seradit pole metodou BubbleSort.\n" +
                "7. Seradit pole metodou QuickSort.\n" +
                "8. Seradit pole metodou HeapSort.\n" +
                "9. Seradit pole metodou MergeSort.\n" +
                "0. Porovnat efektivitu ruznych metod na ruznych velikostech souboru.\n" +
                "X. Konec programu.\n" +
                "Volba? ");
    }

    /**
     * Metoda, ktera se uzivatele zepta na volbu podprogramu a overi validitu teto volby
     * Navratova hodnota Z znaci nevalidni volbu
     * @return identifikator podprogramu
     */
    private static char zvolitPodprogram () {
        boolean validniMoznost = false;
        char[] moznosti = {'1', '2', '3', '4', '5', '6', '7', '8', '9', '0', 'x'};
        char program;
        Scanner sc = new Scanner(System.in);
        String radek;

        radek = sc.next();
        program = radek.charAt(0);

        for (char moznost : moznosti) {
            if (Character.toLowerCase(program) == moznost) {
                validniMoznost = true;
            }
        }

        if (!validniMoznost) {
            program = 'Z';
        }

        return program;
    }

    /**
     * "Rozcestnik", ktery spusti vybrany podprogram
     * @param program identifikator podprogramu
     */
    private static void spustitPodprogram (char program) {
        Scanner sc = new Scanner(System.in);
        String nazevSouboru;

        switch (program) {
            case '1':
                System.out.print("Nazev souboru? ");
                nazevSouboru = sc.next();

                Pole.pole = Soubor.nacistPole(nazevSouboru);
                Pole.vypsatPole(Pole.pole, 1);

                break;
            case '2':
                int pocet;

                System.out.print("Pocet prvku pole? ");
                pocet = sc.nextInt();

                Pole.pole = Pole.vygenerovatPole(pocet);
                Pole.vypsatPole(Pole.pole, 0);

                break;
            case '3':
                System.out.print("Nazev souboru? ");
                nazevSouboru = sc.next();

                Soubor.zapsatPole(nazevSouboru, Pole.pole);
                break;
            case '4':
                Pole.seraditPole(Pole.pole, 0);
                Pole.vypsatPole(Pole.pole, 2);
                break;
            case '5':
                Pole.seraditPole(Pole.pole, 1);
                Pole.vypsatPole(Pole.pole, 2);
                break;
            case '6':
                Pole.seraditPole(Pole.pole, 2);
                Pole.vypsatPole(Pole.pole, 2);
                break;
            case '7':
                Pole.seraditPole(Pole.pole, 3);
                Pole.vypsatPole(Pole.pole, 2);
                break;
            case '8':
                Pole.seraditPole(Pole.pole, 4);
                Pole.vypsatPole(Pole.pole, 2);
                break;
            case '9':
                Pole.seraditPole(Pole.pole, 5);
                Pole.vypsatPole(Pole.pole, 2);
                break;
            case '0':
                Efektivita.inicializace();
                break;
            case 'z':
            case 'Z':
                System.out.println("Neplatna volba! Vracim zpet!");
                break;
        }
    }
}

Soubor.java

/**
 * Created by IntelliJ IDEA.
 * User: Milan
 * Date: Mar 25, 2010
 * Time: 1:21:56 PM
 */
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.text.MessageFormat;

public class Soubor {
    /**
     * Nacte pole ze souboru
     * @param nazevSouboru nazev souboru obsahujici pole
     * @return nactene pole
     */
    public static int[] nacistPole (String nazevSouboru) {
        File ukazatel = new File(MessageFormat.format("src{0}pole{1}{2}", File.separator,
                File.separator, nazevSouboru));
        String radek;
        String[] poleZnaku;
        int[] poleCisel;
        
        try {
            FileReader soubor = new FileReader(ukazatel);
            BufferedReader ctecka = new BufferedReader(soubor);

            radek = ctecka.readLine();
            poleZnaku = radek.split(" ");
            poleCisel = new int[poleZnaku.length];

            for (int i = 0; i < poleZnaku.length; i++) {
                poleCisel[i] = Integer.parseInt(poleZnaku[i]);
            }

            ctecka.close();
        } catch (FileNotFoundException e) {
            poleCisel = new int[0];
            System.out.println("Soubor neexistuje: " + e.getLocalizedMessage() + "!");
        } catch (IOException e) {
            poleCisel = new int[0];
            System.out.println("Ze souboru nelze cist: " + e.getLocalizedMessage() + "!");
        }

        return poleCisel;
    }

    /**
     * Zapise do zadaneho souboru zadane pole
     * @param nazevSouboru nazev souboru, do nejz se bude zapisovat
     * @param pole pole, jenz ma byt zapsano
     */
    public static void zapsatPole (String nazevSouboru, int[] pole) {
        File ukazatel = new File(MessageFormat.format("src{0}pole{1}{2}", File.separator,
                File.separator, nazevSouboru));

        try {
            FileWriter soubor = new FileWriter(ukazatel);
            BufferedWriter zapisovacka = new BufferedWriter(soubor);

            for (int i = 0; i < pole.length; i++) {
                zapisovacka.write(Integer.toString(pole[i]));

                if ((i + 1) != pole.length) {
                    zapisovacka.write(" ");
                }
            }

            zapisovacka.close();
        } catch (IOException e) {
            System.out.println("Neco se zeslonilo: " + e.getLocalizedMessage() + "!");
        }
    }
}