Classificando algoritmos em Java - Diferentes tipos de algoritmos de classificação em Java

• Introdução aos algoritmos de classificação em Java

Introdução aos algoritmos de classificação em Java

Classificar as informações em uma determinada ordem, geralmente em uma estrutura semelhante a uma matriz, é organizá-las. Você pode usar diferentes requisitos de sequência, os populares são a classificação de números do menor para o maior ou vice-versa, ou as sequências de classificação lexicograficamente. Abordaremos algoritmos diferentes, desde alternativas ineficazes, mas intuitivas, até algoritmos eficientes implementados efetivamente em Java e em outras linguagens, se você estiver interessado em saber como a classificação deve funcionar.

Algoritmos de classificação diferentes em java

Existem algoritmos de classificação diferentes e nem todos são igualmente eficazes. Para compará-los e ver quais têm melhor desempenho, analisaremos suas complexidades de tempo.

1. Classificação de inserção
2. Tipo de bolha
3. Classificação da seleção
4. Mesclar classificação
5. Heapsort

1. Classificação de inserção

O conceito por trás da Classificação por inserção divide o intervalo nas sub-matrizes que são classificadas e não classificadas. A parte classificada está no início da duração 1 e corresponde ao primeiro componente (lado esquerdo) na matriz. Passamos pela matriz e expandimos a parte classificada da matriz por um componente durante cada iteração. Quando expandimos, posicionamos o elemento novo na sub-matriz classificada. Fazemos isso movendo todos os elementos para a direita até descobrirmos que não precisamos alterar o primeiro componente. Quando a parte em negrito é classificada em ordem crescente, por exemplo, na seguinte matriz, ocorre:

1. 3 5 7 8 4 2 1 9 6: Considere 4 e é disso que precisamos inserir. Estamos mudando desde 8> 4
2. 2. 3 5 7 x 8 2 1 9 6
3. 3 5 x 7 8 2 1 9 6
4. 3 x 5 7 8 2 1 9 6
5. 3 4 5 7 8 2 1 9 6

Código:

public class InsertionSortEx (
public static void insertionSort(int() arr) (
for (int x = 1; x < arr.length; x++) (
int current = arr(x);
int y = x - 1;
while(y >= 0 && current < arr(y)) (
arr(y+1) = arr(y);
y--;
)
arr(y+1) = current;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 7, 8, 4, 2, 1, 9, 6);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Resultado:

Seguindo esse método, um componente estendeu a peça classificada, agora temos cinco em vez de quatro elementos. Toda iteração faz isso e toda a matriz será classificada no final.

Nota: Isso ocorre porque precisamos transferir toda a lista classificada uma por uma em cada iteração, que é O (n). Para cada componente em cada tabela, devemos fazer isso, o que implica que ele seja O (n 2) delimitado.

2. Tipo de bolha

Se a bolha não estiver na ordem exigida, ela funcionará substituindo os componentes vizinhos. Isso é repetido até que todos os componentes estejam em ordem desde o início da matriz. Sabemos que, se conseguirmos fazer a iteração inteira sem swaps, todos os itens comparados com seus elementos adjacentes estarão na ordem desejável e, por extensão, toda a matriz. A razão para o algoritmo Bubble Sort é que números como "borbulham" no "solo". Se, após uma quantidade específica, você passar pela instância novamente (4 é uma boa instância), notará que o número lentamente move para a direita.

As etapas para a classificação de bolhas são as seguintes:

1. 4 2 1 5 3: Aqui, os dois números não estão na ordem correta, portanto, temos que classificar os dois números.
2. 2 4 1 5 3: Depois disso, o próximo par de números também não está na ordem correta. Portanto, a classificação ocorre novamente.
3. 2 1 4 5 3: Esses dois estão na ordem correta, 4 <5, portanto, não há necessidade de trocá-los.
4. 2 1 4 5 3 : Novamente temos que trocar pela ordem correta.
5. 2 1 4 3 5: Aqui está a matriz resultante após uma iteração.
6. Temos que repetir esse processo novamente até que os números estejam na ordem correta.

Código:

public class BubbleSortExample (
public static void bubbleSort(int() arr) (
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++)(
for(int y=1; y < (nx); y++)(
if(arr(y-1) > arr(y))(
//swap elements
tmp = arr(y-1);
arr(y-1) = arr(y);
arr(y) = tmp;
)
)
)
)
public static void main(String() args) (
int arr() =(4, 2, 1, 5, 3);
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
)
)

Resultado:

Nota: Pode ter terminado em um loop infinito se eu usasse a (i)> = a (i + 1), porque essa conexão ainda seria válida com componentes equivalentes e, portanto, sempre os trocaria de um elemento para outro.

3. Seleção da Seleção

A classificação de seleção divide a matriz em uma matriz de classificações que não são classificadas. Desta vez, no entanto, o subarray de classificação é formado inserindo no final da matriz classificada o elemento mínimo do subarray não classificado, trocando:

1. 3 5 1 2 4
2. 1 5 3 2 4
3. 1 2 3 5 4
4. 1 2 3 5 4
5. 1 2 3 4 5
6. 1 2 3 4 5

Código:

public class SelectionSortEx (
public static void selectionSort(int() arr)(
for (int x = 0; x < arr.length - 1; x++)
(
int indx = x;
for (int y = x + 1; y < arr.length; y++)(
if (arr(y) < arr(indx))(
indx = y;
)
)
int smallNumber = arr(indx);
arr(indx) = arr(x);
arr(x) = smallNumber;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 1, 2, 4);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Resultado:

Nota: O mínimo é O (n) para o tamanho da matriz porque todos os componentes devem ser verificados. Para cada elemento da matriz, devemos encontrar o mínimo e tornar todo o processo O (n 2) limitado.

4. Mesclar Classificação

A classificação de mesclagem utiliza recursão para corrigir o problema do método de divisão e conquista com mais eficiência do que os algoritmos descritos anteriormente.

Esta árvore mostra como as chamadas recursivas funcionam. Matrizes marcadas com seta para baixo são aquelas para as quais chamamos de função enquanto fundimos matrizes com seta para cima. Em seguida, siga a seta até a borda da árvore e depois retorne e junte. Como temos 3 5 3 1, dividimos em 3 5 4 e 2 1. Dividimos em suas partes para classificá-las. Começamos a fundi-los e classificá-los à medida que avançamos quando chegamos ao fundo.

Código:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort (
static void merge(int() array, int lowval, int midval, int highval)(
int x, y, k;
int() c= new int(highval-lowval+1);
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval)(
if(array(x)<=array(y))(
c(k++) = array(x++);
)
else(
c(k++) = array(y++);
)
)
while(x<=midval)(
c(k++) = array(x++);
)
while(y<=highval)(
c(k++) = array(y++);
)
k=0;
for(x = lowval; x<=highval; x++)(
array(x) = c(k++);
)
)
static void mergeSort(int() array, int lowval, int highval)(
if(highval-lowval+1>1)(
int midval = (lowval+highval)/2;
mergeSort(array, lowval, midval);
mergeSort(array, midval+1, highval);
merge(array, lowval, midval, highval);
)
)
public static void main(String() args) (
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try (
size = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("Please Enter valid Input");
return;
)
int() array = new int(size);
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) (
try (
array(x) = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("An error Occurred");
)
)
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
)
)

Neste programa, solicitamos que o usuário insira entrada. A saída será ordenada com base na entrada do usuário.

Resultado:

5. Heap Sort

Primeiro, você deve conhecer a estrutura na qual o Heapsort opera - o heap - para entender por que ele opera. Falaremos especificamente sobre um heap binário, mas você também pode generalizar isso para outras construções de heap. Um heap é uma árvore que cumpre as propriedades do heap, ou seja, que todos os seus filhos tenham relacionamentos com cada nó. Uma pilha também deve estar quase pronta. Um binário de profundidade d quase completo possui uma subárvore d-1, com a mesma raiz, e cada nó tem uma subárvore esquerda completa, com uma descendente esquerda.

Em outras palavras, você obtém um número menor e menor (min-heap) ou maior e maior (max-heap) ao descer a árvore. Aqui está uma instância de max-heap:

1. 6 1 8 3 5 2 4 : Aqui, os números de ambos os filhos são menores que os pais, portanto, não precisamos mudar nada.
2. 6 1 8 3 5 2 4: Aqui, 5> 1, precisamos trocá-los. Precisamos heapificar para 5.
3. 6 5 8 3 1 2 4: Ambos os números das crianças são menores, tudo permanece o mesmo.
4. 6 5 8 3 1 2 4: Aqui, 8> 6, portanto, devemos trocá-los.
5. 8 5 6 3 1 2 4: Após essa iteração, obteremos esse resultado.

Depois de repetir esse processo novamente, obteremos os seguintes resultados:

• 8 5 6 3 1 2 4

1. 4 5 6 3 1 2 8 : Troca
2. 6 5 4 3 1 2 8 : Heapify
3. 2 5 4 3 1 6 8 : Troca
4. 5 2 4 2 1 6 8 : Heapify
5. 1 2 4 2 5 6 8 : Troca

Código:

public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
) public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)

Resultado:

Você pode vê-lo do ponto ao nível do gráfico, da esquerda para a direita. O que alcançamos aqui é que, quando temos o k-ésimo componente na matriz, a posição de seus filhos é 2 \ * k + 1 e 2 \ * k + 2 (assumindo que a indexação comece em 0). Isso pode ser monitorado por você. A posição do pai é sempre (k-1) / 2 para o k-ésimo componente. Você pode prontamente "amontoar" qualquer intervalo, porque você sabe disso. Verifique se um de seus filhos é menor que o de cada componente. Nesse caso, emparelhe um dos pais e repita esta etapa recursivamente com os pais.

Nota: Como iterar for-loops em toda a matriz cria heapSort) (obviamente O (N), isso criaria a complexidade geral do Heapsort O (nlog n). O Heapsort tem um tipo no local, o que significa que requer O ( 1) mais espaço que o Merge Sort, mas possui algumas desvantagens, como paralelos difíceis.

Conclusão - Classificando algoritmos em Java

A classificação é um procedimento muito prevalente com conjuntos de dados, seja para análises adicionais, acelerando a pesquisa com algoritmos mais eficazes, baseados em informações classificadas, informações de filtragem etc. A classificação é recomendada por vários idiomas e muitas vezes as interfaces obscurecem o que o programador faz.

Artigos recomendados

Este é um guia para ordenar algoritmos em Java. Aqui discutimos diferentes tipos de classificação em Java, juntamente com seus algoritmos. Você também pode consultar nossos outros artigos sugeridos -

1. Mesclar algoritmos de classificação em Java
2. JComboBox em Java
3. StringBuffer em Java
4. JTextField em Java
5. Heap Sort em Python
6. Algoritmos de classificação rápida em Java
7. Guia completo para classificação em c # com exemplos
8. Classificação de algoritmos em JavaScript
9. Guia de exemplos de algoritmo C ++
10. Guia completo de classificação de algoritmos em Python