Algoritmos de Ordenação em Java

Neste artigo veremos como aplicar algoritmos de ordenação em Java, dada a sua devida necessidade em ocasiões específicas. Existem diversas aplicabilidades para a ordenação de dados, não só em Java, mas no mundo computacional como um todo.

A ideia de conhecer diversos algoritmos para ordenar dados é saber qual utilizar para conseguir um melhor desempenho ou uma melhor legibilidade de código, dependendo da necessidade. Não precisamos usar, por exemplo, um algoritmo “supercomplexo“ para ordenar 10 valores em um vetor, certo? Seria desperdício de tempo desenvolver um algoritmo tão complexo para resolver um problema tão simples.

Para analisar um algoritmo de ordenação você deve conhecer a sua complexidade no Pior Caso, Caso Médio e o melhor caso. Estas três características presentes em todos os algoritmos dizem respeito a sua velocidade dada uma situação específica. Atente-se a esses conceitos, pois falaremos deles posteriormente, citando a complexidade do algoritmo através de notação matemática.

Algoritmos de Ordenação

InsertionSort

Sua teoria baseia-se em ordenar os valores da esquerda para a direita, deixando os elementos lidos (a esquerda) ordenados. Este é geralmente utilizado para ordenar um pequeno número de valores, onde faz-se muito eficiente. A complexidade do código é:

• Complexidade Pior Caso: O(n²)
• Complexidade Caso Médio: O(n²)
• Complexidade Melhor Caso: O(n)

Quando temos um caso onde a complexidade é n² devemos evitar, visto que a redução de desempenho deste algoritmo é exponencial. Porém, no seu melhor caso temos uma constante n que significa a inalteração da velocidade, proporcional à quantidade de elementos.

Lembre-se que estamos trabalhando com proporcionalidade, então dizer que não varia não significa que um vetor de 10 elementos será ordenado na mesma velocidade de um vetor de um milhão de elementos, mesmo no melhor caso, porém a proporcionalidade entre a quantidade de elementos e sua velocidade continua constante, diferente do Pior Caso que aumenta ao quadrado.

O melhor caso ocorre quando todos os elementos já estão ordenados e o pior caso é exatamente o contrário, quando todos os elementos estão desordenados. Vejamos um exemplo para entender melhor essa teoria na Listagem 1.

O primeiro passo é entender o funcionamento do método insertionSort(). Este irá percorrer todo o vetor começando do segundo elemento e atribuindo o mesmo a uma variável chamada key.

O algoritmo começa fazendo uma iteração em todos os elementos do vetor, a partir do segundo elemento, por isso j=1 e não j=0.

A variável key armazena inicialmente o primeiro valor lido pelo laço for, que no caso será o segundo elemento do vetor. O segundo laço itera sobre os valores que estão antes da variável key:

Perceba que a iteração mostrada continuará até que o valor de i seja maior ou igual a zero e o valor do vetor na posição i seja maior que o valor de key.

Suponha o seguinte vetor: 30,20,10,40. Na primeira iteração o valor de key será 20, já que começamos a iteração a partir do segundo valor. Na primeira iteração do segundo laço for o valor de i será igual a 0, porque o j será igual a 1, sendo assim o i é >= 0 e o vetor[0] é maior que 20, pois vetor[0] = 30. Ao acessar o segundo laço for é feita uma atribuição.

Temos então que vetor[0+1] = vetor[0], ou seja, o valor 20 recebe o valor 30, ficando assim: 30,30,10,40. Quando ele tentar passar pela segunda vez no segundo laço for não será possível, pois i será -1.

Ao sair do segundo laço for o valor de vetor[i+1] recebe o que tínhamos armazenado em key.

No caso, vetor[-1 + 1] = 20, então temos 20, 30, 10, 40.

O mesmo prossegue até que todos os valores do vetor sejam percorridos e estejam ordenados.

A variável i serve para comparar sempre o elemento atual com o elemento anterior, pois ele faz com que seja possível percorrer todos os elementos anteriores ao atual até achar algum que seja maior que o atual, fazendo com que este seja substituído. Conforme a iteração for avançando os elementos a esquerda vão ficando ordenados.

Vejamos agora o que foi feito dentro do método main(), que será usado durante todo o desenvolvimento deste artigo.

O método main() possui uma iteração para preencher elementos de forma randômica:

Após o preenchimento destes elementos é chamado o método insertionsort(), que irá ordenar os valores, sendo que antes e depois são gravadas variáveis do System.currentTimeMillis() para saber-se qual tempo de execução do algoritmo em milissegundos.

O código da Listagem 1 representa o caso médio, onde alguns valores podem já estar ordenados e outros não, visto que usamos o Math.random() e não saberemos qual vetor será construído. Para testar o melhor caso você deve trocar a linha mencionada por:

Vejamos na Tabela 1 os tempos médios: como o pior caso e o caso médio possuem a mesma complexidade decidimos fazer a análise de apenas um destes.

Tabela 1. Medição de Tempo para InsertionSort

O que podemos perceber na tabela é que no caso médio temos uma alteração exponencial, aumentando muito o tempo conforme o aumento do número de elementos. Ao analisar os tempos você verá um aumento considerável quando trabalhamos comn². Por outro lado, no melhor caso o tempo mantem-se quase constante, enquanto temos 20.272 ms para 200.000 no caso Médio, temos 8 ms para a mesma quantidade no melhor Caso.

BubbleSort

O BubbleSort é conhecido pela sua simplicidade e pela eficácia ao realizar ordenações em um número limitado de valores. Seu princípio baseia-se na troca de valores entre posições consecutivas, fazendo com que valores altos ou baixos (dependendo da forma de ordenação desejada) “borbulhem” para o final da fila, por isso este algoritmo é chamado de BubbleSort. Sua complexidade é:

• Complexidade Pior Caso: O(n²)
• Complexidade Caso Médio: O(n²)
• Complexidade Melhor Caso: O(n)

Vimos que no melhor caso o seu tempo é quase inalterável, permanecendo constante, ou seja, um caso ideal.

Vejamos a implementação do bubbleSort na Listagem 2.

Veja que o primeiro passo é criar as variáveis que nos auxiliarão na ordenação dos valores. Um laço while() é criado e executado enquanto o valor de troca for true, e logo na primeira iteração já configuramos essa variável como false (você entenderá mais à frente o porquê).

O laço for percorre o primeiro elemento até o último elemento -1 (ele nunca chegará a ler o último elemento) verificando se o elemento atual que está sendo lido é maior que o próximo elemento que será lido.

Suponhamos então o seguinte vetor: 20, 10, 30.

A primeira iteração no laço for irá capturar o valor 20 e comparar com o próximo, que será 10. Então se 20 > 10, ele entrará na condição fazendo a substituição destes valores:

O valor 20, que está na posição i é armazenado na variável aux para não perdemos sua referência, depois o valor 10 que está na posição i+1 é armazenado no local do valor 20. Trocamos agora o valor de i+1 pelo valor que armazenamos em aux, que no caso é 20. A variável troca que antes era false, agora recebe true para indicar que houve uma troca.

Na segunda iteração do laço for o valor 20 será capturado, pois estaremos com i = 1. O valor 20 será comparado com o valor de i+1 (2), que no caso é o valor 30. Então se 20 > 30 a troca será realizada. Como 20 não é maior que 30 não entraremos na condição e o laço for continuará a ser executado, agora na próxima iteração, onde i = 2.

Quando i = 2 já estamos no último elemento, então não entrará no laço for, já que i não é menor que vetor.length – 1. Se fosse possível entrar no último elemento para realizar comparações o seguinte erro aconteceria:

Isso porque não podemos realizar a operação de comparação do último elemento com um próximo elemento, já que ele não existe.

Porque a variável troca é útil? Ao passar pela primeira vez no vetor de elementos qualquer troca que for realizada ativa a variável troca como true, fazendo com que ele precise passar novamente depois da leitura de todos os elementos. A ideia é passar quantas vezes forem necessárias até que a variável troca não seja mais ativada, assim saberemos que todos os elementos estão devidamente ordenados.

Analisando mais a fundo o algoritmo BubbleSort você perceberá que a segunda passada geralmente será muito mais rápida que a primeira, principalmente se todo o vetor já foi ordenado corretamente, fazendo com que nenhuma vez seja necessário realizar trocas, assim o mesmo entra no “melhor caso”, ou seja, todos os valores ordenados.

Analisando a Tabela 2 podemos perceber que até 1000 elementos o BubbleSort é eficiente e realiza a ordenação de forma eficaz, porém com valores maiores já se torna mais lento. No melhor caso quase não há alteração para o tempo de resposta deste algoritmo, visto que ele apenas passará dentro do laço for sem entrar nenhuma vez na condição para realizar a troca de elementos.

QuickSort

Este algoritmo usa uma técnica conhecida por divisão e conquista, muito conhecida por reduzir problemas complexos em problemas menores para tentar chegar em uma solução. Sendo assim, o resultado do problema inicial é dada como a soma do resultado de todos os problemas menores. Sua complexidade é:

• Complexidade Pior Caso: O(n²)
• Complexidade Caso Médio: (nlogn)
• Complexidade Melhor Caso: (nlogn)

O QuickSort sai na frente de outros algoritmos mais simples quando tratamos do caso médio, por trabalhar com logaritmo (nlogn), o que torna o resultado mais rápido do que o InsertionSort e o QuickSort.

O algoritmo consiste nos seguintes passos:

1. Escolhe-se um elemento qualquer da lista, que será chamado de pivô.
2. Todos os elementos antes do pivô devem ser menores que ele e todos os elementos após o pivô devem ser maiores que ele. Quando esse processo de separação for finalizado, então o pivô deve estar exatamente no meio da lista.
3. De forma recursiva os elementos da sublista menor e maiores são ordenados.

Seu algoritmo pode ser visto na Listagem 3.

O primeiro passo é separar as listas, como havíamos citado anteriormente. No método separar() esse processo é realizado até que seja retornado um pivô, ou seja, o elemento divisível entre as duas listas.

Finalizado o processo de separação então é chamado um próprio método quickSort() de forma recursiva, onde ele fará o processo de separação interna dentro da sublista e assim será feito até que todos os elementos estejam ordenados.

Se você preferir, na Listagem 4 também temos um pseudocódigo que exemplifica o funcionamento do QuickSort em linguagem genérica.

O QuickSort é um algoritmo mais robusto e complexo que os mostrados anteriormente, por isso achamos importante exemplificar o seu uso através do pseudocódigo.

Vejamos na Tabela 3 a comparação entre o tempo de execução.

Veja que o tempo de processamento do QuickSort é muito bom quando tratamos do caso médio, que é exatamente o nosso caso (randômico). Veja que o tempo para 200.000 registros é muito eficiente, muito mais que os mostrados anteriormente para este tipo de caso.

SelectionSort

No InsertionSort vimos uma ordenação simples, já no SelectionSort a implementação torna-se mais simples ainda, porém perdemos muito com o desempenho. Este algoritmo tem por objetivo passar sempre o menor valor para a primeira posição (dependendo da ordem requerida pode ser o maior valor). Então, para que isso seja feito ele percorre todos os elementos procurando um menor valor para só então colocá-lo na primeira posição, repetindo essa tarefa para cada um dos elementos.

• Complexidade Pior Caso: O(n²)
• Complexidade Caso Médio: O(n²)
• Complexidade Melhor Caso: O(n²)

Perceba que este algoritmo possui um péssimo desempenho, visto que sua complexidade é sempre exponencial, independente do caso em que estamos trabalhando. Antes mesmo de mostrar qualquer código você já deve ser capaz de perceber que este algoritmo é bom para trabalhar-se comaté, pelo menos, 10.000 elementos, dada a tabela do InsertionSort, visto sua simplicidade na implementação.

Vejamos a implementação do selectionsort na Listagem 5.

O SelectionSort guarda a posição do menor elemento na variável “menor” e percorre o array procurando por um valor menor. Caso este valor seja encontrado então a variável “menor” recebe a posição deste valor. Por último é checado se a posição do menor elemento é diferente da posição atual, se isso for verdade então é feita uma troca de valores, colocando o menor elemento na frente.

Vamos entender o passo a passo do algoritmo apresentado: começamos com o laço for, que percorre todos os elementos, guardando o valor da iteração atual na variável “fixo”. Em seguida usamos uma variável auxiliar chamada menor que guardará o valor de fixo.

Tendo em mãos a variável menor, que na primeira iteração é igual ao primeiro elemento do vetor, percorremos (através de outro laço for) todos os elementos do array partindo do segundo elemento até o último.Então imagine a situação, se temos o array com as posições 0,1,2,3 a variável menor guardará o valor '0' e o segundo laço irá percorrer os elementos na posição 1,2,3.

A cada vez que um elemento for visitado, no segundo laço for, é feita uma comparação se o elemento atual é menor que o elemento que está na posição indicada pela variável menor. Se isso for verdade então a variável menor recebe o valor de i, ou seja, a nova posição do menor elemento será o atual lido.

Se a variável menor guarda a posição do menor elemento, então sempre que um elemento menor que o menor atual for encontrado, a posição do menor será alterada para o atual.

No final do segundo laço for teremos na variável menor a posição do menor elemento lido, se esta posição for diferente da posição atual que está na variável fixo então faremos uma troca.

Lembre-se que a variável fixo guarda a posição do elemento que está sendo lido no primeiro laço for, e a variável menor guarda a posição do menor elemento encontrado em todo o vetor. Sendo assim, se ambos forem diferentes capturamos o valor contido na posição da variável “fixo” e armazenamos na variável “t”, apenas para não perder o valor. Depois colocamos o valor do elemento na posição da variável “menor” dentro da posição da variável “fixo”. O que temos até agora é que o menor elemento está na primeira posição do vetor e também em outra posição, ou seja, na sua original, agora precisamos colocar o valor de “t” dentro da posição antiga do menor elemento.

Suponha o seguinte vetor: 20,30,40, 10. Na primeira execução do algoritmo acima a posição “0” (valor 20) é gravada na variável fixo, e a variável menor também recebe “0”. Em seguida, no segundo laço for, é verificado se 30 menor que 20, 40 é menor que 20 e 10 é menor que 20. Como 10 é menor que 20, então a variável menor recebe o valor 3 que corresponde a posição do menor elemento do vetor.

Como o valor de menor (3) é diferente do fixo (0) então ocorre a troca:

10,30,40,10.

Quando colocamos o valor de “t” na posição antiga da variável menor, obtemos o seguinte:

10,30,40,20.

Quando ocorrer a segunda iteração do primeiro laço do algoritmo a leitura se dará a partir do valor 30, então a lista considerada será: 30,40,20. Isso será feito até que não reste mais nenhum elemento a ser lido.

Tabela 4. Medição de Tempo para SelectionSort

Percebemos através da análise da Tabela 4 que independentemente do caso o tempo é quase igual, ainda exponencial. Se trabalharmos com uma pequena quantidade de elementos (100 a 1000) é quase imperceptível mas para uma grande quantidade isso pode trazer graves consequências de performance.

Com isso, vimos que em se tratando de simplicidade, o BubbleSort é o melhor, visto que sua implementação e lógica são simples e eficazes para uma pequena quantidade de valores, porém precisamos de algoritmos mais robustos quando sabemos que a entrada se dará para uma grande quantidade de valores.

Por outro lado, o InsertionSort não é tão complexo quanto o QuickSort, mas também não é tão simples quanto o BubbleSort, acrescentando um pouco mais de robustez e consequentemente desempenho na ordenação de valores. O InsertionSort é um meio termo e possibilita a ordenação de valores um pouco maiores que o BubbleSort, mas também não consegue ordenar uma grande quantidade de valores igual ao QuickSort, que por sua vez, mostrou-se o algoritmo mais rápido de todos e consequentemente o mais complexo de ser implementado. Isso ocorre principalmente pelo fato de ele trabalhar com recursos como recursividade para alcançar um desempenho notável.

É perceptível que o QuickSort, BubbleSort e InsertionSort possuem quase o mesmo tempo de resposta quando estamos tratando com até 1000 elementos no vetor, a variação é tão insignificante que a escolha de um destes algoritmos é mais uma questão pessoal do que profissional.

Ao trabalhar com uma quantidade de valores maior, já percebemos que algoritmos simples podem não ser a melhor escolha, você mesmo pode fazer um teste tentando executar o BubbleSort para um milhão de elementos. Se para 200.000 elementos o tempo de resposta foi quase 82 segundos e o mesmo cresce de forma exponencial, então para um milhão de elementos possivelmente chegará perto ou passará (dependendo do hardware) de horas.