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?
L torna-se igual a
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 = 10
o 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 a
e b
se a
for 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 > 2
e eles precisam ser trocados. Como estamos usando um loop dentro de um loop, a complexidade do nosso algoritmo aumenta. Dado n
elementos, 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 n
muda. 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:
Classificação de seleção
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:
ordenação por inserção
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));
Matéria sobre este tema:
Shell sort
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));
Matéria sobre este tema:
Mesclar classificação
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 comoO(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:
Ordenação por contagem e ordenação por raiz
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:
Ordenação rápida
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 L
marcador até encontrar um valor maior que pivot
. Se nenhum valor menor for encontrado, entãopivot
. Em seguida, movemos o
R
marcador até encontrar um valor menor que
pivot
. Se nenhum valor maior for encontrado,
R
torna-se igual a
pivot
. Em seguida, se o
L
marcador estiver antes do
R
marcador ou coincidir com ele, tentamos trocar os elementos se o
L
elemento for menor que o
R
elemento. Em seguida, deslocamos
L
para a direita em 1 e para
R
a esquerda em 1. Quando o
L
marcador se move além do
R
marcador, 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
pivot
no 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
L
para a
pivot
posição, porque
L
não pode passar
pivot
, de acordo com a condição. Escreva novamente 4 2 6 7 3. Circule 6 (
pivot
) e coloque
L
embaixo dele. Agora mova o
R
marcador. 3 é menor que 6, então coloque o
R
marcador 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
L
marcador está no 3. O
R
marcador está no 6. Lembre-se de que movemos os marcadores até
L
mover além de
R
. Mover
L
para 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
L
marcador para 1, porque podemos mover
L
contanto que o
L
marcador aponta para um número menor que
pivot
. Mas não podemos sair
R
de 6, porque só podemos mover R se o
R
marcador 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
).
L
muda
pivot
e para de se mover.
R
não se move. Não realizamos troca. Shift
L
e
R
por uma posição. Escreva o
R
marcador abaixo de 1. O
L
marcador está fora dos limites. Porque
L
está 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
pivot
e comece tudo de novo :)
Se o penúltimo número for 7:Mova o
L
marcador 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
L
marcador agora é deslocado para 7 e o
R
marcador é deslocado para 3. Não faz sentido classificar a parte do
L
final, porque há apenas 1 elemento. No entanto, enviamos a peça de 4 para o
R
marcador para classificação. Escolhemos a
pivot
e 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
pivot
de o outro elemento ser trocado na parte anterior
pivot
.
GO TO FULL VERSION