5 algoritmos de classificação no Dart
Como desenvolvedores, escrevemos algoritmos todos os dias!
Embora o Dart forneça métodos de classificação integrados, ter um conhecimento sólido de algoritmos de classificação pode aprimorar suas habilidades gerais de programação e capacitá-lo a tomar decisões informadas quando se trata de projetar aplicativos Flutter eficientes e escalonáveis.
Um algoritmo de classificação é um método para reorganizar um grande número de itens em uma ordem específica, como alfabética, do maior para o menor valor ou da menor para a maior distância.
Existem muitos algoritmos de classificação com os quais você pode se familiarizar. Cada um desses algoritmos tem alguns prós e contras e pode ser escolhido de forma eficaz dependendo do tamanho dos dados a serem tratados.
Vamos nos concentrar em cinco algoritmos clássicos por enquanto:
- Classificação de inserção
- Seleção
- Tipo de bolha
- Mesclar classificação
- Ordenação rápida.
Conteudo
Classificação de inserção
Este algoritmo é um dos algoritmos mais simples com uma implementação simples.
Funciona de maneira semelhante à maneira como você classifica as cartas em suas mãos. A matriz é virtualmente dividida em uma parte classificada e uma parte não classificada. Os valores da peça não classificada são selecionados e colocados na posição correta na peça classificada.
Credito da Imagem GIF : medium-algorithms-for-beginners
O código que implementa esta rotina é descrito abaixo. O índice j assume o valor inicial valores.length — 1 (última posição) e a condição de parada do loop é satisfeita quando este índice chega a 0 ou quando o valor que queremos inserir na ordem já está em sua posição (valores[j] >= valores[j-1]). Se j atingir 0, todo o array foi avaliado e o algoritmo deverá parar. Da mesma forma, se valores[j] >= valores[j-1] o algoritmo deve parar porque o elemento que estamos tentando ajustar já está em seu lugar.
...
int j = list.length - 1;
while (j > 0 && list[j] < list[j - 1]) {
int aux = list[j];
list[j] = list[j - 1];
list[j - 1] = aux;
j--;
}
...A classificação por inserção aplica a inserção classificada várias vezes para classificar uma sequência. Faremos isso adicionando o comando for com i variando de 1 ao final e j variando de acordo com i .
List<int> insertionSort(List<int> list) {
for (int i = 1; i < list.length; i++) {
int j = i;
while (j > 0 && list[j] < list[j - 1]) {
int aux = list[j];
list[j] = list[j - 1];
list[j - 1] = aux;
j--;
}
}
return list;
}
Ordenação por seleção
Se você pedir a alguém que não está familiarizado com algoritmos para classificar uma sequência numérica, provavelmente essa pessoa aplicará a classificação por seleção. Isso porque o Selection Sort segue uma rotina básica: “selecionar o valor mínimo da sequência e colocá-lo na primeira posição”. A ideia é executar essas duas etapas até que a sequência seja ordenada.
Em cada iteração de classificação por seleção, o elemento mínimo do submatriz não classificado é selecionado e movido para o submatriz classificado. A ordenação por seleção tem a propriedade de minimizar o número de trocas.
void swap(List<int> list, int left, int right) {
int temp = list[left];
list[left] = list[right];
list[right] = temp;
}
List<int> selectionSort(List<int> list) {
for (int i = 0; i < list.length; i++) {
int minIndex = i;
// Encontre o elemento mínimo em uma matriz não classificada
for (int j = i + 1; j < list.length; j++) {
if (list[j] < list[minIndex]) {
minIndex = j;
}
}
// Troque o elemento mínimo encontrado pelo primeiro elemento
swap(list, i, minIndex);
}
return list;
}
Tipo de bolha
Bubble sort é um algoritmo de classificação que compara dois elementos adjacentes e os troca até que estejam na ordem pretendida.
Este algoritmo não é adequado para grandes conjuntos de dados, pois sua complexidade média e de pior caso são de Ο(n²), onde n é o número de itens
A ideia principal é:
- Percorra da esquerda e compare os elementos adjacentes e o mais alto é colocado no lado direito.
- Desta forma, o elemento maior é movido primeiro para a extremidade direita.
- Este processo continua para encontrar o segundo maior e colocá-lo e assim por diante até que os dados sejam classificados.
Abaixo está a implementação do tipo bolha.
void swap(List<int> values, int left, int right) {
final temp = values[left];
values[left] = values[right];
values[right] = temp;
}
List<int> bubbleSort(List<int> values) {
// Otimiza o algoritmo parando o algoritmo
// se o loop interno não causou nenhuma troca.
bool swapped = false;
for (var i = 0; i < values.length; i++) {
swapped = false;
for (var j = i + 1; j < values.length; j++) {
if (values[i] > values[j]) {
swap(values, i, j);
swapped = true;
}
}
// Se dois elementos não foram trocados pelo loop interno, então quebre
if (!swapped) break;
}
return values;
}
Mesclar classificação
Merge Sort é um algoritmo eficiente de dividir e conquistar. Isso funciona dividindo uma matriz em submatrizes menores, classificando cada submatriz e, em seguida, mesclando as submatrizes classificadas novamente para formar a matriz ordenada final.
Em termos simples, podemos dizer que o processo de classificação por mesclagem consiste em dividir a matriz em duas metades, classificar cada metade e, em seguida, mesclar as metades classificadas novamente. Este processo é repetido até que todo o array seja classificado.
Implementação de mesclagem
O código para o método de mesclagem é descrito abaixo. Vamos detalhar cada detalhe de implementação.
void merge(List<int> values, int left, int middle, int right) {
// crie um array temporário com elementos de [valores]
final tempArray = List.generate(values.length, (index) => values[index]);
int i = left;
int j = middle + 1;
int k = left;
while (i <= middle && j <= right) {
if (tempArray[i] <= tempArray[j]) {
values[k] = tempArray[i];
i++;
} else {
values[k] = tempArray[j];
j++;
}
k++;
}
// se não consumiu a parte inicial, anexe
while (i <= middle) {
values[k] = tempArray[i];
i++;
k++;
}
// se não consumiu a última parte, anexe
while (j <= right) {
values[k] = tempArray[j];
j++;
k++;
}
}O método recebe como parâmetro o array a ser processado. Recebe também três índices: esquerdo, médio e direito, que determinam os limites em que o algoritmo deve atuar.
Para fazer manipulações em nosso array original, precisamos de um array auxiliar (tempArray) para armazenar o estado
// crie um array temporário com elementos de [valores] final tempArray = List.generate(values.length, (index) => values[index]);
A seguir definimos i, j e k, esses são os índices utilizados para controlar a execução e comparação dos elementos. i marca o início da primeira parte do array, j marca o início da segunda parte do array e k marca a posição onde o menor elemento entre tempArray[i] e tempArray[j] deve ser adicionado.
int i = left; int j = middle + 1; int k = left; ...
Agora o algoritmo faz a comparação entre tempArray[i] e tempArray[j] para adicionar o elemento mínimo em valores[k].
...
while (i <= middle && j <= right) {
if (tempArray[i] <= tempArray[j]) {
values[k] = tempArray[i];
i++;
} else {
values[k] = tempArray[j];
j++;
}
k++;
}
...Ao final, basta anexar todos os elementos da parte que não foi totalmente consumida.
...
// se não consumiu a parte inicial, anexe
while (i <= middle) {
values[k] = tempArray[i];
i++;
k++;
}
// se não consumiu a última parte, anexe
while (j <= right) {
values[k] = tempArray[j];
j++;
k++;
}
...
Implementação de classificação de mesclagem
Merge Sort é um algoritmo de dividir e conquistar. A parte da conquista que já abordamos detalhadamente, sabemos como combinar dois arrays classificados em um array ordenado.
A parte da divisão é bastante simples 🙂. Simplesmente “divida” o array recursivamente ao meio até que reste apenas um elemento. Vamos ver o código 👇🏿
List<int> mergeSort(List<int> values, int left, int right) {
if (left >= right) {
return values;
} else {
int middle = (left + right) ~/ 2;
// Classifique a primeira e a segunda metades
mergeSort(values, left, middle);
mergeSort(values, middle + 1, right);
merge(values, left, middle, right);
}
return values;
}Vamos analisar esse método.
Vamos analisar a assinatura do método. Os parâmetros são o array a ser ordenado, um índice left e um índice right, que delimitam a parte do array que o algoritmo deve analisar. Na primeira chamada teremos left = 0 e right =values.length — 1.
Na primeira linha do método, temos a condição de parada do algoritmo (left >= right).
Definimos meio como o valor intermediário entre left e rigth. Em seguida, criamos chamadas recursivas para a metade esquerda (da esquerda para o meio) e para a metade direita (do meio + 1 para a direita).
Por fim, após cada quebra há uma chamada ao método merge, passando os limites a serem considerados (esquerdo, meio, direita).
... int middle = (left + right) ~/ 2; mergeSort(values, left, middle); mergeSort(values, middle + 1, right); merge(values, left, middle, right); ...
Código Completo
List<int> mergeSort(List<int> values, int left, int right) {
if (left >= right) {
return values;
} else {
int middle = (left + right) ~/ 2;
// Classifique a primeira e a segunda metades
mergeSort(values, left, middle);
mergeSort(values, middle + 1, right);
merge(values, left, middle, right);
}
return values;
}
void merge(List<int> values, int left, int middle, int right) {
// crie um array temporário com elementos de [valores]
final tempArray = List.generate(values.length, (index) => values[index]);
int i = left;
int j = middle + 1;
int k = left;
while (i <= middle && j <= right) {
if (tempArray[i] <= tempArray[j]) {
values[k] = tempArray[i];
i++;
} else {
values[k] = tempArray[j];
j++;
}
k++;
}
// se não consumiu a parte inicial, anexe
while (i <= middle) {
values[k] = tempArray[i];
i++;
k++;
}
// se não consumiu a última parte, anexe
while (j <= right) {
values[k] = tempArray[j];
j++;
k++;
}
}
Ordenação rápida
Quick Sort também é um algoritmo Divide and Conquer. Ele escolhe um elemento como pivô e particiona a matriz fornecida em torno do pivô escolhido, de modo que todos os elementos menores fiquem à esquerda do pivô e todos os elementos maiores fiquem à direita do pivô. Existem muitas versões diferentes do quickSort que escolhem o pivô de diferentes maneiras:
- Sempre escolha o primeiro elemento como pivô.
- Sempre escolha o último elemento como pivô.
- Escolha um elemento aleatório como pivô (implementado abaixo).
- Escolha a mediana como pivô.
O processo principal no quicksort é o método partition(). Particionar significa escolher qualquer número presente no array como pivô e colocá-lo em uma posição tal que todos os elementos à esquerda sejam menores ou iguais e todos os elementos à direita sejam maiores.
Para entradas pequenas, o quicksort é o melhor algoritmo em comparação com o merge sort. Quando você não precisa de uma classificação estável e o desempenho do caso médio é mais importante do que o desempenho do pior caso, opte pelo quicksort. Vamos ver primeiro o algoritmo de partição e sua implementação.
Algoritmo de partição
Começamos do elemento mais à direita e acompanhamos o índice de elementos menores (ou iguais a) como r.
- Se encontrarmos um elemento
jmenor quer, incrementamos o ponteiroie trocamos os elementos deiej. - Se encontrarmos um elemento
jmaior quer, simplesmente incrementamos o ponteiroj.
import 'dart:math';
int partition(List<int> values, int left, int right) {
// obter um índice dinâmico aleatório
final pivotRange = right - left + 1;
final randomPivot = Random().nextDouble().toInt() * pivotRange + left;
// altere o valor aleatório escolhido com a primeira posição
swap(values, left, randomPivot);
int pivot = values[left];
int i = left;
for (int j = i + 1; j <= right; j++) {
if (values[j] <= pivot) {
i++;
swap(values, i, j);
}
}
swap(values, left, i);
return i;
}Primeiro, vamos entender a assinatura do método de partição. Ele recebe como parâmetro o array a ser particionado. Recebe também dois índices válidos do array (left e right) que determinam os limites em que o algoritmo deve atuar. Na primeira chamada, left = 0 e right =values.length — 1.
As duas primeiras linhas são a escolha do pivô aleatório (você também pode optar por sempre escolher o pivô como primeiro elemento [left=0]).
Então precisamos iterar sobre o array procurando os elementos menores ou iguais e trocando-os pelas posições à frente do pivô.
Quando um valor menor ou igual ao pivô é encontrado (se values[j] <= pivot), realizamos duas etapas:
- Incrementar i
- Trocar
values[i]porvalues[j]
Ao terminar a iteração, basta alterar os valores[i] pela posição do pivô. Ou seja, trocamos valores[i] por valores[esquerda].
Finalmente, retornamos i que é a posição final do pivô.
Implementação de classificação rápida
Quick Sort, é executado em partições consecutivas. A primeira é realizada levando em consideração todo o array (left = 0 e right = values.length — 1). Então, leva-se em consideração a esquerda do pivô, ou seja, left = 0 e right = indexPivot — 1 e a direita do pivô (left = indexPpivot + 1 e right = values.length — 1). Em seguida, o mesmo processo é feito com a esquerda e a direita dos novos pivôs e assim por diante até que todo o array tenha sido percorrido (left >= right).
List<int> quickSort(List<int> values, int left, int right) {
if (left < right) {
final indexPivot = partition(values, left, right);
quickSort(values, left, indexPivot - 1);
quickSort(values, indexPivot + 1, right);
}
return values;
}Código Completo
import 'dart:math';
List<int> quickSort(List<int> values, int left, int right) {
if (left < right) {
final indexPivot = partition(values, left, right);
quickSort(values, left, indexPivot - 1);
quickSort(values, indexPivot + 1, right);
}
return values;
}
int partition(List<int> values, int left, int right) {
final pivotRange = right - left + 1;
final randomPivot = Random().nextDouble().toInt() * pivotRange + left;
swap(values, left, randomPivot);
int pivot = values[left];
int i = left;
for (int j = i + 1; j <= right; j++) {
if (values[j] <= pivot) {
i++;
swap(values, i, j);
}
}
swap(values, left, i);
return i;
}
List<int> swap(List<int> values, int left, right) {
final temp = values[left];
values[left] = values[right];
values[right] = temp;
return values;
}Espero que este artigo lhe dê uma visão geral de alguns dos algoritmos de classificação mais conhecidos e que você comece a explorar mais por conta própria 🙂.
Você encontrará todos os algoritmos aqui 👇🏿👇🏿
GitHub
