Algoritmo QuickSort em JavaScript

O que é a classificação rápida?

O algoritmo de classificação rápida segue a abordagem de divisão e conquista. Ele divide os elementos em partes menores com base em alguma condição e realiza as operações de classificação nessas partes menores divididas.

O algoritmo de classificação rápida é um dos algoritmos mais usados e populares em qualquer linguagem de programação. Mas, se você for um desenvolvedor de JavaScript, talvez já tenha ouvido falar de sort (), que já está disponível em JavaScript. Então, você deve estar pensando qual é a necessidade desse algoritmo de classificação rápida. Para entender isso, primeiro precisamos o que é classificação e qual é a classificação padrão em JavaScript.

O que é classificação?

Classificar nada mais é do que organizar os elementos na ordem que desejamos. Você pode ter se deparado com isso em sua escola ou na faculdade. Como organizar os números do menor para o maior (crescente) ou do maior para o menor (decrescente) é o que vimos até agora e é chamado de classificação.

Classificação padrão em JavaScript

Conforme mencionado anteriormente, o JavaScript possui sort () . Vamos dar um exemplo com poucos array de elementos como [5,3,7,6,2,9] e queremos classificar os elementos desse array em ordem crescente. Basta chamar sort () no array de itens e ele classifica os elementos do array em ordem crescente.

Código:

var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]

Qual é a razão para escolher a classificação rápida em vez da classificação padrão () em JavaScript

Embora sort () forneça o resultado que queremos, o problema está na maneira como ele classifica os elementos do array. A classificação padrão () em JavaScript usa a classificação por inserção pelo V8 Engine do Chrome e a classificação por mesclagem pelo Mozilla Firefox e Safari .

Porém, isso não é adequado se você precisar classificar um grande número de elementos. Portanto, a solução é usar a classificação rápida para grandes conjuntos de dados.

Portanto, para entender completamente, você precisa saber como funciona a classificação rápida e vamos ver isso em detalhes agora.

O que é classificação rápida?

A classificação rápida segue o algoritmo Divide and Conquer . Ele divide os elementos em partes menores com base em alguma condição e realiza as operações de classificação nessas partes menores divididas. Portanto, funciona bem para grandes conjuntos de dados. Então, aqui estão as etapas de como a classificação rápida funciona em palavras simples.

Primeiro selecione um elemento que deve ser chamado de elemento pivô .
Em seguida, compare todos os elementos da matriz com o elemento pivô selecionado e organize-os de forma que os elementos menores que o elemento pivô estejam à sua esquerda e maiores que o pivô à sua direita.
Finalmente, execute as mesmas operações nos elementos do lado esquerdo e direito do elemento pivô.

Portanto, esse é o esboço básico da classificação rápida. Aqui estão as etapas que precisam ser seguidas uma a uma para realizar a classificação rápida.

Como funciona o QuickSort

Primeiro encontre o elemento "pivô" na matriz.
Inicie o ponteiro esquerdo no primeiro elemento da matriz.
Inicie o ponteiro direito no último elemento da matriz.
Compare o elemento que aponta com o ponteiro esquerdo e se for menor que o elemento pivô, mova o ponteiro esquerdo para a direita (adicione 1 ao índice esquerdo). Continue até que o elemento do lado esquerdo seja maior ou igual ao elemento pivô.
Compare o elemento que aponta com o ponteiro direito e, se for maior que o elemento pivô, mova o ponteiro direito para a esquerda (subtraia 1 para o índice direito). Continue até que o elemento do lado direito seja menor ou igual ao elemento pivô.
Verifique se o ponteiro esquerdo é menor ou igual ao ponteiro direito e veja os elementos nas localizações desses ponteiros.
Aumente o ponteiro esquerdo e diminua o ponteiro direito.
Se o índice do ponteiro esquerdo ainda for menor que o índice do ponteiro direito, repita o processo; caso contrário, retorne o índice do ponteiro esquerdo.

Então, vamos ver essas etapas com um exemplo. Vamos considerar o array de elementos que precisamos classificar como [5,3,7,6,2,9].

Determine o elemento Pivot

Mas antes de prosseguir com a classificação rápida, selecionar o elemento pivô desempenha um papel importante. Se você selecionar o primeiro elemento como o elemento pivô, ele terá o pior desempenho na matriz classificada. Portanto, é sempre aconselhável escolher o elemento do meio (comprimento do array dividido por 2) como o elemento pivô e fazemos o mesmo.

Aqui estão as etapas para realizar a classificação rápida que está sendo mostrada com um exemplo [5,3,7,6,2,9].

PASSO 1: Determine o pivô como o elemento do meio. Portanto, 7 é o elemento pivô.

PASSO 2: Inicie os ponteiros para a esquerda e para a direita como o primeiro e o último elemento da matriz, respectivamente. Portanto, o ponteiro esquerdo está apontando para 5 no índice 0 e o ponteiro direito está apontando para 9 no índice 5.

PASSO 3: Compare o elemento no ponteiro esquerdo com o elemento pivô. Uma vez que, 5 <6 desloca o ponteiro esquerdo para a direita para o índice 1.

PASSO 4: Agora, ainda 3 <6, então mude o ponteiro esquerdo para mais um índice à direita. Portanto, agora 7> 6 pare de incrementar o ponteiro esquerdo e agora o ponteiro esquerdo está no índice 2.

PASSO 5: Agora, compare o valor do ponteiro direito com o elemento pivô. Como 9> 6 mova o ponteiro direito para a esquerda. Agora, como 2 <6, pare de mover o ponteiro direito.

PASSO 6: Troque os valores presentes nos ponteiros esquerdo e direito entre si.

PASSO 7: Mova os dois ponteiros mais uma etapa.

PASSO 8: Como 6 = 6, mova os ponteiros para mais uma etapa e pare quando o ponteiro esquerdo cruzar o ponteiro direito e retornar o índice do ponteiro esquerdo.

Portanto, aqui com base na abordagem acima, precisamos escrever código para trocar elementos e particionar o array conforme mencionado nas etapas acima.

Código para trocar dois números em JavaScript:

function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}

Código para executar a partição conforme mencionado nas etapas acima:

function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}

Execute a operação recursiva

Depois de realizar as etapas acima, o índice do ponteiro esquerdo será retornado e precisamos usá-lo para dividir o array e realizar a classificação rápida nessa parte. Por isso, é chamado de algoritmo Divide and Conquer.

Portanto, a classificação rápida é realizada até que todos os elementos na matriz esquerda e na matriz direita sejam classificados.

Nota: A classificação rápida é executada na mesma matriz e nenhuma nova matriz é criada no processo.

Portanto, precisamos chamar essa partição () explicada acima e com base nisso dividimos o array em partes. Então, aqui está o código onde você o usa,

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Código de classificação rápida completo:

var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]