Classificação rápida em C ++

Organizar as coisas em sequência é uma tarefa que realizamos na vida cotidiana, seja organizada em ordem crescente ou ordem decrescente. O processo de organizar as coisas em uma sequência adequada é chamado de classificação. Ascender está aumentando a ordem e a descendência está diminuindo a ordem. Na programação, também realizamos a classificação usando algoritmos diferentes. Mas um algoritmo fornece a classificação mais rápida que é "classificação rápida". Este algoritmo de classificação classifica a matriz mais rápido que os outros algoritmos. Funciona na regra de dividir e conquista, primeiro define um ponto de articulação e divide a matriz em dois sub-dores. Em seguida, defina um pivô para sub-maiores e o processo continua até chegarmos ao fim e a matriz necessária é classificada. Este artigo explica um trabalho aprofundado de uma classificação rápida em C ++ com um exemplo de codificação prática em ordem crescente.

Como selecionar um pivô

Antes de mudar para mais detalhes, é importante aprender como podemos selecionar um pivô para o algoritmo de classificação rápida.

• • Primeiro elemento
  • Último elemento
  • Elemento mediano
  • Elemento aleatório

Não há restrição para selecionar um pivô. Principalmente, definimos o último valor da matriz como um ponto de articulação.

Algoritmos:

A classificação rápida é feita usando dois algoritmos - um é particionar a matriz de acordo com o ponto dinâmico e o outro é para classificar a matriz.

Para particionar:

• • Tome duas variáveis ​​como o mais baixo e o mais alto.
  • Armazene o índice inicial da matriz no mais baixo e depois armazene o último índice no mais alto.
  • Defina outra variável e inicialize -a com a variável mais baixa como "iter".
  • Selecione o último membro da matriz para atuar como o pivô.
  • Passe pela matriz. Depois disso, combine cada elemento com o valor do pivô.
  • Se o elemento da matriz for menor que o pivô, incremente o "iter" e troque suas posições.
  • Incrementar o "i" por 1 e repito o processo até que o final da matriz seja alcançado. Rescindir o loop lá e devolver o iter-1.

O valor retornado nos dá a posição do índice pivô. Antes do pivô, existem os elementos menores que o valor do pivô. Após o pivô, existem os elementos maiores que o valor do pivô.

Para classificar:

Agora, passe para a classificação. Use as seguintes instruções para classificar uma matriz:

• • Escolha o último item da matriz para agir como o pivô.
  • O algoritmo de partição de índice retornado é o índice correto de um pivô.
  • O método do Quicksort é chamado nas subarraias esquerda e direita repetidamente.

Com a ajuda desses dois algoritmos, podemos executar a classificação rápida em qualquer matriz. Um exemplo do método de classificação rápido é elucidado no seguinte:

Classificação rápida em ordem crescente

Vamos explicar o método de "classificação rápida" para classificar uma matriz inteira em ordem crescente.

Código:

#incluir
usando namespace std;
Void Swap (int array_0 [], int position_1, int position_2)
int temp_0;
temp_0 = array_0 [posicionamento_1];
Array_0 [POSITION_1] = Array_0 [POSICION_2];
Array_0 [POSITION_2] = temp_0;
int partitio (int array_0 [], int baixo, int alto, int pivot)
int i_0 = baixo;
int j_0 = baixo;
enquanto (i_0 <= high) if(array_0[i_0] > pivot) i_0 ++;
else swap (array_0, i_0, j_0); i_0 ++; j_0 ++;
retornar j_0-1;

void Quicksort_0 (int array_0 [], int baixo, int alto)
se (baixo < high)
int pivot = array_0 [alto];
int position = partition (array_0, baixo, alto, pivô);
Quicksort_0 (Array_0, Low, Position-1);
Quicksort_0 (Array_0, posição+1, alto);
int main ()

int n [4] = 12,3,8,6;
Quicksort_0 (n, 0, 3);
cout<<"The sorted array is: ";
para (int i = 0; i < 4 ; i++) cout<< n[i]<<"\t";

Inicie o código importando a biblioteca e inclua o espaço de nome padrão. Depois disso, defina um método chamado "Swap" do tipo de retorno vazio. Nesta função, passe três parâmetros com tipo inteiro. Os dois argumentos, "POSITION_1" e "POSITION_2", são usados ​​para posições. O terceiro, "temp_0", é uma matriz. O método troca as posições dos elementos da matriz. A variável chamada "temp_0" é declarada para salvar temporariamente o valor. Além disso, inicialize este "temp_0" com a primeira posição da matriz. Em seguida, atribua a segunda posição da matriz à primeira posição de uma matriz "Position_1". E atribua a temperatura à segunda posição da matriz, que é "POSITION_2". Isso funciona como A = B; b = c; c = a. Este método executa apenas a troca.

Além disso, defina outra função para a partição. Este método divide a matriz em duas partes e divide ainda mais os sub-maiores de arremetidos. Esta função é um método do tipo de retorno e retorna um valor inteiro que contém o índice correto do pivô. Este método partition () tem quatro argumentos do tipo inteiro. Primeiro é uma matriz de "Array_0", a segunda é "baixa" que armazena o índice de partida da matriz, o terceiro é "alto", que contém o último índice da matriz, e o quarto é "pivô". Dentro deste método, inicialize duas variáveis ​​- "i_0" e "j_0" - com "baixo". Essas duas variáveis ​​têm um tipo de dados "int". Como sabemos, "baixo" contém o índice inicial da matriz. Na linha seguinte, use o loop "while" para iterar na matriz. Primeiro, defina a condição de "" while "como i_0 <= high. Iterate until we reach the last index of the array. Inside the “while” loop, employ the “if” decision-making statement to check whether the array elements are greater than the pivot or not. If this condition is fulfilled, the body of “if” executes which increments the iterator. Otherwise, the body of “else” is run. In the body of “else”, we callthe swap() method that swaps the array values until they are in ascending order. Outside the “while”, return the “j_0-1” to the function. Because that is incremented in the “else” part.

Defina outro método quicksort () do tipo de retorno vazio para executar a classificação rápida. Três argumentos - "Array_0", "Baixo" e "Alto" - com um tipo de número inteiro são fornecidos a esta função. Além disso, defina a condição "se". Se "baixo" for menor que o "alto", inicialize o "pivô" com o último índice da matriz "alto". Para a variável "posição", ligue para o método partition (). Em seguida, invocará recursivamente a função Quicksort () nas sub-maiores direita e esquerda.

Na última parte do código, empregue o método principal (). Em seguida, inicialize uma matriz do tipo "int" e ligue para o método quicksort_0 (). Esta função contém três argumentos. Ele executa uma classificação rápida na matriz especificada e classifica esta matriz. Digite o “cout<<” command to print the “The sorted array is:” line. To display the sorted array, use a “for” loop and iterate until the end of the array is reached.

Saída:

A matriz classificada é: 3 6 8 12

Conclusão

Classificação rápida no C ++ é discutida neste guia. Na programação, é necessário organizar as matrizes em ordem ascendente ou decrescente. Existem vários algoritmos de classificação, como tipo de bolha, classificação de mesclagem, etc. Rápido classificar é um deles, mas como o nome diz, ele classifica a matriz mais rapidamente do que outros. Este artigo explica o que é um pivô, qual elemento da matriz pode ser o pivô, cujos algoritmos são usados ​​para classificação rápida e como eles se apresentam. Este artigo termina com o Código de C ++, onde implementamos a classificação rápida.