APS - ALGORITMOS DE ORDENAÇÃO DE DADOS - 2017

Prévia do material em texto

21
Universidade Paulista
Ciência da computação
Atividade Prática Supervisionada
ALGORÍTMOS DE ORDENAÇÃO DE DADOS
Lucas Colleone Pexe 
Bauru
2017-2
Sumário
1. Objetivo do Trabalho	3
2. Introdução	4
3. Referencial Teórico	6
3.1. Algoritmo de ordenação	6
3.2. Algoritmo Quicksort	6
3.2.1. Complexidade	8
3.2.2. Análise de QuickSort	8
3.2.3. Vantagens	8
3.2.4. Desvantagens	8
3.3. Algoritmo Bubble Sort	8
3.3.1. Complexidade	10
3.3.2. Análise de BubbleSort	10
3.3.3. Vantagens	10
3.3.4. Desvantagens	10
3.4. Algoritmo Selection Sort	10
3.4.1. Complexidade	12
3.4.2. Vantagens	12
3.4.3. Desvantagens	12
4. Desenvolvimento	13
 4.1. 1º CASO - Obtenção de dados através do usuário 	13
 4.2. 2º CASO - Dados gerados de forma aleatório pelo programa 	18
5. Resultado e Discussão	23
5.1. Dados aleatórios 	23
6. Considerações Finais	24
Referência Bibliográfica	25
Anexos – Código Fonte	28
	
Objetivo do trabalho
O objetivo desse trabalho consiste em estudar os algoritmos de ordenação de dados e toda teoria computacional envolvida. Após pesquisa bibliográfica sobre o assunto em questão o grupo deverá escolher 2 algoritmos de ordenação para implementar e comparar o desempenho entre eles. A unidade de medida para efeito de comparação do desempenho dos algoritmos escolhidos e implementados deverá ser o tempo total de ordenação, não contabilizando o tempo de aquisição dos dados, mas somente a ordenação em si. Os algoritmos escolhidos para implementação e comparação neste trabalho tratam-se do Bubble Sort, Selection Sort e Quick Sort, os quais serão implementados na linguagem de programação JAVA.
Introdução
Ordenar indica o processo de rearranjar um conjunto de objetos ou informações em uma ordem ascendente ou descendente. A atividade de colocar as coisas em ordem está presente na maioria das aplicações em que os objetos e informações armazenados precisam ser pesquisados e recuperados.
O objetivo principal da ordenação é facilitar a recuperação posterior de itens do conjunto ordenado. Imagine como seria difícil utilizar um catálogo telefônico se os nomes das pessoas não estivessem listados em ordem alfabética. O mesmo pode ser dito com relação a dicionários, índices de livros, folhas de pagamento, contas bancárias, tabelas, arquivos e outros materiais organizados alfabeticamente, portanto, evidencia-se que a conveniência de usar dados ordenados é inquestionável. 
Os tipos de ordenação mais usados conhecidos são: Ordenação por troca, Ordenação por inserção, Ordenação por seleção, entre outros.
Em ordenação por troca existem os algoritmos: BubbleSort (método da bolha) e QuickSort (método da troca e partição); Na ordenação por inserção, existem os algoritmos: InsertionSort (método da inserção direta) e BinaryInsertionSort (método da inserção direta binária); Na ordenação por seleção, os algoritmos são: SelectionSort (método da seleção direta) e HeapSort (método da seleção em árvore). Existem ouros métodos como o: MergeSort (método da intercalação) e o BucketSort (método da distribuição de chave).
Cada um desses algoritmos faz a ordenação de maneiras diferentes, possuindo suas vantagens e desvantagens as quais devem ser consideradas conforme a aplicação que se destinam. Para decidir que método é o melhor, certos critérios de eficiência têm que ser estabelecidos, e um método para comparar diferentes algoritmos precisa ser selecionado. 
	Para tornar a comparação independente da máquina, certas propriedades críticas dos algoritmos de ordenação precisam ser definidas quando comparados, como o número de comparações e o número de movimentos de dados. Para ordenar um conjunto de dados, eles têm que ser comparados e movidos conforme necessário; a eficiência dessas duas operações depende do tamanho do conjunto de dados. 
Os métodos de ordenação são classificados através de sua complexidade (O) e são em geral, classificados em dois grandes grupos: métodos de ordenação interna (vetores) e métodos de ordenação externa (arquivos). Se o arquivo a ser ordenado é pequeno, ou seja, cabe todo na memória principal então o método ordenador é chamado de ordenação interna. Em um método de ordenação interna, qualquer registro pode ser imediatamente acessado. Se o arquivo a ser ordenado não cabe na memória principal e por isso tem de ser armazenado em fita ou disco, então o método de ordenação é chamado de ordenação externa. Em um método de ordenação externa, os registros são acessados sequencialmente ou em grandes blocos.
	Existem os métodos simples, que são ideais para conjuntos pequenos, requerem O(n2) comparações, produzem programas pequenos e fáceis de entender; e existem métodos eficientes que são adequados para conjuntos maiores, requerem O(n log n) comparações, usam menos comparações e essas comparações são mais complexas nos detalhes.
A proposta deste trabalho consiste justamente em estudar com maior profundidade o assunto de ordenação e os algoritmos envolvidos, bem como suas características principais. Esse estudo será abordado no capítulo 3 o qual consiste do referencial teórico. Após o referencial teórico, será abordado no capítulo 4 o desenvolvimento dos algoritmos escolhidos pelo grupo, depois no capítulo 5 os resultados e discussões, isto é, como foram aplicados os testes e sobre o desempenho obtido pelos algoritmos, etc. No capítulo 6 o grupo apresentará as considerações finais e o seu entendimento sobre tudo que foi feito. E finalmente as referências para esta pesquisa e o código dos algoritmos desenvolvidos como anexo.
3. Referencial Teórico
Este capítulo aborda a teoria envolvida na proposta deste trabalho.
3.1. Algoritmo de ordenação
Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem - em outras palavras, efetua sua ordenação completa ou parcial (MARCOS LAUREANO, 2012). O objetivo da ordenação é facilitar a recuperação dos dados de uma lista.
Existem vários algoritmos de ordenação, mas para este trabalho foram escolhidos para estudo os algoritmos de ordenação: Bubble Sort, Selection Sort, Quick Sort e Insertion Sort. E desses serão implementados os algoritmos Bubble Sort e Quick Sort. (DEVMEDIA, 2012).
3.2. Algoritmo Quicksort
De acordo com BAASE (1988), o Quicksort adota a estratégia de divisão e conquista, a qual 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. Os passos para essa ordenação são:
1. Escolha um elemento da lista, denominado pivô;
2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição;
3. Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;
A base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.
Há dois índices, i e j, e bem no início do algoritmo i aponta para o primeiro elemento no vetor e j aponta para o último. Em seguida, o algoritmo move o i para frente, até um elemento com valor maior ou igual ao pivô é encontrado. O índice j é movido para trás, até que um elemento com valor inferior ou igual ao pivô seja encontrado. Se i<=j então eles são trocados e i passa para a próxima posição (i+1), j passa para a posição anterior (j-1). O algoritmo termina quando i se torna maior do que j.
Após o particionamento, todos os valores anteriores ao elemento i são inferiores ou iguais ao pivô e todos os valores posteriores ao elemento j são maiores ou iguais ao pivô.
A forma como o algoritmo funciona pode ser resumida na seguinte estratégia: O QuickSort divide sualista de entrada em duas sub-listas a partir de um pivô, em seguida realiza o mesmo procedimento nas duas listas menores até o caso trivial, onde terá uma lista unitária. (GUIMARÃES, 2013)
Segue exemplo abaixo:
· Ordenando {1, 12, 5, 26, 7, 14, 3, 7, 2} usando quicksort.
3.2.1. Complexidade
Em média, o quicksort possui O (n log n) de complexidade, mas nos piores casos, o quicksort roda em O (n²) de tempo, mas nos mais "práticos" dados ele funciona bem e superior à outros O (n log n) algoritmos de ordenação.
É recomendado que o algoritmo de partição seja usado como uma função separada, por exemplo, a utilização de duas funções, uma de partição e outra de ordenação que utiliza a de partição.
3.2.2. Análise QuickSort
· Pior caso: C(n) = O (n2)
O pior caso ocorre quando, sistematicamente, o pivô é escolhido como sendo um dos extremos de um arquivo já ordenado.
Isto faz com que o procedimento ordena seja chamado recursivamente n vezes, eliminando apenas um item em cada chamada. 
· Melhor caso: C(n) = 2C(n/2) + n = n log n
Esta situação ocorre quando cada partição divide o arquivo em duas partes iguais.
3.2.3. Vantagens
· Vantagens: Necessita de apenas uma pequena pilha como memória auxiliar. Requer cerca de n log n comparações em média para ordenar n itens. Memória auxiliar para a pilha de recursão é pequena e complexidade no caso médio é O(n lg(n)).
3.2.4. Desvantagens
· Desvantagens: Sua implementação é muito delicada e difícil. Um pequeno engano pode levar a efeitos inesperados para algumas entradas de dados. O método não é estável.
3.3. Algoritmo Bubble Sort
Bubble sort é um do mais simples algoritmo de ordenação de dados, conhecido como ordenação por flutuação (Bolha). 
De acordo com Prof. Jesus Menachalco (2016), o princípio da bolha é a troca de valores entre posições consecutivas fazendo com que os valores mais altos “borbulhem” para o final do vetor. O algoritmo basicamente compara dois elementos e troca a posição dos mesmos, assim de forma consecutiva vai colando o elemento de maior valor no final do vetor e de menor valor no início. Esse algoritmo usa a ordem quadrática (O(n²)). Portanto, ele não é usado em programas onde o intuito é aumentar a velocidade e que utilizam uma quantidade muito alta de dados.
O algoritmo Bubble Sorte primeiro compara cada par de elementos adjacentes do início do vetor e se eles estiverem na ordem reversa, troca eles de lugar. Se ao menos uma troca foi feita, repete o primeiro passo.
Para fácil entendimento, podemos observar no exemplo abaixo a forma em que o algoritmo funciona.
Segue exemplo abaixo:
· Ordenando {5, 1, 12, -5, 16} usando Bubble Sort.
3.3.1. Complexidade
Em casos de complexidade mediana ou alta, o bubble sort possui desempenho de O (n²). Assim como, ele efetua O (n²) trocas nos piores casos. Bubble sort é adaptativo. Isso significa que em vetores quase ordenados seu desempenho estimado é O(n). Evite implementações que não confiram se o vetor já está ordenado em cada passo (qualquer troca feita). Essa checagem é necessária, em ordem para preservar propriedades adaptativas.
3.3.2. Análise BubbleSort
· Pior caso: o algoritmo realizará N-1 trocas para o primeiro passo, depois N-2 trocas para o segundo, e assim por diante até 1 troca. Exemplo: Trocas = N-1 + N-2 + N-3 + ... +2 + 1; Aproximadamente N² trocas.
· Melhor caso: nenhuma troca será realizada. Exemplo: Em ambos os casos, bubblesort faz da ordem de N² comparações, apenas bubblesort2 faz N-1 comparações no melhor caso.
3.3.3. Vantagens
· Vantagens: Algoritmo simples e estável. Os elementos são trocados de lugar sem utilizar armazenamento temporário, o que faz o requerimento de espaço ser mínimo.
3.3.4. Desvantagens
· Desvantagens: O fato de o arquivo já estar ordenado não ajuda a reduzir o número de comparações (o custo continua quadrático), porém o número de movimentações cai para zero.
3.4. Algoritmo Selection Sort
O Selection Sort ou Ordenação por Seleção, é um dor algoritmos de classificação O(n2), o que o torna bastante ineficiente para classificar grandes volumes de dados. O Selection Sort é notável por sua simplicidade de programação, e pode superar outros métodos de ordenação em determinadas situações (ver análise de complexidade para mais detalhes).
Este algoritmo é baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o segundo menor valor para a segunda posição e assim sucessivamente, até os últimos dois elementos. (HONORATO. 2017)
A ideia de algoritmo é bastante simples. Imagine um array dividido em duas partes – ordenado e não classificado. No início, a parte classificada está vazia, enquanto não escolhida, uma contém toda a matriz. Em cada passo, o algoritmo encontra um elemento mínimo na parte selecionada e o adiciona ao final do ordenado. Quando a parte não selecionada fica vazia, o algoritmo para. Quando o algoritmo classifica uma matriz, ele troca o primeiro elemento da parte selecionada com um elemento mínimo e então este é incluído na parte classificada.
Segue exemplo abaixo:
· Ordenando {5, 1, 12, -5, 16, 2, 12, 14} usando Selection Sort.
3.4.1. Complexidade
O selection sort compara a cada interação um elemento com os outros, visando encontrar o menor. Dessa forma, podemos entender que não existe um melhor caso mesmo que o vetor ordenado ou em ordem inversa serão executados os dois laços do algoritmo, o externo e o interno. A complexidade deste algoritmo será sempre O(n^2) enquanto que, por exemplo, os algoritmos heapsort e mergesor possuem complexidades O(n log n). 
3.4.2. Vantagens
· Não necessita de um vetor auxiliar (in-place).
· Por não usar um vetor auxiliar para realizar a ordenação, ele ocupa menos memória.
· Ele é uns dos mais velozes na ordenação de vetores de tamanhos pequenos.
3.4.3. Desvantagens 
· Ele é um dos mais lentos para vetores de tamanhos grandes.
· Ele não é estável.
· Ele faz sempre {\displaystyle n^{2}}n^2 comparações, independente do vetor está ordenado ou não.
4. Desenvolvimento
Após estudo bibliográfico o grupo implementou e comparou os algoritmos Bubble Sort, Quick Sort e Selection Sort. 
4.1. 1°CASO – Obtenção de Dados através do usuário
Na tela inicial do programa, é requisitado o modo de obtenção de dados. Caso digite 1, os dados serão obtidos através da inserção pelo usuário, caso contrário, os dados serão gerados de forma aleatória. Na figura 1, a opção escolhida é a 1.
Figura 1
Agora na Figura 2 logo abaixo, é requisitado pelo programa que o usuário digite um número, para ser armazenado e depois usado para a ordenação.
 	 	 Figura 2
Neste momento, o programa deseja saber se o usuário quer continuar digitando mais valores ou encerrar, caso digite qualquer tecla, o programa irá pedir que digite outro valor, mas se o N for digitado, será encerrado o processo de obtenção de dados. Segue exemplo na figura 3.
 Figura 3
Caso a opção digitada for N, o usuário será apresentado a essa tela que está presente na Figura 4, na qual o programa estará requisitando a opção para selecionar o modo de ordenação em que os valores serão ordenados. Se o usuário digitar 1, será utilizado o Bubble Sort, caso digite 2, será utilizado o Selection Sort e se for digitado o 3, será utilizado o Quick Sort. Nesse caso, a opção informada pelo usuário é o Bubble Sort, de número 1.
 Figura 4
Após isso, serão apresentados na tela final (Figura 5) o número total de índices informados pelo usuário, a ordem original de seus valores, a ordem final, obtida após a ordenação pelo método selecionado e o tempo total decorrido durante a ordenação dos dados.
Figura 5
4.2. 2°CASO – Dados gerados de forma aleatório pelo programa
Na tela inicial do programa, é requisitado o modo de obtenção de dados. Caso digite 1, os dados serão obtidos através da inserção pelo usuário, caso contrário, os dados serão gerados de forma aleatória. Na figura 6 a seguir, a opção escolhida é a 2.
 Figura 6
Na Figura 7 a seguir, o programa irá requisitar que o usuário digite a quantidade de númerosa serem gerados de forma aleatória. Neste exemplo, a quantidade de números a serem gerados será de 100.
Figura 7
Como no primeiro caso, o programa está requisitando que o usuário informe o método de ordenação que irá ser utilizado para a ordenação do vetor. Se o usuário digitar 1, será utilizado o Bubble Sort, caso digite 2, será utilizado o Selection Sort e se for digitado o 3, será utilizado o Quick Sort. Nesse caso, a opção informada pelo usuário é o Selection Sort, de número 2. Segue na Figura 8 a seguir.
Figura 8
Por último, como no primeiro caso, nas figuras 9 e 10 seguintes serão apresentados o número total de índices gerados de forma aleatória, a ordem original de seus valores, a ordem final, obtida após a ordenação pelo método selecionado e o tempo total decorrido durante a ordenação dos dados.
Figura 9
Figura 10
A apresentação dos resultados comparativos entre os métodos e diferentes casos estará contida no próximo tópico.
5. Resultados e Discussão
Os resultados que serão apresentados a seguir foram obtidos através de um computador com processador AMD Phenom(tm) II X6 3.30GHz e memória RAM DDR2 de 16GB.
5.1. Dados Aleatórios
	ALEATÓRIO
	DEZ
	CEM
	MIL
	DEZ MIL
	CEM MIL
	BUBBLE SORT
	0
	0
	8
	194
	18086
	SELECTION SORT
	0
	0
	4
	78
	7565
	QUICK SORT
	0
	0
	0
	3
	14
Valores na escala de milissegundos (ms)
Na condição de dados em ordem aleatória, o Bubble Sort obteve de longe o pior desempenho, 2 vezes mais demorado para ordenar mil números, quase 3 vezes para ordenar dez mil e quase 3 vezes mais para ordenar cem mil em comparação com o segundo da lista, o Selection Sort. E como melhor desempenho bem acima dos demais se encontra o Quick Sort.
6. Considerações Finais
No trabalho foi apresentado o que são métodos de ordenação, alguns dos mais conhecidos, foi explicado como funcionam, seus desempenhos e foram também aplicados na prática em um programa. 
Em relação aos desempenhos dos métodos, o algoritmo Bubble Sort, apesar de ser o de mais fácil implementação, não apresenta resultados satisfatórios, principalmente no número de comparações. A ineficiência desse algoritmo pode ser traduzida como um grande consumo de processamento, o que, para máquinas com poucos (ou limitados) recursos computacionais, resulta em lentidão e longos períodos de espera. Sua aplicação é, na opinião dos autores, indicada somente para fins educacionais, visto que um projeto com o mesmo pode ser considerado ineficiente e/ou fraco (SILVA, 2010).
O Selection Sort torna-se útil em estruturas lineares com o número de elementos consideravelmente maior, o número de trocas é muito inferior ao número de comparações, consumindo, assim, mais tempo de leitura e menos de escrita. A vantagem de seu uso ocorre quando se trabalha com componentes em que, quanto mais se escreve, ou reescreve, mais se desgasta, e consequentemente perdem sua eficiência.
O algoritmo Quick Sort, ao subdividir o vetor e fazer inserções diretas utilizando um valor de referência (pivô), reduz seu tempo de execução, mas as quantidades de comparações (leitura) e principalmente trocas (escrita) ainda são muito altas. Apesar disso, o Quick Sort se apresenta uma boa opção para situações em que o objetivo é a execução em um menor tempo, mesmo que para isso haja um detrimento em recursos computacionais de processamento.
Após estudo bibliográfico que o grupo implementou e comparou os algoritmos, o que obteve o melhor desempenho no decorrer do trabalho foi algoritmo Quick Sort.
Referências bibliográficas
AZEREDO, Paulo A. Métodos de Classificação de Dados e Análise de suas Complexidades. Rio de Janeiro: Campus, 1996
BAASE, Sara. Computer Algorithms: Introduction to Design and Analysis (em inglês). 2ª ed. Reading, Massachusetts: Addison-Wesley, 1988. 53 p
CORMEMN, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C.; Algoritmos. Tradução da 2ª edição americana Teoria e Prática. 2002.
DEVMEDIA; Algoritmos de ordenação: análise e comparação. Disponível em: <http://www.devmedia.com.br/articles/viewcomp.asp?comp=28261>. Acesso em: Nov/2017.
Mello, R.S. Ordenação de Dados, 2002. Disponível em: <http://www.inf.uri.com.br/neilor/apostila-ED2.pdf>. Acesso em: Nov/2017.
ALGOLIST; Algorithms and Data Structures, 2009. Disponível em: <http://www.algolist.net/Algorithms/Sorting/Bubble_sort>. Acesso em: Nov/2017.
ALGOLIST; Algorithms and Data Structures, 2009. Disponível em: <http://www.algolist.net/Algorithms/Sorting/Quicksort>. Acesso em Nov/2017.
NETSOFT; Algoritmos e Estruturas de Dados, 2017. Disponível em: <http://www.netsoft.inf.br/aulas/2_ESW_Estruturas_de_Dados/quicksort_analise.pdf>. Acesso em: Nov/2017.
UNICAMP; Algoritmos e Programação de Computadores, 2017. Disponível em: <http://www.lis.ic.unicamp.br/~mc102/files/mc102jk-a17-4pp.pdf>. Acesso em Nov/2017.
USP; Métodos de Ordenação, 2011. Disponível em: <http://wiki.icmc.usp.br/images/b/b3/SCC501Cap4.pdf>. Acesso em Nov/2017.
EMBARCADOS; Algoritmos de Ordenação: Bubble Sorthttps, 2017. Disponível em: <www.embarcados.com.br/algoritmos-de-ordenacao-bubble-sort/>. Acesso em: Nov/2017.
KHANACADEMY; Visão geral do Quicksort, 2017. Disponível em: <https://pt.khanacademy.org/computing/computerscience/algorithms/quicksort/a/overview-of-quicksort>. Acesso em: Nov/2017.
USP; Análise do algoritmo Quicksort, 2015. Disponível em> <https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/quick.html>. Acesso em: Nov/2017.
Silva, E. S. “Estudo Comparativo de Algoritmos de Ordenação. ” 33 f. Trabalho de Conclusão de Curso – Universidade Federal do Espírito Santo, São Mateus, 2010.
MENACHALCO, Jesus. "Algoritmos e Estruturas de Dados" Aula 05º, 2016. Disponível em:<http://professor.ufabc.edu.br/~jesus.mena/courses/mcta001-1q2017/AED105.pdf>. Acesso em: Nov/2017
LAUREANO, Marcos. "Estrutura de Dados com Algoritmos e C", pg. 100, 2012. Disponível em: <http://www.mlaureano.org/livro/livro_estrutura_conta.pdf>. Acesso em: Nov/2017.
GUIMARÃES, Gleyser. “História da Computação: O Algoritmo Quicksort”, 2013. Disponível em: <http://www.dsc.ufcg.edu.br/~pet/jornal/abril2013/materias/historia_da_computacao.html> Acesso em: Nov/2017.
HONORATO, Bruno. “Algoritmos de ordenação: análise e comparação”, 2017. Disponível em: <http://www.devmedia.com.br/articles/viewcomp.asp?comp=28261>. Acesso em: Nov/2017.
ANEXOS - Código Fonte
· CÓDIGO
package aps;
import javax.swing.JOptionPane;
import java.util.ArrayList;
public class APS {
 //Bubble Sort
 
 static void Bubblesort(int[] vetor) {
 int n = vetor.length;
 int MenorNumero;
 for (int i = 0; i < n; i++) {
 for (int j = 1; j < (n - i); j++) {
 if (vetor[j - 1] > vetor[j]) {
 MenorNumero = vetor[j - 1];
 vetor[j - 1] = vetor[j];
 vetor[j] = MenorNumero;
 }
 }
 }
 }
 public static int[] SelectSort(int[] Vetor) {
 for (int i = 0; i < Vetor.length - 1; i++) {
 int aux = i;
 for (int j = i + 1; j < Vetor.length; j++) {
 if (Vetor[j] < Vetor[aux]) {
 aux = j;
 }
 }
 int MenorNumero = Vetor[aux];
 Vetor[aux] = Vetor[i];
 Vetor[i] = MenorNumero;
 }
 return Vetor;
 }
//QuickSort e 2 metodos 
 
 int dividir(int vetor[], int esq, int dir) {
 int i = esq, j = dir;
 int tmp;
 int pivot = vetor[(esq + dir) / 2];
 while (i <= j) {
 while (vetor[i] < pivot) {
 i++;
 }
 while (vetor[j] > pivot) {
 j--;
 }
 if (i <= j) {
 tmp = vetor[i];
 vetor[i] = vetor[j];
 vetor[j] = tmp;
 i++;
 j--;
 }
 }
 return i;
 }
 void quickSort(int vetor[], int esq, int dir) {
 int index = dividir(vetor, esq, dir);if (esq < index - 1) {
 quickSort(vetor, esq, index - 1);
 }
 if (index < dir) {
 quickSort(vetor, index, dir);
 }
 }
 public static void main(String[] args) {
 String continuar = "", opcao = "";
 int contador = 0, i, n;
 long time = 0;
 ArrayList vetororiginal = new ArrayList();
 do {
 opcao = JOptionPane.showInputDialog("Digite 1 - para escolher os números // 2 - para usar números aleatórios");
 if (!opcao.equals("1") && !opcao.equals("2")) {
 JOptionPane.showMessageDialog(null, "Opção inexistente, digite novamente");
 }
 } while (!opcao.equals("1") && !opcao.equals("2"));
 if (opcao.equals("1")) {
 while (!continuar.equals("n")) {
 vetororiginal.add(Integer.parseInt(JOptionPane.showInputDialog("Digite um número")));
 contador++;
 continuar = JOptionPane.showInputDialog("Continuar? Pressione qualquer tecla para sim ou N para nao");
 }
 n = contador;
 int vetorordenado[] = new int[n];
 for (i = 0; i < n; i++) {
 vetorordenado[i] = Integer.parseInt(vetororiginal.get(i).toString());
 }
 do {
 opcao = JOptionPane.showInputDialog("Digite 1 - Bubble Sort, 2 - Selection Sort ou 3 - Quick Sort");
 if (!opcao.equals("1") && !opcao.equals("2") && !opcao.equals("3")) {
 JOptionPane.showMessageDialog(null, "Opção inexistente, digite novamente");
 }
 } while (!opcao.equals("1") && !opcao.equals("2") && !opcao.equals("3"));
 if (opcao.equals("1")) {
 Cronometro.start();
 Bubblesort(vetorordenado);
 Cronometro.stop();
 time = Cronometro.elapsedTime();
 } else {
 if (opcao.equals("2")) {
 Cronometro.start();
 SelectSort(vetorordenado);
 Cronometro.stop();
 time = Cronometro.elapsedTime();
 } else {
 APS ordenarQuick = new APS();
 Cronometro.start();
 ordenarQuick.quickSort(vetorordenado, 0, n - 1);
 Cronometro.stop();
 time = Cronometro.elapsedTime();
 }
 }
 System.out.println("v[i] = Original, Ordenado");
 System.out.println("-------------------------");
 for (i = 0; i < vetororiginal.size(); i++) {
 System.out.printf("v[%d] = %8s, %8d\n", i, vetororiginal.get(i).toString(), vetorordenado[i]);
 }
 System.out.println("");
 System.out.println("Tempo de ordenação: " + time + "ms");
 } //aleatorio
 else {
 n = Integer.parseInt(JOptionPane.showInputDialog("Digite a quantidade de números aleatórios"));
 int x;
 int vetorordenado[];
 vetorordenado = new int[n];
 for (i = 0; i < n; i++) {
 x = (int) Math.round(Math.random() * n); //o resultado desta expressao sera um numero
 vetororiginal.add(x); // no intervalo de 0 ate 100
 vetorordenado[i] = x;
 }
 do {
 opcao = JOptionPane.showInputDialog("Digite 1 para Bubble Sort, 2 para Selection Sort ou 3 para Quick Sort");
 if (!opcao.equals("1") && !opcao.equals("2") && !opcao.equals("3")) {
 JOptionPane.showMessageDialog(null, "Opção inexistente, digite novamente");
 }
 } while (!opcao.equals("1") && !opcao.equals("2") && !opcao.equals("3"));
 if (opcao.equals("1")) {
 Cronometro.start();
 Bubblesort(vetorordenado);
 Cronometro.stop();
 time = Cronometro.elapsedTime();
 } else {
 if (opcao.equals("2")) {
 Cronometro.start();
 SelectSort(vetorordenado);
 Cronometro.stop();
 time = Cronometro.elapsedTime();
 } else {
 APS ordenarQuick = new APS();
 Cronometro.start();
 ordenarQuick.quickSort(vetorordenado, 0, n - 1);
 Cronometro.stop();
 time = Cronometro.elapsedTime();
 }
 }
 System.out.println("v[i] = Original, Ordenado");
 System.out.println("-------------------------");
 for (i = 0; i < vetororiginal.size(); i++) {
 System.out.printf("v[%d] = %8s, %8d\n", i, vetororiginal.get(i).toString(), vetorordenado[i]);
 }
 System.out.println("");
 System.out.println("Tempo de ordenação: " + time + "ms");
 }
 }
}
· CRONOMETRO 
package aps;
public final class Cronometro {
 private static long startValue;
 private static long stopValue;
 private static long timeDiff;
 /**
 *
 * Inicia a contagem temporal
 *
 */
 public static void start() {
 startValue = System.currentTimeMillis();
 stopValue = 0;
 timeDiff = 0;
 }
 /**
 *
 * Calcula a diferença temporal
 *
 */
 public static void stop() {
 stopValue = System.currentTimeMillis();
 timeDiff = stopValue - startValue;
 }
 /**
 *
 * Retorna o diferença de tempo medida
 *
 * @return tempo em milisegundos
 *
 */
 public static long elapsedTime() {
 return timeDiff;
 }
}
Ordenação dos Algoritmos em ms
BUBBLE SORT	DEZ	CEM	MIL	DEZ MIL	CEM MIL	0	0	8	194	18086	SELECTION SORT	DEZ	CEM	MIL	DEZ MIL	CEM MIL	0	0	4	78	7565	QUICK SORT	DEZ	CEM	MIL	DEZ MIL	CEM MIL	0	0	0	3	14