Como implementar QuickSort em Java?



Este artigo apresentará outro algoritmo de classificação do Divide And Conquer que é o QuickSort em Java e o acompanhará com uma demonstração.

QuickSort é um algoritmo de divisão e conquista. No paradigma de projeto do algoritmo Divide & Conquer, dividimos os problemas em subproblemas recursivamente, em seguida, resolvemos os subproblemas e, por fim, combinamos as soluções para encontrar o resultado final. Neste artigo, vamos nos concentrar no QuickSort In

As dicas a seguir serão abordadas neste artigo,





Vamos começar!

Uma coisa a ter em mente ao dividir os problemas em subproblemas é que a estrutura dos subproblemas não muda a partir do problema original.
O algoritmo Divide & Conquer tem 3 etapas:



  • Divide: dividindo o problema em subproblemas
  • Conquistar: Resolvendo os subproblemas recursivamente
  • Combine: Combine as soluções para obter o resultado final

Image- Quick sort in Java- Edureka

como fazer um jframe

Existem vários algoritmos baseados no paradigma dividir e conquistar. A classificação rápida e a classificação por mesclagem estão entre elas.

Embora o pior caso de complexidade de tempo do QuickSort seja O (n2), que é mais do que muitos outros algoritmos de classificação, como Merge Sort e Heap Sort, QuickSort é mais rápido na prática, porque seu loop interno pode ser implementado com eficiência na maioria das arquiteturas e na maioria dados do mundo real.



Vamos falar sobre a implementação do algoritmo de classificação rápida. Os algoritmos Quicksort pegam um elemento pivô e particionam a matriz em torno do elemento pivô. Existem várias variações do Quicksot que dependem de como você escolhe o elemento pivô. Existem várias maneiras de escolher o elemento pivô:

  • Escolhendo o primeiro elemento
  • Escolha o último elemento
  • Escolha um elemento aleatório
  • Escolhendo o elemento mediano

A próxima coisa importante a entender é a função partition () no algoritmo de classificação rápida. Função de partição para pegar um elemento pivô, colocá-lo na posição certa, mover todos os elementos menores que o elemento pivô para sua esquerda e todos os elementos maiores para sua direita. Quicksort leva um tempo linear para fazer isso.
Em seguida, a matriz é dividida em duas partes a partir do elemento pivô (ou seja, elementos menores que pivô e elementos maiores que pivô) e ambas as matrizes são classificadas recursivamente usando o algoritmo Quicksort.

Agora que entendemos o funcionamento do algoritmo QuickSort. Vamos entender como implementar o algoritmo Quicksort em Java.

Ordenação rápida Função:

/ * A função Quicksort precisa que a matriz seja classificada com o índice mais baixo e mais alto * /

como usar substituir em java
void sort (int arr [], int lowIndex, int highIndex) {// Até lowIndex = highIndex if (lowIndex

Agora, vamos examinar o código de particionamento para entender como ele funciona.

Partição Código

No código de particionamento, escolheremos o último elemento como o elemento pivô. Percorremos o array completo (ou seja, usando a variável j em nosso caso). Acompanhamos o último elemento menor na matriz (ou seja, usando a variável i em nosso caso). Se encontrarmos qualquer elemento menor que o pivô, movemos o elemento atual de troca a [j] com arr [i], caso contrário, continuamos a percorrer.

int partition (int arr [], int lowIndex, int highIndex) {// Fazendo o último elemento como pivô int pivot = arr [highIndex] // Usando i para rastrear elementos menores do pivô int i = (lowIndex-1) para (int j = lowIndex j

Agora que você entendeu a função Quicksort e partição, vamos dar uma olhada rápida no código completo

Ordenação rápida Código Java

class QuickSort {// Método de partição int partição (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j

// Método de classificação

void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex

// Método para imprimir array

static void printArray (int arr []) {int n = arr.length for (int i = 0 i

// Método Principal

public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('matriz classificada') printArray (arr)}}

Resultado:

Output- Quick sort in Java- Edureka

Agora, depois de executar o programa Java acima, você terá entendido como o QuickSort funciona e como implementá-lo em Java.Assim, chegamos ao fim deste artigo sobre ‘Quicksort em Java’. Se você deseja aprender mais,Confira o pela Edureka, uma empresa de aprendizagem online confiável. O curso de certificação e treinamento Java J2EE e SOA da Edureka foi projetado para treiná-lo tanto para os conceitos básicos e avançados do Java, juntamente com várias estruturas Java como Hibernate e Spring.

Tem alguma questão para nós? Mencione isso na seção de comentários deste blog e entraremos em contato com você o mais breve possível.