Introdução aos algoritmos de classificação rápida em Java
A classificação rápida em java, também conhecida como classificação de troca de partição, é um algoritmo de classificação de dividir e conquistar. A ordenação rápida é um bom exemplo de algoritmo que faz o melhor uso dos caches da CPU, devido à sua divisão e conquista a natureza. O algoritmo Quicksort é um dos algoritmos de classificação mais usados, especialmente para classificar as grandes listas e a maioria das linguagens de programação o implementou. No algoritmo Quicksort, os dados originais são divididos em duas partes que são classificadas individualmente e depois mescladas para produzir dados classificados.
Vamos considerar que a matriz (8, 6, 3, 4, 9, 2, 1, 7) precisa ser classificada usando a Classificação Rápida.
Etapas para implementar algoritmos de classificação rápida
1. Escolha um elemento chamado pivô da matriz. Geralmente, o elemento do meio é escolhido como o pivô. Vamos considerar 4 como o pivô.
2. Reorganize a matriz em duas partes, de modo que os elementos menores que o pivô venham antes do pivô e os elementos maiores que o pivô apareçam após o pivô. Os seguintes passos são seguidos:
- Escolha o elemento mais à esquerda, ou seja, 8, Dado que 4 é o pivô e 8 é mais que 4, 8 precisa ser movido para a direita de 4. No lado direito, deixamos 7, pois é maior que 4, e escolha 1 para trocar com 8, portanto, após a troca, o array se torna: 1, 6, 3, 4, 9, 2, 8, 7
- Escolha o próximo elemento esquerdo, ou seja, 6, Como 4 é o pivô e 6 é mais que 4, 6 precisa ser movido para a direita de 4. No lado direito, deixamos 7, 8, pois são maiores que 4, e escolhe 2 para trocar com 6, portanto, após a troca, o array se torna: 1, 2, 3, 4, 9, 6, 8, 7
- Agora, como todos os elementos à esquerda do pivô são menores que o pivô e todos os elementos à direita do pivô são maiores que o pivô, terminamos com 4 como pivô.
3. Aplique recursivamente as etapas 1 e 2 para a sub-matriz esquerda (matriz com elementos menores que o pivô) e para a sub-matriz direita (matriz com elementos mais que a pivô). Se a matriz contiver apenas um ou zero elementos, a matriz será considerada sortida.
Programa para Implementar Algoritmos de Classificação Rápida
Aqui está um programa java para classificar uma matriz de números inteiros usando um algoritmo de classificação rápida.
Código:
import java.lang.*;
import java.util.*;
public class Main (
private int array();
private int length;
public void sort(int() inputArrayArr) (
if (inputArrayArr == null || inputArrayArr.length == 0) (
return;
)
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
)
private void performQuickSort(int lowerIndex, int higherIndex) (
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array(lowerIndex+(higherIndex-lowerIndex)/2);
// Divide into two subarrays
while (i <= j) (
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array(i) < pivot) (
i++;
)
while (array(j) > pivot) (
j--;
)
if (i <= j) (
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
)
)
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
)
private void swapNumbers(int i, int j) (
int temp = array(i);
array(i) = array(j);
array(j) = temp;
)
public static void main(String args())(
Main quickSort = new Main();
int() inputArray = (8, 6, 3, 4, 9, 2, 1, 7);
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
)
)
Resultado:
Vantagens dos algoritmos de classificação rápida
A seguir, estão as vantagens do algoritmo de classificação rápida:
- Excelente localidade de referência: a localidade de referência é a capacidade de um processador acessar repetidamente o mesmo local de memória por um curto período de tempo. A ordenação rápida em java fornece excelente localidade de referência devido ao número muito pequeno de falhas de cache, o que nas arquiteturas modernas é fundamental para o desempenho.
- A classificação rápida é paralelelizável: uma vez concluída a etapa inicial de particionar uma matriz em regiões menores, todas as sub-matrizes individuais podem ser classificadas independentemente em paralelo. Por esse motivo, a classificação rápida tem um desempenho melhor.
Análise de complexidade da classificação rápida
O Quicksort é um algoritmo rápido e recursivo da cauda que funciona pelo princípio de dividir e conquistar. Aqui está sua análise de complexidade em Melhor, Média e Pior Caso:
- Complexidade do melhor caso: se uma matriz ou uma lista contiver n elementos, a primeira execução precisará de O (n). Agora, a classificação dos dois subarrays restantes leva 2 * O (n / 2). Isso conclui a complexidade de O (n logn) no melhor caso.
- Complexidade média do caso : O caso médio do quicksort é O (n log n).
- Complexidade do pior caso: escolher o primeiro ou o último causaria o pior desempenho para os dados quase classificados ou quase reversos. A ordenação rápida executa O (n 2) no pior caso.
Em Java, matrizes. O método Sort () usa um algoritmo de classificação rápida para classificar uma matriz.
Artigos recomendados
Este é um guia para Algoritmos de Classificação Rápida em Java. Aqui discutimos as etapas para implementar, vantagens e análise de complexidade de um algoritmo de classificação rápida em java junto com o programa. Você também pode consultar os seguintes artigos para saber mais -
- Classificação de inserção em Java
- loop do-while em Java
- JComponent em Java
- Quadrados em Java
- Trocando em PHP
- Classificando em C #
- Classificação em Python
- Algoritmo C ++ | Exemplos de algoritmo C ++