package me.andrefma.testearquivo;

import java.util.Arrays;

public class Ordenacao {
    public static String[] bubbleSort(String[] A) {
        for (int i = A.length; i >= 1; i--) {
            for (int j = 1; j < i; j++) {
                if (A[j - 1].length() > A[j].length()) {
                    String aux = A[j];
                    A[j] = A[j - 1];
                    A[j - 1] = aux;
                }
            }
        }
        return A;
    }
    public static String[] selectionSort(String[] A) {
        for (int i = 0; i < A.length; i++) {
            int minIndx = i;
            for (int j = i + 1; j < A.length; j++) {
                if(A[j].length() < A[minIndx].length()) {
                    minIndx = j;
                }
                String aux = A[minIndx];
                A[minIndx] = A[i];
                A[i] = aux;
            }
        }
        return A;
    }
    public static String[] insertionSort(String[] A) {
        for (int i = 1; i < A.length; i++) {
            String key = A[i];
            int j = i - 1;
            while(j >= 0 && A[j].length() > key.length()) {
                A[j + 1] = A[j];
                j = j - 1;
            }
            A[j + 1] = key;
        }
        return A;
    }
    public static String[] mergeSort(String[] A, int low, int high) {
        if (low < high) {
            int middle = (low + high) / 2;
            mergeSort(A, low, middle);
            mergeSort(A, middle + 1, high);
            merge(A, low, middle, high);
        }
        return A;
    }
    private static void merge(String[] A, int low, int middle, int high) {
        String[] aux = new String[A.length];
        for (int i = low; i <= high; i++) {
            aux[i] = A[i];
        }
        int auxL = low;
        int auxR = middle + 1;
        int k = low;
        while (auxL <= middle && auxR <= high) {
            if (aux[auxL].length() <= aux[auxR].length()) {
                A[k] = aux[auxL];
                auxL++;
            }else {
                A[k] = aux[auxR];
                auxR++;
            }
            k++;
        }
        int restante = middle - auxL;
        for (int i = 0; i <= restante; i++) {
            A[k + i] = aux[auxL + i];
        }
    }
    public static int partition(String[] A, int low, int high) {
        int pivot = A[high].length();
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if(A[j].length() <= pivot) {
                i++;
                String aux = A[i];
                A[i] = A[j];
                A[j] = aux;
            }
        }
        String aux = A[i + 1];
        A[i + 1] = A[high];
        A[high] = aux;
        return i + 1;
    }
    public static String[] quickSort(String[] A, int low, int high) {
        if(low < high) {
            int pi = partition(A, low, high);
            quickSort(A, low, pi - 1);
            quickSort(A, pi + 1, high);
        }
        return A;
    }
    public static int buscaBinaria(String[] A, String search) {
        Arrays.sort(A);
        /*Ordena o Vetor[] de forma alfabetica, pois o enunciado pede ordenacao por
        tamanho da String e a buscaBinaria funciona com ordenacao alfabetica*/
        int low = 0;
        int high = A.length - 1;
        int middle;
        while (low <= high) {
            middle = (low + high) / 2;

            if (A[middle].compareTo(search) < 0) {
                low = middle + 1;
            } else if (A[middle].compareTo(search) > 0) {
                high = middle - 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
    public static String buscaSequencial(String[] A, String search) {
        for (int i = 0; i < A.length; i++) {
            if(A[i].equalsIgnoreCase(search)) {
                return search + " está presente no Vetor[] na posição " + i;
            }
        }
        return search + " não está presente no Vetor[]";
    }
    public static void imprimeVetor(String[] A) {
        for(int i = 0; i < A.length; i++) {
            System.out.println(A[i]);
        }
    }
    private static long startMillis;
    private static long startNano;
    private static long finishMillis;
    private static long finishNano;
    public static void startTime() {
        startMillis = System.currentTimeMillis();
        startNano = System.nanoTime();
    }
    public static void finishTime() {
        finishMillis = System.currentTimeMillis() - startMillis;
        finishNano = System.nanoTime() - startNano;
    }
    public static void printTime() {
        System.out.println(finishMillis+" milisegundos\n" + finishNano+" nanosegundos");
    }
}