Classificação rápida em JavaScript
Como o algoritmo de classificação rápido funciona
O algoritmo do Quicksort escolhe um elemento e o considera um elemento dinâmico; agora o elemento dinâmico é reservado.
Em seguida, levaremos os dois ponteiros 'P' e 'q'.
O ponteiro 'P' se moverá do lado esquerdo para o lado direito e não parará até encontrar um maior ou igual ao elemento dinâmico.
O segundo ponteiro 'q' se moverá do lado direito para o lado esquerdo e parará de pesquisar quando encontrar um elemento menor ou igual ao elemento dinâmico.
Então, 'P' classificará os elementos menores no lado esquerdo e 'q' classificará os elementos maiores para o lado direito.
Agora vamos entender o funcionamento do algoritmo de classificação rápida com a ajuda de um exemplo:
Suponha que tenhamos uma variedade de seis elementos e queremos classificá -la em ordem crescente usando um algoritmo do QuickSort:
Na etapa inicial, selecionamos '36' como um elemento dinâmico (elemento médio):
Na próxima etapa, selecionamos nossos ponteiros, o ponteiro 'P' para passar da esquerda para a direita e 'q' ponteiro para se mover do lado direito para o lado esquerdo:
Agora, o valor do ponteiro esquerdo 'P' será comparado com o valor do pivô, pois '35' é menor que '36' move o ponteiro 'P' para o elemento adjacente. Por outro lado, compare o valor do ponteiro direito 'q' com o valor do pivô, '39' é maior que '36', então o ponteiro 'q' se moverá para o elemento adjacente esquerdo:
Agora, o ponteiro 'P' está apontando para '33' e é comparado com o pivô '36', o valor do ponteiro 'P' é menor que o valor do pivô, portanto o ponteiro 'P' será transferido para o elemento adjacente. Enquanto o valor do ponteiro 'q' '32' é menor que o valor do pivô '36', então ele vai parar por aqui:
O valor do ponteiro esquerdo '37' é maior que o valor do pivô '36', então, também vai parar por aqui. Agora, 'P' para em '37' e 'q' para em '32'.
Agora vamos verificar se o ponteiro 'P' atravessa o ponteiro 'q' ou não. Nesse caso, até agora 'P' não atravessa o ponteiro 'q', então trocaremos o valor do ponteiro 'P' com o valor do ponteiro 'q':
Agora 'P' e 'Q' estão apontando para '32' e '37', respectivamente, mude os ponteiros mais uma vez, agora p = q ('36 '=' 36 '):
Mova os ponteiros mais uma vez, pois o ponteiro 'P' atravessa o ponteiro 'Q', então aqui, ele parará e retornará o índice de 'P' Pointer. Até agora, o elemento dinâmico está em sua posição correta e todos os elementos maiores que o elemento dinâmico estão no lado direito do pivô, e todos os elementos menos que os elementos dinâmicos estão no lado esquerdo do pivô. Dessa forma, vamos classificar toda a lista.
Agora vamos implementar esse conceito em javascript. Primeiro, o código para trocar elementos:
função swap_elements (elementos, esquerd_index, right_index)var temp = elementos [esquerd_index];
elementos [esquerd_index] = elementos [right_index];
elementos [right_index] = temp;
Em seguida, o código para dividir uma lista em sub-listas:
função sub_lists (elementos, esquerd_pointer, right_pointer)var pivot = elementos [matemática.piso ((direita_pointer + esquerd_pointer) / 2)],
i = esquerd_pointer,
j = right_pointer;
enquanto eu <= j)
while (elementos [i] pivô)
J--;
if (i 1)
index = sub_lists (elementos, esquerd_pointer, right_pointer);
if (esquerd_pointer < index - 1)
Quick_sort (Elements, Left_Pointer, Index - 1);
if (índice < right_pointer)
Quick_sort (Elements, Index, Right_Pointer);
elementos de retorno;
Criamos uma função que leva três parâmetros dentro da função. Dividimos a lista inteira em sub-listas e descobrimos o ponteiro esquerdo e o ponteiro direito e escrevemos o código para incrementar o ponteiro esquerdo, se for menor que o elemento dinâmico e diminuir o ponteiro direito se for maior que o elemento pivô:
Agora vamos escrever o código para lidar com o comportamento recursivo da classificação rápida. Como na etapa acima, o índice de Left_Pointer é retornado e o utilizaremos para dividir a lista em sub-listas e aplicar o Quicksort nessas sub-listas:
função Quick_sort (Elements, Left_Pointer, Right_Pointer)Índice var;
if (elementos.comprimento> 1)
index = sub_lists (elementos, esquerd_pointer, right_pointer);
if (esquerd_pointer < index - 1)
Quick_sort (Elements, Left_Pointer, Index - 1);
if (índice < right_pointer)
Quick_sort (Elements, Index, Right_Pointer);
elementos de retorno;
O trecho completo do código será assim:
var elements = [35,33,37,36,32,39];função swap_elements (elementos, esquerd_index, right_index)
var temp = elementos [esquerd_index];
elementos [esquerd_index] = elementos [right_index];
elementos [right_index] = temp;
função sub_lists (elementos, esquerd_pointer, right_pointer)
var pivot = elementos [matemática.piso ((direita_pointer + esquerd_pointer) / 2)],
i = esquerd_pointer,
j = right_pointer;
enquanto eu <= j)
while (elementos [i] pivô)
J--;
if (i 1)
index = sub_lists (elementos, esquerd_pointer, right_pointer);
if (esquerd_pointer < index - 1)
Quick_sort (Elements, Left_Pointer, Index - 1);
if (índice < right_pointer)
Quick_sort (Elements, Index, Right_Pointer);
elementos de retorno;
var stored_array = Quick_sort (elementos, 0, elementos.comprimento - 1);
console.log ("A lista classificada:", classificada_array);
Inicializamos a matriz não classificada no início do programa e no final do programa que chamamos de função "Quick_Sort ()" para obter a matriz final classificada:
Finalmente, quando executamos este código, obtemos a saída resultante como:
Conclusão:
O Quicksort é um algoritmo de classificação que funciona na filosofia de dividir e conquistar e dividir o problema em subproblemas menores. E continue esse processo até atingir a meta resultante. Neste artigo, discutimos como o QuickSort funciona e implementamos esse conceito em JavaScript para resolver qualquer matriz da maneira mais eficiente.