E aí galera, hoje deixo pra vocês um projeto que ordena números de um arquivo em .CSV contendo várias opções de ordenação contendo:
Entendendo Selection Sort, Insertion Sort, Bubble Sort, Merge Sort, Quick Sort, Heap Sort
Vamos ver detalhes de cada método de ordenação juntamente com seu código fonte feito em java.
Selection Sort
A ordenação por seleção (do inglês, selection sort) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os n-1 elementos restantes, até os últimos dois elementos.
public int[] selectionSort(int[] vetor) {
long tempoinicial = System.currentTimeMillis();
for (int i = 0; i < vetor.length; i++) {
int indiceMinimo = i;
for (int j = i + 1; j < vetor.length; j++) {
if (vetor[j] < vetor[indiceMinimo]) {
indiceMinimo = j;
}
}
int tmp = vetor[indiceMinimo];
vetor[indiceMinimo] = vetor[i];
vetor[i] = tmp;
}
long tempofinal = System.currentTimeMillis();
long tempototal = tempofinal - tempoinicial;
System.out.println("Tempo de Processamento de SelectionSort: " + tempototal + "ms");
return vetor;
}
Fonte: Wikipedia
Insertion Sort
Insertion sort, ou ordenação por inserção, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer.
public int[] insertionSort(int[] vetor) {
long tempoinicial = System.currentTimeMillis();
for (int i = 0; i < vetor.length; i++) {
int atual = vetor[i];
int j = i - 1;
while (j >= 0 && vetor[j] >= atual) {
vetor[j + 1] = vetor[j];
j--;
}
vetor[j + 1] = atual;;
}
long tempofinal = System.currentTimeMillis();
long tempototal = tempofinal - tempoinicial;
System.out.println("Tempo de Processamento de InsertionSort: " + tempototal + "ms");
return vetor;
}
Fonte: Wikipedia
Bubble Sort
O bubble sort, ou ordenação por flutuação (literalmente “por bolha”), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
public int[] bubbleSort(int vetor[]) {
long tempoinicial = System.currentTimeMillis();
for (int i = vetor.length; i >= 1; i--) {
for (int j = 1; j < i; j++) {
if (vetor[j - 1] > vetor[j]) {
int aux = vetor[j];
vetor[j] = vetor[j - 1];
vetor[j - 1] = aux;
}
}
}
long tempofinal = System.currentTimeMillis();
long tempototal = tempofinal - tempoinicial;
System.out.println("Tempo de Processamento de BubbleSort: " + tempototal + "ms");
return vetor;
}
Fonte: Wikipedia
Quick Sort
O Quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves “menores” precedam as chaves “maiores”. Em seguida o Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada.
package arquivoordena;
public class QuickSort {
public static int[] quicksort(int vet[], int ini, int fim) {
int meio;
if (ini < fim) {
meio = partition(vet, ini, fim);
quicksort(vet, ini, meio);
quicksort(vet, meio + 1, fim);
}
return vet;
}
public static int partition(int vet[], int ini, int fim) {
int pivo, topo, i;
pivo = vet[ini];
topo = ini;
for (i = ini + 1; i <= fim; i++) {
if (vet[i] < pivo) {
vet[topo] = vet[i];
vet[i] = vet[topo + 1];
topo++;
}
}
vet[topo] = pivo;
return topo;
}
}
Fonte: Wikipedia
Merge Sort
Sua ideia básica consiste em Dividir (o problema em vários sub-problemas e resolver esses sub-problemas através da recursividade) e Conquistar (após todos os sub-problemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos sub-problemas).
Como o algoritmo Merge Sort usa a recursividade, há um alto consumo de memória e tempo de execução, tornando esta técnica não muito eficiente em alguns problemas .
package arquivoordena;
public class MergeSort {
public static int[] sort(int[] array) {
if (array.length <= 1) {
return array;
}
int meio = array.length / 2;
int[] dir = array.length % 2 == 0 ? new int[meio] : new int[meio + 1];
int[] esq = new int[meio];
int[] aux = new int[array.length];
for (int i = 0; i < meio; i++) {
esq[i] = array[i];
}
int auxIndex = 0;
for (int i = meio; i < array.length; i++) {
dir[auxIndex] = array[i];
auxIndex++;
}
esq = sort(esq);
dir = sort(dir);
aux = mergesort(esq, dir);
return aux;
}
static int[] mergesort(int[] esq, int[] dir) {
int[] aux = new int[esq.length + dir.length];
int indexDir = 0, indexEsq = 0, indexAux = 0;
while (indexEsq < esq.length || indexDir < dir.length) {
if (indexEsq < esq.length && indexDir < dir.length) {
if (esq[indexEsq] <= dir[indexDir]) {
aux[indexAux] = esq[indexEsq];
indexAux++;
indexEsq++;
} else {
aux[indexAux] = dir[indexDir];
indexAux++;
indexDir++;
}
} else if (indexEsq < esq.length) {
aux[indexAux] = esq[indexEsq];
indexAux++;
indexEsq++;
} else if (indexDir < dir.length) {
aux[indexAux] = dir[indexDir];
indexAux++;
indexDir++;
}
}
return aux;
}
}
Fonte: Wikipedia
Heap Sort
O Heapsort não é um algoritmo de ordenação estável. Porém, é possível adaptar a estrutura a ser ordenada de forma a tornar a ordenação estável. Cada elemento da estrutura adaptada deve ficar no formato de um par (elemento original, índice original). Assim, caso dois elementos sejam iguais, o desempate ocorrerá pelo índice na estrutura original.
package arquivoordena;
public class HeapSort {
public static int[] sort(int[] v) {
buildMaxHeap(v);
int n = v.length;
for (int i = v.length - 1; i > 0; i--) {
swap(v, i, 0);
maxHeapify(v, 0, --n);
}
return v;
}
private static void buildMaxHeap(int[] v) {
for (int i = v.length / 2 - 1; i >= 0; i--) {
maxHeapify(v, i, v.length);
}
}
private static void maxHeapify(int[] vetor, int pos, int tamanhoDoVetor) {
int max = 2 * pos + 1, right = max + 1;
if (max < tamanhoDoVetor) {
if (right < tamanhoDoVetor && vetor[max] < vetor[right]) {
max = right;
}
if (vetor[max] > vetor[pos]) {
swap(vetor, max, pos);
maxHeapify(vetor, max, tamanhoDoVetor);
}
}
}
public static void swap(int[] v, int j, int aposJ) {
int aux = v[j];
v[j] = v[aposJ];
v[aposJ] = aux;
}
}
Fonte: Wikipedia
Colocando esses Códigos para Executar
Vamos precisar de uma classe principal para nosso projeto então crie uma classe “ProgramaPrincipal”
package arquivoordena;
import java.io.IOException;
public class ProgramaPrincipal {
public static void main(String[] args) throws IOException {
Arquivo arquivo = new Arquivo();
Ordenacao ordenar = new Ordenacao();
int[] arrayDesordenado = new int[65000];
int[] arrayOrdenado = new int[65000];
arrayDesordenado = arquivo.lerArquivo("C:\\database\\database.txt");
//arrayOrdenado = ordenar.insertionSort(arrayDesordenado);
//arrayOrdenado = ordenar.selectionSort(arrayDesordenado);
//arrayOrdenado = ordenar.bubbleSort(arrayDesordenado);
arrayOrdenado = ordenar.mergeSort(arrayDesordenado);
arrayOrdenado = ordenar.quickSort(arrayDesordenado);
arrayOrdenado = ordenar.heapSort(arrayDesordenado);
arquivo.gravarArquivo("C:\\database\\databaseOrdenada.txt", arrayOrdenado);
}
}
Vamos criar uma classe “Ordenacao” onde irá ficar nossas chamadas das classes.
package arquivoordena;
public class Ordenacao {
public int[] insertionSort(int[] vetor) {
long tempoinicial = System.currentTimeMillis();
for (int i = 0; i < vetor.length; i++) {
int atual = vetor[i];
int j = i - 1;
while (j >= 0 && vetor[j] >= atual) {
vetor[j + 1] = vetor[j];
j--;
}
vetor[j + 1] = atual;;
}
long tempofinal = System.currentTimeMillis();
long tempototal = tempofinal - tempoinicial;
System.out.println("Tempo de Processamento de InsertionSort: " + tempototal + "ms");
return vetor;
}
public int[] selectionSort(int[] vetor) {
long tempoinicial = System.currentTimeMillis();
for (int i = 0; i < vetor.length; i++) {
int indiceMinimo = i;
for (int j = i + 1; j < vetor.length; j++) {
if (vetor[j] < vetor[indiceMinimo]) {
indiceMinimo = j;
}
}
int tmp = vetor[indiceMinimo];
vetor[indiceMinimo] = vetor[i];
vetor[i] = tmp;
}
long tempofinal = System.currentTimeMillis();
long tempototal = tempofinal - tempoinicial;
System.out.println("Tempo de Processamento de SelectionSort: " + tempototal + "ms");
return vetor;
}
public int[] bubbleSort(int vetor[]) {
long tempoinicial = System.currentTimeMillis();
for (int i = vetor.length; i >= 1; i--) {
for (int j = 1; j < i; j++) {
if (vetor[j - 1] > vetor[j]) {
int aux = vetor[j];
vetor[j] = vetor[j - 1];
vetor[j - 1] = aux;
}
}
}
long tempofinal = System.currentTimeMillis();
long tempototal = tempofinal - tempoinicial;
System.out.println("Tempo de Processamento de BubbleSort: " + tempototal + "ms");
return vetor;
}
public int[] mergeSort(int[] array) {
long tempoinicial = System.currentTimeMillis();
array = MergeSort.sort(array);
long tempofinal = System.currentTimeMillis();
long tempototal = tempofinal - tempoinicial;
System.out.println("Tempo de Processamento de MergeSort: " + tempototal + "ms");
return array;
}
public int[] quickSort(int[] array) {
long tempoinicial = System.currentTimeMillis();
array = QuickSort.quicksort(array, 0, (array.length - 1));
long tempofinal = System.currentTimeMillis();
long tempototal = tempofinal - tempoinicial;
System.out.println("Tempo de Processamento de QuickSort: " + tempototal + "ms");
return array;
}
public int[] heapSort(int[] array) {
long tempoinicial = System.currentTimeMillis();
array = HeapSort.sort(array);
long tempofinal = System.currentTimeMillis();
long tempototal = tempofinal - tempoinicial;
System.out.println("Tempo de Processamento de HeapSort: " + tempototal + "ms");
return array;
}
public void imprimirVetor(int[] array) {
for (int counter = 0; counter < (array.length - 1); counter++) {
System.out.println(array[counter]);
}
}
}
Agora vamos criar uma classe “Arquivo”
package arquivoordena;
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.util.StringTokenizer;
public class Arquivo {
public int[] lerArquivo(String endereco) throws FileNotFoundException, IOException {
File arquivo = new File(endereco);
int[] array = new int[65000];
String dadosdatabase = null;
FileReader filereader = new FileReader(arquivo);
BufferedReader bufferreader = new BufferedReader(filereader);
while (bufferreader.ready()) {
dadosdatabase = bufferreader.readLine();
}
int counter = 0;
StringTokenizer databasetoken = new StringTokenizer(dadosdatabase, ";");
while (databasetoken.hasMoreTokens()) {
array[counter] = Integer.parseInt(databasetoken.nextToken());
counter++;
}
bufferreader.close();
filereader.close();
return array;
}
public void gravarArquivo(String endereco, int[] array) throws IOException {
File arquivo = new File(endereco);
try {
if (!arquivo.exists()) {
arquivo.createNewFile();
}
FileWriter fw = new FileWriter(endereco);
BufferedWriter bw = new BufferedWriter(fw);
for (int counter = 0; counter < (array.length - 1); counter++) {
bw.write(array[counter]+";");
//bw.newLine();
}
bw.close();
fw.close();
} catch (IOException ex) {
}
}
}
Classe para gerar números randomicamente
package arquivoordena;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;
public class ArquivoGera {
public static void main(String[] args) throws IOException {
File arquivo = new File("c:\\temp\\arquivo.txt");
if (!arquivo.exists()) {
//cria um arquivo (vazio)
arquivo.createNewFile();
}
//caso seja um diretório, é possÃvel listar seus arquivos e diretórios
File[] arquivos = arquivo.listFiles();
//escreve no arquivo
FileWriter fw = new FileWriter(arquivo, true);
BufferedWriter bw = new BufferedWriter(fw);
//inicializa gerador de numeros aleatórios
Random gerador = new Random();
//gera aleatorio e grava com ;
for (long x=0;x<60000;x++)
bw.write(gerador.nextInt(65000)+";");
bw.newLine();
bw.close();
fw.close();
}
}
Baixar projeto de ordenação
NetBeans: Download
Arquivo com números: Download
Caso você tenha alguma dúvida referente a estes métodos de ordenação, deixe um comentário abaixo.