Efektivita.java

/**
 * Created by IntelliJ IDEA.
 * User: Milan Vit
 * Date: Mar 25, 2010
 * Time: 2:51:22 PM
 */

import java.text.MessageFormat;

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

	/**
	 * Verejna metoda, ktera inicializuje mereni efektivity
	 */
	public static void inicializace () {
		vytvoritSoubory ();
		provestRazeni ();
		vypsatVysledky ();
	}

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

		vysledky = new long[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);
		}
	}

	/**
	 * Spusti vsechny radici metody na vsech velikostech pole
	 */
	private static void provestRazeni () {
		int[] pole;
		long zacatek;
		long konec;

		for (int i = 0; i < vysledky.length; i++) {
			for (int j = 0; j < hodnoty.length; j++) {
				pole = Soubor.nacistPole (MessageFormat.format ("E{0}.txt", Integer.toString (hodnoty[j])));

				zacatek = System.nanoTime ();
				Pole.seraditPole (pole, i);
				konec = System.nanoTime ();

				vysledky[i][j] = (konec - zacatek);
			}
		}
	}

	/**
	 * Vypise vysledky mereni efektivity radicich algoritmu
	 */
	private static void vypsatVysledky () {
		System.out.format ("%1$-15s", "Radici metoda");

		for (int i = 0; i < hodnoty.length; i++) {
			System.out.format ("%15s", hodnoty[i] + " prvku");

			if ((i + 1) == hodnoty.length) {
				System.out.println ();
			}
		}

		for (int i = 0; i < vysledky.length; i++) {
			switch (i) {
				case 0:
					System.out.format ("%-15s", "Select sort");
					break;
				case 1:
					System.out.format ("%-15s", "Insert sort");
					break;
				case 2:
					System.out.format ("%-15s", "Bubble sort");
					break;
				case 3:
					System.out.format ("%-15s", "Quick sort");
					break;
				case 4:
					System.out.format ("%-15s", "Heap sort");
					break;
				case 5:
					System.out.format ("%-15s", "Merge sort");
					break;
				default:
					System.out.format ("%-15s", "Huh?");
			}

			for (int j = 0; j < vysledky[i].length; j++) {
				System.out.format ("%15d", vysledky[i][j]);

				if ((j + 1) == vysledky[i].length) {
					System.out.println ();
				}
			}
		}

		System.out.println ("Vysledky jsou uvedeny v nanosekundach.");
	}
}

Pole.java

/**
 * Created by IntelliJ IDEA.
 * User: Milan Vit
 * Date: Feb 23, 2010
 * Time: 12:04:11 PM
 */

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

Projekt1.java

/**
 * Created by IntelliJ IDEA.
 * User: Milan Vit
 * 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 Vit
 * 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;

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 () + "!");
		}
	}
}