Classificação rápida em Java explicou

Classificação rápida, também escrita como Quicksort, é um esquema de classificação de lista que usa o paradigma de divisão e conquista. Existem diferentes esquemas para classificação rápida, todos usando o paradigma de divisão e conquista. Antes de explicar uma classificação rápida, o leitor deve conhecer a convenção para reduzir pela metade uma lista ou sub-lista e a mediana de três valores.

Convenção pela metade

Quando o número de elementos em uma lista é uniforme, a metade da lista significa que a primeira metade literal da lista é a primeira metade, e a segunda metade literal da lista é a segunda metade. O elemento médio (médio) de toda a lista é o último elemento da primeira lista. Isso significa que o índice do meio é de comprimento / 2 - 1, pois a contagem de índice começa de zero. Comprimento é o número de elementos na lista. Por exemplo, se o número de elementos for 8, a primeira metade da lista tem 4 elementos e a segunda metade da lista também possui 4 elementos. Está bem. Desde que a contagem de índice começa a partir de 0, o índice do meio é 3 = 8 /2 - 1.

E o caso, quando o número de elementos na lista ou sub-lista é estranho? No início, o comprimento ainda está dividido por 2. Por convenção, o número de elementos na primeira metade desta divisão é o comprimento / 2 + 1/2. A contagem de índice começa de zero. O índice do meio é dado por comprimento / 2 - 1/2. Isso é considerado o termo intermediário, por convenção. Por exemplo, se o número de elementos em uma lista for 5, o índice do meio será 2 = 5/2 - 1/2. E há três elementos na primeira metade da lista e dois elementos no segundo tempo. O elemento intermediário de toda a lista é o terceiro elemento no índice, 2, que é o índice do meio porque a contagem do índice começa de 0.

Divisão dessa maneira é um exemplo de aritmética inteira.

Mediana de três valores

Pergunta: Qual é a mediana da sequência:

C b a

Solução:
Organize a lista em ordem crescente:

A b c

O termo intermediário, B, é a mediana. É a magnitude que fica entre as outras duas magnitudes.

Procurar a mediana em uma lista não é esse tipo. Por exemplo, em uma lista de 19 elementos não classificados, a mediana para o primeiro elemento, elemento médio e o último elemento pode ser necessário. Esses três valores podem não estar em ordem crescente; E assim, seus índices devem ser levados em consideração.

Com classificação rápida, a mediana para toda a lista e sub-listas são necessárias. O pseudocódigo para procurar a mediana de três valores espaçados em uma lista (matriz) é:

MID: = ⌊ (baixo + alto) / 2⌋
Se arr [Mid] < arr[low]
Swap arr [baixo] com arr [mid]
Se arr [alto] < arr[low]
Swap arr [baixo] com arr [alto]
Se arr [Mid] < arr[high]
Swap arr [Mid] com arr [alto]
pivô: = arr [alto]

O termo "arr" significa matriz. Este segmento de código procura a mediana e também faz alguma classificação. Este segmento de código parece simples, mas pode ser bastante confuso. Então, preste atenção à seguinte explicação:

A classificação neste tutorial produzirá uma lista em que o primeiro valor é o menor valor, e o último valor é o maior valor. Com o alfabeto, A é menor que Z.

Aqui, o pivô é a mediana resultante. O baixo é o menor índice da lista ou sub-lista (não necessariamente para o menor valor); High é o índice mais alto da lista ou sub-lista (não necessariamente para o valor mais alto), e o meio é o índice do meio convencional (não necessariamente para o valor médio de toda a lista).

Portanto, a mediana a ser obtida está entre o valor do menor índice, o valor do índice do meio e o valor do índice mais alto.

No código, o índice do meio convencional é obtido primeiro. Neste começo, a lista é não classificada. A comparação e algum rearranjo em ordem crescente dos três valores devem ocorrer ao mesmo tempo. A primeira estatura IF compara o valor para o menor índice e o do índice do meio. Se o do índice do meio for menor que o do índice mais baixo, os dois valores trocam posições. Isso começa a classificar e altera o arranjo de valores na lista ou sub-lista. A segunda estatização IF compara o valor para o índice mais alto e o do menor índice. Se o do índice mais alto for menor que o do índice mais baixo, os dois valores trocam posições. Isso continua com alguma classificação e mudança do arranjo de valores na lista ou sub-lista. A terceira estatura IF compara o valor para o índice do meio e o do mais alto índice. Se o do índice mais alto for menor que o índice do meio, os dois valores trocam posições. Alguma classificação ou rearranjo também pode ocorrer aqui. Esta terceira condição se não é como os dois anteriores.

No final desses três swaps, o valor médio dos três valores em questão seria um [alto], cujo conteúdo original poderia ter sido alterado no segmento de código. Por exemplo, considere a sequência não classificada:

C b a

Já sabemos que a mediana é B. No entanto, isso deve ser comprovado. O objetivo aqui é obter a mediana desses três valores usando o segmento de código acima. A primeira estatura se compara B e C. Se B for menor que C, as posições de B e C devem ser trocadas. B é menor que C, então o novo arranjo se torna:

B c a

Observe que os valores para o menor índice e o índice do meio mudaram. A segunda estatura se compara A e B. Se A for menor que B, as posições de A e B precisam ser trocadas. A é menor que B, então o novo arranjo se torna:

A c b

Observe que os valores para o índice mais alto e o menor índice mudaram. A terceira estatura se compara C e B. Se C for menor que B, as posições de C e B precisam ser trocadas. C não é menor que B, então nenhuma troca ocorre. O novo arranjo permanece como o anterior, ou seja:

A c b

B é a mediana, que é, um [alto], e é o pivô. Então, o pivô nasce no extremo extremo da lista ou sub-lista.

A função de troca

Outro recurso necessário para a classificação rápida é a função de troca. A função de troca, troca os valores de duas variáveis. O pseudocódigo para a função de troca é:

Definir troca (x, y)
Temp: = x
x: = y
y: = temp

Aqui, x e y se referem aos valores reais e não às cópias.

A classificação neste artigo produzirá uma lista em que o primeiro valor é o menor valor, e o último valor é o maior valor.

Conteúdo do artigo

• Algoritmo de classificação rápida
• Um pseudocódigo de partição
• Ilustração de classificação rápida
• Codificação Java
• Conclusão

Algoritmo de classificação rápida

A maneira normal de classificar uma lista não classificada é considerar os dois primeiros valores. Se não estiverem em ordem, coloque -os em ordem. Em seguida, considere os três primeiros valores. Digitalize os dois primeiros a ver onde o terceiro valor se encaixa e encaixe -o adequadamente. Então, considere os quatro primeiros valores. Digitalize os três primeiros valores para ver onde o quarto valor se encaixa e encaixe -o adequadamente. Continue com este procedimento até que toda a lista seja classificada.

Este procedimento, também conhecido como o tipo de força bruta, na linguagem de programação de computadores, é muito lenta. O algoritmo de classificação rápido vem com um procedimento muito mais rápido.

As etapas para o algoritmo do Quicksort são as seguintes:

1. Verifique se há pelo menos 2 números para classificar na lista não classificada.
2. Obter um valor central estimado para a lista, chamado de pivô. A mediana, como descrito acima, é uma maneira de obter o pivô. Diferentes maneiras vêm com suas vantagens e desvantagens. - Veja mais tarde.
3. Partição da lista. Isso significa, coloque o pivô na lista. Dessa forma, todos os elementos à esquerda são menores que o valor do pivô, e todos os elementos à direita são maiores ou iguais ao valor do pivô. Existem diferentes maneiras de particionar. Cada método de partição vem com suas vantagens e desvantagens. O particionamento está se dividindo no paradigma de divisão e conquista.
4. Repita as etapas 1, 2 e 3 recursivamente para os novos pares de sub-lista que emergem até que toda a lista seja classificada. Isso está conquistando o paradigma de divisão e conquista.

O pseudocode rápido é:

Algoritmo Quicksort (arr, baixo, alto) é
se baixo < high then
pivô (baixo, alto)
P: = Partição (arr, baixa, alta)
Quicksort (arr, Low, p - 1)
Quicksort (arr, p + 1, alto)

Um pseudocódigo de partição

O pseudocódigo de partição usado neste tutorial é:

Partição de algoritmo (ARR, baixa, alta) é
pivô: = arr [alto]
i: = baixo
J: = alto
fazer
fazer
++eu
enquanto (arr [i] < pivot)
fazer
--j
enquanto (arr [j]> pivô)
se eu < j)
Swap arr [i] com arr [j]
enquanto eu < j)
Swap arr [i] com arr [alto]
retornar i

Na ilustração da classificação rápida abaixo, este código é usado:

Ilustração de classificação rápida

Considere a seguinte lista não classificada (matriz) de cartas alfabéticas:

Q W E R T Y U I O P

Por inspeção, a lista classificada é:

E i o p q r t u w y

A lista classificada agora será comprovada, usando os segmentos de algoritmo e pseudocódigo acima, da lista não classificada:

Q W E R T Y U I O P

O primeiro pivô é determinado a partir de arr [0] = q, arr [4] = t e arr [9] = p, e é identificado como q e colocado no extremo direito da lista. Então, a lista com qualquer função pivô se torna:

P w e r t y u i o q

O pivô atual é q. O procedimento pivô fez uma pequena classificação e colocou P na primeira posição. A lista resultante deve ser reorganizada (particionada), de modo que todos os elementos à esquerda são menores em valor, depois o pivô e todos os elementos à direita do pivô, são iguais ou maiores que o pivô. O computador não pode fazer partição por inspeção. Então, isso faz usando os índices e o algoritmo de partição acima.

Os índices baixos e altos agora são 0 e 9. Portanto, o computador começará a digitalizar o índice 0 até atingir um índice, cujo valor é igual ou maior que o pivô e para lá temporariamente. Ele também escaneará a partir da extremidade alta (à direita), o índice 9, descendo, até atingir um índice cujo valor é menor ou igual ao pivô e para lá temporariamente. Isso significa duas posições de parada. Se eu, a variável de índice incremental, de baixa ainda não for igual ou maior que a variável de índice decrescente, J de alta, esses dois valores serão trocados. Na situação atual, a digitalização de ambas as extremidades parou em W e O. Então a lista se torna:

P e r t y u i w q

O pivô ainda é q. A digitalização em direções opostas continua e para de acordo. Se eu ainda não for igual ou maior que J, os dois valores nos quais a digitalização de ambas as extremidades paradas são trocadas. Desta vez, a digitalização de ambas as extremidades parou em r e eu. Então, o arranjo da lista se torna:

P e i t y u r w q

O pivô ainda é q. A digitalização em direções opostas continua e para de acordo. Se eu ainda não for igual ou maior que J, os dois valores nos quais a digitalização foram interrompidos, são trocados. Desta vez, a digitalização de ambas as extremidades parou em t para i e eu para j. Eu e J nos conhecemos ou cruzamos. Então, não pode haver troca. A lista permanece a mesma que:

P e i t y u r w q

Neste ponto, o pivô, Q, deve ser colocado em sua posição final na classificação. Isso é feito trocando arr [i] com arr [alta], trocando t e q. A lista se torna:

P e i q y u r w t

Neste ponto, a partição para toda a lista terminou. O pivô = Q desempenhou seu papel. Agora existem três sub-listas, que são:

P e i q y u r w t

A partição é divisão e conquista (classificação) no paradigma. Q está em sua posição de classificação correta. Cada elemento à esquerda de Q é menor que o Q, e todo elemento à direita de Q é maior que q. No entanto, a lista de esquerda ainda não é classificada; e a lista certa ainda não está classificada. Toda a função de classificação rápida deve ser chamada recursivamente para classificar a sub-lista esquerda e a sub-lista direita. Essa lembrança de classificação rápida tem que continuar; Novas sub-listas se desenvolverão até que toda a lista original seja completamente classificada. Para cada lembrança da função de classificação rápida, a sub-lista esquerda é atendida primeiro antes que a sub-lista direita correspondente seja atendida. Um novo pivô deve ser obtido para cada sub-lista.

Para a sub-lista:

P O E I

O pivô (mediano) para p, o e eu é determinado. O pivô seria o. Para esta sub-lista, e relacionado à lista completa, o novo arr [baixo] é arr [0], e o novo arr [alto] é o último arr [i-1] = arr [4-1] = arr [ARR [3], onde eu é o índice de pivô final da partição anterior. Depois que a função pivot () foi chamada, o novo valor do pivô, pivô = o. Não confunda entre a função pivô e o valor do pivô. A função pivô pode fazer uma pequena classificação e colocar o pivô à direita extrema da sub-lista. Esta sub-lista se torna,

Eu p e o

Com esse esquema, o pivô sempre termina na extremidade direita da sub-lista ou lista após sua chamada de função. A digitalização de ambas as extremidades começa no arr [0] e arr [3] até que eu e J nos conheço ou cruzem. A comparação é feita com pivô = o. As primeiras paradas estão em P e E. Eles são trocados e a nova sub-lista se torna:

Eu e P O

A digitalização de ambas as extremidades continua, e as novas paradas estão em P para i e em E para J. Agora eu e J nos conhecemos ou cruzamos. Portanto, a sub-lista permanece a mesma que:

Eu e P O

A partição de uma sub-lista ou lista termina quando o pivô foi colocado em sua posição final. Então, os novos valores para arr [i] e arr [alta] são trocados. Isto é, P e O são trocados. A nova sub-lista se torna:

Eu e o p

O está agora em sua posição final para toda a lista. Seu papel como pivô terminou. A sub-lista é atualmente particionada em mais três listas, que são:

Eu e o p

Neste ponto, um tipo rápido da primeira sub-lista à direita deve ser chamada. No entanto, não será chamado. Em vez disso, será observado e reservado, a ser chamado mais tarde. Como as declarações da função de particionamento estavam sendo executadas, a partir do topo da função, é do tipo rápido para a sub-lista esquerda que deve ser chamada agora (depois que o pivot () foi chamado). Será chamado para a lista:

Eu e

Vai começar procurando a mediana de eu e e. Aqui, arr [baixo] = i, arr [mid] = i e arr [alto] = e. Portanto, a mediana, pivô, deve ser determinada pelo algoritmo pivô como, eu. No entanto, o pseudocódigo de pivô acima determinará o pivô como e. Este erro ocorre aqui porque o pseudocódigo acima é destinado a três elementos e não dois. Na implementação abaixo, há algum ajuste no código. A sub-lista se torna,

E i

O pivô sempre termina na extremidade direita da sub-lista ou lista após sua chamada de função. A digitalização de ambas as extremidades começa no ARR [0] e ARR [1] exclusivo até que eu e J conheçam ou cruzem. A comparação é feita com pivô = eu. A primeira e única parada está em i e e: em i para i e em e para j. Agora eu e J nos conhecemos ou cruzamos. Então, a sub-lista permanece a mesma que:

E i

A partição de uma sub-lista ou lista termina quando o pivô foi colocado em sua posição final. Então, os novos valores para arr [i] e arr [alta] são trocados. Acontece aqui que arr [i] = i e arr [alto] = eu. Então, o mesmo valor é trocado por si mesmo. A nova sub-lista se torna:

E i

Agora estou em sua posição final para toda a lista. Seu papel como pivô terminou. A sub-lista agora é particionada em mais duas listas, que são,

E i

Agora, os pivôs até agora foram Q, O e eu. Pivôs terminam em suas posições finais. Uma sub-lista de um único elemento, como o P acima, também termina em sua posição final.

Neste ponto, a primeira sub-lista esquerda foi completamente classificada. E o procedimento de classificação está agora em:

E i o p q y u r w t

A primeira sub-lista à direita:

Você é

ainda precisa ser classificado.

Conquistando a primeira sub-lista direita
Lembre-se de que a chamada rápida para a primeira sub-lista à direita foi observada e reservada em vez de ser executada. Neste ponto, será executado. E assim, o novo arr [baixo] = arr [5] = arr [qpivotindex+1], e o novo arr [alto] permanece arr [9]. Um conjunto semelhante de atividades que aconteceram para a primeira sub-lista de esquerda acontecerá aqui. E esta primeira sub-lista à direita é classificada para:

R t u w y

E a lista original não classificada foi classificada para:

E i o p q r t u w y

Codificação Java

Colocar o algoritmo em Java é apenas para colocar todos os segmentos de pseudocódigo acima nos métodos Java em uma classe. Não se esqueça que precisa haver um método principal () na classe que chamará a função Quicksort () com a matriz não classificada.

O método pivot ()

O método java pivot () que retorna o valor, pivô, deve ser:

Void Pivot (char arr [], int baixo, int alto)
int mid = (baixo + alto) / 2;
se (arr [mid] < arr[low])
troca (arr, baixa, média);
if (arr [alto] < arr[low])
troca (arr, baixa, alta);
if ((alto - baixo)> 2)
se (arr [mid] < arr[high])
troca (arr, média, alta);

O método swap ()

O método swap () deve ser:

Void Swap (char arr [], int x, int y)
char temp = arr [x];
arr [x] = arr [y];
arr [y] = temp;

O método Quicksort ()

O método QuickSort () deve ser:

Void Quicksort (char arr [], int baixo, int alto)
se (baixo < high)
pivô (arr, baixo, alto);
int p = partição (arr, baixa, alta);
Quicksort (arr, baixo, p - 1);
Quicksort (arr, p + 1, alto);

O método partition ()

O método partition () deve ser:

int partitio (char arr [], int baixo, int alto)
char pivot = arr [alto];
int i = baixo;
int j = alto;
fazer
fazer
++eu;
enquanto (arr [i] < pivot);
fazer
--j;
enquanto (arr [j]> pivô);
se eu < j)
troca (arr, i, j);
enquanto eu < j);
trocar (arr, i, alto);
retornar i;

O método principal ()

O método principal () pode ser:

public static void main (string [] args)
char arr [] = 'q', 'w', 'e', ​​'r', 't', 'y', 'u', 'i', 'o', 'p';
Theclass Quicksort = new TheClass ();
Ordenação rápida.Quicksort (arr, 0, 9);
Sistema.fora.println ("Os elementos classificados:");
para (int i = 0; i<10; i++)
Sistema.fora.impressão (arr [i]); Sistema.fora.imprimir(");

Sistema.fora.println ();

Todos os métodos acima podem ser colocados em uma classe.

Conclusão

Quick Sort é um algoritmo de classificação que usa o paradigma de divisão e conquista. Começa dividindo uma lista não classificada em duas ou três sub-listas. Neste tutorial, o Quick Sort dividiu uma lista em três sub-listas: uma sub-lista esquerda, uma lista do meio de um único elemento e uma sub-lista direita. Conquistar em Quick Class. Este tutorial explicou uma implementação de classificação rápida na linguagem do computador Java.