A classificação é uma das operações básicas que executamos em objetos. Mesmo na infância, as crianças são ensinadas a classificar à medida que desenvolvem suas habilidades de pensamento. Computadores e software não são exceção. Há uma enorme variedade de algoritmos de classificação em Java . Sugiro que você verifique o que são e como funcionam. E se algum dia você for questionado sobre um deles em uma entrevista?
Introdução
Ordenar elementos é uma das categorias de algoritmos que um desenvolvedor deve conhecer. Se a ciência da computação não era levada a sério quando eu estava na escola, os alunos de hoje devem ser capazes de implementar e entender os algoritmos de classificação. Algoritmos básicos, os mais simples, são implementados usando um loop for . Naturalmente, para classificar uma coleção de elementos, como um array, você precisa passar pela coleção de alguma forma. Por exemplo:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
O que pode ser dito sobre esse segmento de código? Temos um loop no qual mudamos o índice ( int i) de 0 para o último elemento do array. Na verdade, estamos simplesmente pegando cada elemento do array e exibindo seu conteúdo. Quanto mais elementos no array, mais tempo o código levará para terminar. Ou seja, se né o número de elementos, quando n = 10o programa levará o dobro do tempo para ser executado do que quando n = 5. Se nosso programa tiver um único loop, o tempo de execução cresce linearmente: quanto mais elementos houver, maior será o tempo de execução. Acontece que o algoritmo acima funciona em tempo linear (uma função linear de n). Nesses casos, dizemos que a complexidade do algoritmo é "O(n)". Essa notação também é chamada de "big O" ou "comportamento assintótico". Mas você pode apenas lembrar "
O algoritmo de classificação mais simples (ordenação por bolhas)
Suponha que temos uma matriz e podemos iterar por ela. Ótimo. Agora vamos tentar classificá-lo em ordem crescente. O que isto significa? Isso significa que, dados dois elementos (por exemplo, a = 6, b = 5), devemos reorganizar ae bse afor maior que b(se a > b). O que isso significa quando estamos usando um índice para trabalhar com uma coleção (como é o caso de um array)? Isso significa que se o elemento com índice a for maior que o elemento com índice b( array[a] > array[b]), os elementos devem ser trocados. Existem diferentes maneiras de mudar de lugar. Mas usaremos uma técnica simples, compreensível e fácil de lembrar:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Agora podemos escrever o seguinte:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Como você pode ver, os elementos realmente foram trocados. Começamos com o índice 1, pois se o array tiver apenas um elemento, a expressão array[i] < array[i-1]é inválida para o índice 0. Fazer isso também nos protege de casos em que o array não tem elementos ou tem apenas um elemento, e melhora a aparência do código. Mas a matriz resultante ainda não está classificada, porque uma passagem não é suficiente para fazer a classificação. Teremos que adicionar outro loop no qual realizaremos passagens repetidas vezes até obtermos um array ordenado:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Então terminamos nosso primeiro algoritmo de ordenação. Repetimos o loop externo ( while) até decidirmos que não são necessárias mais iterações. Por padrão, antes de cada nova iteração, assumimos que nosso array está classificado e não precisamos mais repetir. Assim, passamos sequencialmente pelos elementos e verificamos essa suposição. Mas se os elementos não estiverem em ordem, trocamos os elementos e entendemos que agora não temos garantia de que os elementos estejam na ordem correta. Isso significa que precisamos realizar outra iteração. Por exemplo, suponha que temos [3, 5, 2]. 5é mais do que 3- tudo está bem. Mas 2é menor que 5. No entanto, [3, 2, 5]requer outro passe, já que3 > 2e eles precisam ser trocados. Como estamos usando um loop dentro de um loop, a complexidade do nosso algoritmo aumenta. Dado nelementos, torna-se n * n, isto é, O(n^2). Isso é chamado de complexidade quadrática. Em geral, não podemos saber exatamente quantas iterações serão necessárias. A expressão da complexidade de um algoritmo mostra como a complexidade aumenta no pior caso. Ou seja, indica quanto aumentará o tempo de execução à medida que o número de elementos nmuda. Bubble sort é um dos algoritmos de ordenação mais simples e ineficientes. Às vezes também é chamado de "classificação estúpida". Matéria sobre este tema:
Outro algoritmo de ordenação é a ordenação por seleção. Ele também tem complexidade quadrática, mas mais sobre isso depois. Então a ideia é simples. Em cada passagem, selecionamos o menor elemento e o deslocamos para o início. Além disso, cada passagem começa um passo para a direita. Em outras palavras, a primeira passagem começa do elemento zero, a segunda passagem do primeiro, etc. Ficará assim:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Essa classificação é instável porque elementos idênticos (em termos de qualquer característica que estamos usando para classificar os elementos) podem mudar suas posições relativas. Há um bom exemplo no artigo da Wikipedia sobre seleção de classificação . Matéria sobre este tema:
A classificação por inserção também tem complexidade quadrática, pois novamente temos um loop dentro de um loop. O que torna a classificação por inserção diferente? Esse algoritmo de classificação é "estável". Isso significa que elementos idênticos não mudarão sua ordem relativa. Novamente, queremos dizer idênticos em termos das características pelas quais estamos classificando.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
tipo de transporte
Existe outro algoritmo de ordenação simples: a ordenação por vaivém. Isso também é conhecido como tipo de bolha bidirecional ou tipo de coqueteleira. Esses nomes alternativos nos dizem que o tipo de ônibus espacial não é sobre o ônibus espacial. É sobre algo que se move para frente e para trás. Agora você pode pensar nisso quando pensar neste algoritmo. Qual é a essência do algoritmo? A essência do algoritmo é iterar da esquerda para a direita, trocando elementos e verificando se algum dos elementos restantes na outra direção precisa ser trocado.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Outro algoritmo de classificação simples é o shell sort. A essência disso é semelhante ao tipo de bolha, mas em cada iteração temos uma lacuna diferente entre os elementos comparados. Ele é cortado pela metade a cada iteração. Aqui está uma implementação:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
Além desses algoritmos de classificação simples, também existem algoritmos de classificação mais complicados. Por exemplo, classificação por mesclagem. Há duas coisas a serem observadas. Primeiro, a recursão vem em nosso socorro aqui. Em segundo lugar, a complexidade do algoritmo não é mais quadrática, como estamos acostumados. A complexidade desse algoritmo é logarítmica. Isso é escrito como O(n log n). Então vamos implementá-lo. Primeiro, escreveremos uma chamada recursiva para o método sort:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Agora, vamos adicionar a ação principal à nossa implementação. Aqui está o nosso super método:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Podemos executar nosso exemplo chamandomergeSort(array, 0, array.length-1). Como você pode ver, o processo se resume a aceitar uma matriz de entrada junto com as indicações do início e do fim da seção que precisa ser classificada. Quando a classificação começa, estes são o início e o fim da matriz. Depois calculamos o delimitador, que é o índice onde iremos dividir o array. Se o array puder ser dividido em 2 partes, então chamamos o método sort recursivamente para as duas metades do array. Preparamos um buffer auxiliar onde iremos inserir a seção ordenada. Em seguida, defina o índice no início da seção a ser classificada e comece a percorrer cada elemento do buffer vazio, preenchendo-o com os menores elementos. Se o elemento apontado pelo índice for menor que o elemento apontado pelo delimitador, colocamos o elemento no buffer e deslocamos o índice. De outra forma, colocamos o elemento apontado pelo delimitador no buffer e deslocamos o delimitador. Assim que o delimitador ultrapassa os limites da seção que está sendo classificada ou preenchemos todo o array, o intervalo especificado é considerado classificado.Matéria sobre este tema:
Outro algoritmo de classificação interessante é a classificação por contagem. A complexidade algorítmica aqui é O(n+k), onde né o número de elementos e ké o valor máximo de um elemento. Esse algoritmo tem uma falha: precisamos saber os valores mínimo e máximo no array. Aqui está um exemplo do tipo de contagem:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Você pode entender que é muito inconveniente quando precisamos saber antecipadamente os valores mínimo e máximo. E temos outro algoritmo aqui: radix sort. Vou apenas apresentar o algoritmo aqui visualmente. Veja os materiais complementares para a implementação: Materiais:
Bem, é hora da sobremesa — classificação rápida, um dos algoritmos de classificação mais famosos. Tem complexidade logarítmica: O(n log n). Este algoritmo de classificação foi desenvolvido por Tony Hoare. Curiosamente, ele o inventou enquanto morava na União Soviética, onde estudou tradução automática na Universidade de Moscou e desenvolveu um livro de frases russo-inglês. Além do mais, o Java usa uma versão mais complexa desse algoritmo em Arrays.sort. E sobre Collections.sort? Por que não dar uma olhada em como as coisas são classificadas "sob o capô"? Aqui está o código:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Isso tudo é muito assustador, então vamos nos aprofundar nisso. Para array de entrada ( int[]source), criamos dois marcadores: left ( L) e right ( R). Durante a primeira chamada do método, eles correspondem ao início e ao fim do array. Em seguida, identificamos o elemento pivô, que é apropriadamente chamado de pivot. Depois disso, nossa tarefa é mover os valores menores que pivotà esquerda de pivot, e os maiores - à direita. Para fazer isso, primeiro movemos o Lmarcador até encontrar um valor maior que pivot. Se nenhum valor menor for encontrado, então
L torna-se igual a
pivot. Em seguida, movemos o
Rmarcador até encontrar um valor menor que
pivot. Se nenhum valor maior for encontrado,
Rtorna-se igual a
pivot. Em seguida, se o
Lmarcador estiver antes do
Rmarcador ou coincidir com ele, tentamos trocar os elementos se o
Lelemento for menor que o
Relemento. Em seguida, deslocamos
Lpara a direita em 1 e para
Ra esquerda em 1. Quando o
Lmarcador se move além do
Rmarcador, significa que a troca está completa: valores menores estão à esquerda de
pivot, valores maiores estão à direita de
pivot. Depois disso, chamamos o mesmo método de classificação recursivamente nos subarrays — do início da seção a ser classificada para o marcador direito e do marcador esquerdo até o final da seção a ser classificada. Por que desde o início até o marcador certo? Porque no final de uma iteração, acontece que o marcador direito se move o suficiente para se tornar o limite da parte esquerda. Esse algoritmo é mais complexo do que a classificação simples, portanto, é melhor esboçá-lo. Pegue uma folha de papel branca e escreva: 4 2 6 7 3. Em seguida, escreva
pivotno meio, ou seja, abaixo do número 6. Circule-o. Em 4, escreva
L, e em 3, escreva
R. 4 a menos que 6, 2 a menos que 6. A gente acaba passando
Lpara a
pivotposição, porque
Lnão pode passar
pivot, de acordo com a condição. Escreva novamente 4 2 6 7 3. Circule 6 (
pivot) e coloque
Lembaixo dele. Agora mova o
Rmarcador. 3 é menor que 6, então coloque o
Rmarcador em 3. Como 3 é menor que 6 (
pivot), realizamos um
swap. Escreva o resultado: 4 2 3 7 6. Circule 6, porque ainda é o
pivot. O
Lmarcador está no 3. O
Rmarcador está no 6. Lembre-se de que movemos os marcadores até
Lmover além de
R. Mover
Lpara o próximo número. Aqui eu gostaria de explorar duas possibilidades: 1) o caso em que o penúltimo número é 7 e 2) o caso em que é 1, não 7.
Se o penúltimo número for 1: Mova o
Lmarcador para 1, porque podemos mover
Lcontanto que o
Lmarcador aponta para um número menor que
pivot. Mas não podemos sair
Rde 6, porque só podemos mover R se o
Rmarcador apontar para um número maior que
pivot. Não executamos um
swap, porque 1 é menor que 6. Escreva a situação atual: 4 2 3 1 6. Circule 6 (
pivot).
Lmuda
pivote para de se mover.
Rnão se move. Não realizamos troca. Shift
Le
Rpor uma posição. Escreva o
Rmarcador abaixo de 1. O
Lmarcador está fora dos limites. Porque
Lestá fora dos limites, eu não faço nada. Mas, escrevemos 4 2 3 1 novamente, porque este é o nosso lado esquerdo, que é menor que
pivot(6). Selecione o novo
pivote comece tudo de novo :)
Se o penúltimo número for 7:Mova o
Lmarcador para 7. Não podemos mover o marcador direito, porque ele já está apontando para o pivô. 7 é maior que
pivot, então executamos um
swap. Escreva o resultado: 4 2 3 6 7. Circule 6, porque é o
pivot. O
Lmarcador agora é deslocado para 7 e o
Rmarcador é deslocado para 3. Não faz sentido classificar a parte do
Lfinal, porque há apenas 1 elemento. No entanto, enviamos a peça de 4 para o
Rmarcador para classificação. Escolhemos a
pivote começamos tudo de novo :) À primeira vista, pode parecer que se você adicionar muitos valores iguais a
pivot, então você quebrará o algoritmo. Mas este não é o caso. Você pode pensar em combinações complicadas e, no papel, convencer-se de que tudo está correto e se maravilhar com o fato de ações tão simples implementarem um mecanismo de classificação tão confiável. A única desvantagem é que esse algoritmo de classificação não é estável. Porque uma troca pode alterar a ordem relativa de elementos idênticos se um deles for encontrado antes
pivotde o outro elemento ser trocado na parte anterior
pivot.
A linha de fundo
Acima, examinamos um conjunto "de cavalheiros" de algoritmos de classificação implementados em Java. Algoritmos são geralmente úteis, tanto do ponto de vista aplicado quanto em termos de aprender a pensar. Alguns são mais simples, alguns são mais complicados. Pessoas inteligentes defenderam suas dissertações para alguns. Para outros, escreveram livros super grossos. Espero que os materiais complementares ajudem você a aprender ainda mais, já que este artigo é apenas uma visão geral que já se mostrou pesada. E seu objetivo é fornecer uma pequena introdução. Você também pode encontrar uma introdução aos algoritmos se ler
"Grokking Algorithms ". Também gosto da lista de reprodução de Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . Para se divertir, você pode ver visualizações de algoritmo na
classificação.visualgo.net .
GO TO FULL VERSION