Boa tarde!
Preciso de uma ajudinha de vocês. É o seguinte, o algoritmo abaixo para cada método que está comentado deveria me retornar o número de comparações que o algoritmo faz para ordenar os números em cada um dos métodos de ordenação.
Para o método de seleção (ordena) está ok. Já o inserção(insertionSort),o bolha(bubbleSort) e o quickSort não me é retornada a quantidade de comparações executadas para ordenação.
public class JavaApplication4 {
static int i, j, tamanho;
public static void ordena(int arranjo[]) {
int i, j, menor, aux;
int contador = 0;
for (i = 0; i < tamanho - 1; i++) {
menor = i;
for (j = i + 1; j < tamanho; j++) {
contador++;
if (arranjo[j] < arranjo[menor]) {
menor = j;
}
}
aux = arranjo[menor];
arranjo[menor] = arranjo[i];
arranjo[i] = aux;
}
System.out.println("\n\ncontador = " + contador);
}
public static void insertionSort(int[] vetor) {
int j;
int key;
int i = 0;
int aux;
int menor = 0;
int contador = 0;
for (j = 1; j < vetor.length; j++) {
key = vetor[j];
for (i = j - 1; (i >= 0) && (vetor[i] > key); i--) {
vetor[i + 1] = vetor[i];
}
vetor[i + 1] = key;
}
aux = vetor[menor];
vetor[menor] = vetor[i];
vetor[i] = aux;
System.out.println("\n\ncontador = " + contador);
}
public static void bubbleSort(int vetor[]) {
boolean troca = true;
int aux;
int contador = 0;
while (troca) {
troca = false;
for (int i = 0; i < vetor.length - 1; i++) {
contador++;
if (vetor[i] > vetor[i + 1]) {
aux = vetor[i];
vetor[i] = vetor[i + 1];
vetor[i + 1] = aux;
troca = true;
}
}
System.out.println("\n\ncontador = " + contador);
}
}
private static void quickSort(int[] vetor, int inicio, int fim) {
if (inicio < fim) {
int posicaoPivo = separar(vetor, inicio, fim);
quickSort(vetor, inicio, posicaoPivo - 1);
quickSort(vetor, posicaoPivo + 1, fim);
}
}
private static int separar(int[] vetor, int inicio, int fim) {
int pivo = vetor[inicio];
int i = inicio + 1, f = fim;
while (i <= f) {
if (vetor[i] <= pivo)
i++;
else if (pivo < vetor[f])
f--;
else {
int troca = vetor[i];
vetor[i] = vetor[f];
vetor[f] = troca;
i++;
f--;
}
}
vetor[inicio] = vetor[f];
vetor[f] = pivo;
return f;
}
public static void main (String[] args) {
int vetor[];
tamanho = 10000;
vetor = new int[tamanho];
Random gerador = new Random();
for (i = 0; i < tamanho; i++) {
vetor[i] = i;
}
System.out.println();
for (i = 0; i < tamanho; i++) {
System.out.print(" " + vetor[i]);
}
//CHAMA O METODO QUE SERÁ EXECUTADO
quickSort(vetor);
System.out.println();
for (i = 0; i < tamanho; i++) {
System.out.print(" " + vetor[i]);
}
System.out.println("\n");
}
private static void quickSort(int[] vetor) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
}
}