Introdução à Classificação Rápida em Java
O artigo a seguir Classificação Rápida em Java fornece um esboço do algoritmo de classificação rápida em java. O algoritmo de classificação rápida é um dos algoritmos de classificação que é eficiente e semelhante ao do algoritmo de classificação de mesclagem. Este é um dos algoritmos utilizados com maior frequência para fins de classificação em tempo real. A complexidade do tempo do pior caso desse algoritmo é O (n 2), a complexidade do tempo do caso médio é O (n log n) e a complexidade do tempo do melhor caso é O (n log n).
A complexidade do espaço se O (n log n) em que n for o tamanho da entrada. O processo de classificação envolve particionamento de entrada, iterações recursivas e marcação de um elemento central para cada recursão. O tipo de classificação neste algoritmo envolve uma comparação de elementos adjacentes de maneira iterativa.
Como a Classificação Rápida funciona em Java?
O algoritmo Quick Sort pode ser implementado em Java, formando um pseudo-código com uma sequência de etapas projetadas e seguidas de maneira eficiente.
- O principal princípio do algoritmo de classificação rápida que ele funciona é baseado na abordagem de dividir e conquistar e também é um algoritmo de classificação eficiente.
- A matriz de entrada é dividida em sub-matrizes e a divisão é baseada no elemento pivô, que é um elemento central. As sub-matrizes de ambos os lados do elemento pivô são as principais áreas em que a classificação realmente ocorre.
- O elemento pivô central é a base para dividir a matriz em duas partições, onde a metade esquerda dos elementos da matriz é menor que o elemento pivô e a metade direita dos elementos da matriz é maior que o elemento pivô.
- Antes de considerar o elemento dinâmico, pode ser qualquer um dos elementos de uma matriz. Normalmente, isso é considerado um do meio ou primeiro ou último para facilitar o entendimento. O elemento dinâmico pode ser aleatório a partir de qualquer um dos elementos da matriz.
- No nosso exemplo, o último elemento de uma matriz é considerado um elemento dinâmico, em que o particionamento de sub-matrizes começa na extremidade direita da matriz.
- Finalmente, o elemento pivô estará em sua posição classificada real após a conclusão do processo de classificação, onde o processo principal de classificação está na lógica de partição do algoritmo de classificação.
- A eficiência do algoritmo depende do tamanho das sub-matrizes e de como elas são equilibradas. Quanto mais os sub-arrays forem desequilibrados, mais a complexidade do tempo levará à pior complexidade.
- A seleção de elementos dinâmicos de maneira aleatória resulta na melhor complexidade de tempo em muitos casos, em vez de escolher um índice inicial, final ou intermediário específico como elementos dinâmicos.
Exemplos para implementar a classificação rápida em Java
O algoritmo QuickSort foi implementado usando a linguagem de programação Java como abaixo e o código de saída foi exibido sob o código.
- O código inicialmente recebe a entrada usando o método quickSortAlgo () com a matriz, o índice inicial e o índice final, ou seja, o comprimento da matriz como argumentos.
- Depois de chamar o método quickSortAlgo (), ele verifica se o índice inicial é menor que o índice final e chama o método arrayPartition () para obter o valor do elemento dinâmico.
- O elemento de partição contém a lógica de organizar os elementos menores e maiores ao redor do elemento dinâmico com base nos valores do elemento.
- Após obter o índice do elemento dinâmico após a execução do método de partição, o método quickSortAlgo () é chamado por si só recursivamente até que todas as sub-matrizes sejam particionadas e classificadas completamente.
- Na lógica da partição, o último elemento é atribuído como elemento dinâmico e o primeiro elemento é comparado com o elemento dinâmico, ou seja, o último em que os elementos são trocados com base em serem menores ou maiores.
- Esse processo de recursão ocorre até que todos os elementos de uma matriz sejam particionados e classificados, onde o resultado final é uma matriz classificada combinada.
- Os elementos são trocados dentro da iteração de loop for apenas no caso de o elemento ser menor ou igual ao elemento pivô.
- Após concluir o processo de iteração, o último elemento é trocado, ou seja, o valor do elemento pivô é movido para o lado esquerdo para que as novas partições sejam feitas e o mesmo processo se repita na forma de recursão, o que resulta em uma série de operações de classificação em diferentes partições possíveis como uma formação de sub-matrizes a partir dos elementos da matriz fornecidos.
- O código abaixo pode ser executado em qualquer IDE e a saída pode ser verificada alterando o valor da matriz no main () O método principal é usado apenas com a finalidade de obter a saída no console. Como parte dos padrões de codificação Java, o método principal pode ser removido abaixo e um objeto pode ser criado e os métodos abaixo podem ser chamados, tornando-os não estáticos.
Implementação de código do algoritmo de classificação rápida em Java
/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm (
public static void main(String() args) (
int() array = ( 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 );
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) (
System.out.print(ar + " ");
)
)
public static int arrayPartition(int() array, int start, int end) (
int pivot = array(end);
int i = (start - 1);
for (int ele = start; ele < end; ele++) (
if (array(ele) <= pivot) (
i++;
int swap = array(i);
array(i) = array(ele);
array(ele) = swap;
)
)
// Swapping the elements
int swap = array(i + 1);
array(i + 1) = array(end);
array(end) = swap;
return i + 1;
)
public static void quickSortAlgo(int() arrayTobeSorted, int start, int end) (
if (start < end) (
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
)
)
)
Resultado:
Conclusão
O algoritmo de classificação rápida é eficiente, mas não muito estável, em comparação com outras técnicas de classificação. A eficiência dos algoritmos de ordenação rápida diminui no caso de um número maior de elementos repetidos, o que é uma desvantagem. A complexidade do espaço é otimizada neste algoritmo de classificação rápida.
Artigos recomendados
Este é um guia para a Classificação Rápida em Java. Aqui discutimos como o Quick Sort funciona em Java, juntamente com um exemplo e implementação de código. Você também pode consultar nossos outros artigos sugeridos para saber mais -
- Heap Sort In Java
- O que é uma árvore binária em Java?
- Manipulação de bits em Java
- Visão geral do Merge Sort in JavaScript
- Visão geral da classificação rápida em JavaScript
- Heap Sort em Python
- Os 6 principais algoritmos de classificação em JavaScript