Atividade 01 - TAP II

/*
 * @Ano: 2013/2
 * @Escola: Pontifícia Universidade Católica do Paraná
 * @Curso: Engenharia de Computação
 * @Autor: Luis Henrique de Souza, Maicon Augusto Tibola
 */

package br.pucpr;

import java.io.*;
import java.util.Scanner;

    public class MainCls {
        static char vet[];
        static long timeInicial;
        static String dir = "";
        static int tam[] = { 1024, 10240, 102400, 512000, 1048576, 2097152 };
        static long comparacoes = 0, trocas = 0;
        static Scanner scanner = new Scanner(System.in);

        public static void selectMetodo() throws IOException {
            int opcMet = 0, opcTam = 0;

            System.out.println("Criar arquivo de:");
            System.out.println("<1> 1K | <2> 10K | <3> 100K | <4> 500K | <5> 1M | <6> 2M | <0> Arquivo existente");
            System.out.print("Arquivo: ");
            opcTam = scanner.nextInt();

            if (opcTam == 0) {
                System.out.print("Arquivo: ");
                opcTam = scanner.nextInt();

                lerArquivo(opcTam);
            } else {
                criarArquivo(opcTam);
                lerArquivo(opcTam);
            }

            System.out.println("Informe o método desejado:");
            System.out.println("(1) Buble Sort, (2) QuickSort, (3) HeapSort, (4) MergeSort");
            System.out.print("Método: ");
            opcMet = scanner.nextInt();

            timeInicial = System.currentTimeMillis();
            switch (opcMet) {
            case 1:
                bubbleSort(vet);
                System.out.println("\nBubble Sort:");
                imprimirDados();
                break;
            case 2:
                quickSort(vet, 0, vet.length - 1);
                System.out.println("\nQuick Sort:");
                imprimirDados();
                break;
            case 3:
                heapSort(vet);
                System.out.println("\nHeap Sort:");
                imprimirDados();
                break;
            case 4:
                mergeSort(vet, 0, vet.length - 1);
                System.out.println("\nMerge Sort:");
                imprimirDados();
                break;
            default:
                System.out.println("Opção inválida.");
            }

            gravarArquivo(opcTam);
            System.out.println("Arquivo salvo: " + dir);
        }

    public static void criarArquivo(int n) throws IOException {
        int imp = 0, i;

        dir = "C:/temp/" + tam[n - 1] + ".txt";
        FileWriter arq = new FileWriter(dir);
        PrintWriter gravarArq = new PrintWriter(arq);

        for (i = 0; i < tam[n - 1]; i++) {
            imp = (int) (Math.random() * 10);
            gravarArq.print(imp);
        }
        arq.close();
    }


    public static void lerArquivo(int n) throws IOException {
        try{
        dir = "C:/temp/" + tam[n - 1] + ".txt";
        BufferedReader buf = new BufferedReader(new FileReader(dir));
        String line = "", l;
        while ((l = buf.readLine()) != null) {
            line += l;
        }
        vet = line.toCharArray();
        }catch(Exception erro){
            System.out.println(erro.getMessage() + "\n");
            System.exit(0);
        }
    }

    public static void gravarArquivo(int n) throws IOException {
        dir = "C:/temp/" + tam[n - 1] + "_organizado.txt";
        FileWriter arq = new FileWriter(dir);
        PrintWriter gravarArq = new PrintWriter(arq);

        gravarArq.print(vet);
        arq.close();
    }

    public static void imprimirDados() {
        System.out.println("Comparações: " + comparacoes + "\nTrocas: " + trocas);
        System.out.println("Tempo: " + (System.currentTimeMillis() - timeInicial) + "ms");
    }

    // BUBBLE SORT \\
    public static void bubbleSort(char v[]) {
        char aux = 0;
        int i, j;

        for (i = 0; i < v.length; i++) {
            for (j = 0; j < (v.length - 1); j++) {
                comparacoes++;
                if (v[j] > v[j + 1]) {
                    trocas++;
                    aux = v[j];
                    v[j] = v[j + 1];
                    v[j + 1] = aux;
                }
            }
        }
    }

    // QUICK SORT \\
    private static void quickSort(char[] input, int start, int end) {
        int currStart = start, currEnd = end;
        int pivot = input[start + (end - start) / 2];

        while (currStart <= currEnd) {
            comparacoes++;
            while (input[currStart] < pivot) {
                comparacoes++;
                currStart++;
            }

            while (input[currEnd] > pivot) {
                comparacoes++;
                currEnd--;
            }

            if (currStart <= currEnd) {
                trocas++;
                char temp = input[currStart];
                input[currStart] = input[currEnd];
                input[currEnd] = temp;
                currStart++;
                currEnd--;
            }
        }

        if (start < currEnd)
            quickSort(input, start, currEnd);

        if (currStart < end)
            quickSort(input, currStart, end);
    }

    // HEAP SORT \\
    public static void heapSort(char v[]) {
        buildMaxHeap(v);
        int n = v.length;

        for (int i = v.length - 1; i > 0; i--) {
            comparacoes++;
            swap(v, i, 0);
            maxHeapify(v, 0, --n);
        }
    }

    private static void buildMaxHeap(char v[]) {
        for (int i = v.length / 2 - 1; i >= 0; i--) {
            comparacoes++;
            maxHeapify(v, i, v.length);
        }
    }

    private static void maxHeapify(char v[], int pos, int n) {
        int maxi;
        int l = 2 * pos + 1;
        int right = 2 * pos + 2;
        if ((l < n) && (v[l] > v[pos])) {
            maxi = l;
        } else {
            maxi = pos;
        }
        if (right < n && v[right] > v[maxi]) {
            maxi = right;
        }
        if (maxi != pos) {
            swap(v, pos, maxi);
            maxHeapify(v, maxi, n);
        }
    }

    public static void swap(char v[], int j, int aposJ) {
        trocas++;
        char aux = v[j];
        v[j] = v[aposJ];
        v[aposJ] = aux;
    }

    // MERGE SORT \\
    private static void mergeSort(char v[], int start, int end) {
        int mid = (start + end) / 2;
        if (start < end) {
            mergeSort(v, start, mid);
            mergeSort(v, mid + 1, end);
            merge(v, start, mid, end);
        }
    }

    private static void merge(char v[], int start, int mid, int end) {
        char inputCopy[] = new char[v.length];
        int firstArrStart = start, secondArrStart = mid + 1;
        for (int i = start; i <= end; i++) {
            inputCopy[i] = v[i];
        }
        while (secondArrStart <= end && firstArrStart <= mid) {
            comparacoes++;
            if (inputCopy[firstArrStart] >= inputCopy[secondArrStart]) {
                trocas++;
                v[start++] = inputCopy[secondArrStart++];
            } else {
                trocas++;
                v[start++] = inputCopy[firstArrStart++];
            }
        }
        while (firstArrStart <= mid) {
            comparacoes++;
            v[start++] = inputCopy[firstArrStart++];
        }
        while (secondArrStart <= end) {
            comparacoes++;
            v[start++] = inputCopy[secondArrStart++];
        }
    }

    public static void main(String[] args) throws IOException {
        selectMetodo();
    }
}