package faculdade;
import java.util.Random;
public class Ordenacao {
public static long comparacao;
public static long movimentacao;
public static void main(String() args) {
int() vetor = new int(1000);
fill(vetor);
System.out.println("Vetor criado:");
// show(vetor);
// tempo inicial
long tempoInicial = System.currentTimeMillis();
//selectionSort(vetor);
bubbleSort(vetor);
//insertionSort(vetor);
//quickSort(vetor, 0, vetor.length - 1);
// tempo final
long tempoFinal = System.currentTimeMillis();
System.out.println("Executado em = " + (tempoFinal - tempoInicial) + " ms");
System.out.println("n Comparações: " + comparacao + " Movimentaçoes: " + movimentacao);
System.out.println("Finalizado.");
}
public static void selectionSort(int() vetor) {
comparacao = 0;
movimentacao = 0;
for (int i = 0; i < vetor.length - 1; i++) {
int menor = i;
for (int j = i + 1; j < vetor.length; j++) {
comparacao++;
if (vetor(j) < vetor(menor)) {
comparacao++;
menor = j;
}
}
swap(vetor, i, menor);
// show(vetor);
movimentacao++;
}
}
public static void bubbleSort(int() vetor) {
movimentacao = 0;
comparacao = 0;
for (int i = vetor.length; i >= 1; i--) {
for (int j = 1; j < i; j++) {
if (vetor(j - 1) > vetor(j)) {
swap(vetor, j, j-1);
comparacao++;
}
}
show(vetor);
}
}
public static void insertionSort(int() vetor) {
comparacao = 0;
movimentacao = 0;
for (int i = 1; i < vetor.length; i++) {
int current = vetor(i);
int j = i - 1;
while (j >= 0 && current < vetor(j)) {
vetor(j + 1) = vetor(j);
j--;
comparacao++;
}
// at this point we've exited, so j is either -1
// or it's at the first element where current >= a(j)
vetor(j + 1) = current;
}
show(vetor);
movimentacao++;
}
public static void quickSort(int vetor(), int esquerda, int direita) {
int esq = esquerda;
int dir = direita;
int pivo = vetor((esq + dir) / 2);
int troca;
while (esq <= dir) {
while (vetor(esq) < pivo) {
esq = esq + 1;
}
while (vetor(dir) > pivo) {
dir = dir - 1;
}
if (esq <= dir) {
troca = vetor(esq);
vetor(esq) = vetor(dir);
vetor(dir) = troca;
esq = esq + 1;
dir = dir - 1;
movimentacao++;
}
comparacao++;
}
if (dir > esquerda) {
quickSort(vetor, esquerda, dir);
}
if (esq < direita) {
quickSort(vetor, esq, direita);
}
}
public static void fill(int() vetor) {
Random r = new Random();
for (int i = 0; i < vetor.length; i++) {
vetor(i) = r.nextInt(100);
}
}
public static void show(int() vetor) {
for (int i = 0; i < vetor.length; i++) {
System.out.print(vetor(i) + " ");
}
System.out.println("");
}
public static void swap(int() vetor, int a, int b) {
int aux = vetor(a);
vetor(a) = vetor(b);
vetor(b) = aux;
movimentacao++;
}
}
At runtime, the comparison number corresponds to the train number. I think that's wrong
