Algoritmo QuickSort 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 época de escola ou faculdade. Assim como organizar os números do menor para o maior (crescente) ou do maior para o menor (descendente) é o que vimos até agora e é chamado de classificação.

Classificação padrão em JavaScript

Como mencionado anteriormente, JavaO script tem ordenar(). Vamos dar um exemplo com poucos arrays de elementos como [5,3,7,6,2,9] e queremos classificar os elementos desse array em ordem crescente. Apenas ligue ordenar() na matriz de itens e classifica os elementos da matriz 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 é o motivo para escolher a classificação rápida em vez da classificação padrão () em JavaScript

Embora sort() forneça o resultado que desejamos, o problema está na maneira como ele classifica os elementos do array. Classificação padrão() em JavaO script usa tipo de inserção by Motor V8 do Chrome e Mesclar classificação by Mozilla Firefox e Safári.

Mas, por outro lado, 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.

Então, 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 Dividir e conquistar algoritmo. Ele divide os elementos em partes menores com base em alguma condição e executa 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.

1. Primeiro selecione um elemento que será chamado como articulação elemento.
2. Em seguida, compare todos os elementos da matriz com o elemento pivô selecionado e organize-os de tal forma que os elementos menores que o elemento pivô fiquem à sua esquerda e os maiores que o pivô estejam à sua direita.
3. Por fim, execute as mesmas operações nos elementos laterais esquerdo e direito do elemento pivô.

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

Como funciona o QuickSort

1. Primeiro encontre o "Pivô" elemento na matriz.
2. Inicie o ponteiro esquerdo no primeiro elemento do array.
3. Inicie o ponteiro direito no último elemento do array.
4. 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 assim até que o elemento do lado esquerdo seja maior ou igual ao elemento pivô.
5. 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 ao índice direito). Continue assim até que o elemento do lado direito seja menor ou igual ao elemento pivô.
6. Verifique se o ponteiro esquerdo é menor ou igual ao ponteiro direito e, em seguida, troque os elementos nas localizações desses ponteiros.
7. Aumente o ponteiro esquerdo e diminua o ponteiro direito.
8. 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 que a matriz de elementos que precisamos classificar é [5,3,7,6,2,9].

Determinar o elemento pivô

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

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

PASSO 1: Determine o pivô como elemento intermediário. Então, 7 é o elemento pivô.

PASSO 2: Comece os ponteiros esquerdo e direito como o primeiro e o último elementos da matriz, respectivamente. Então, 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ô. Desde então, 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. Então agora 7 > 6 param de incrementar o ponteiro esquerdo e agora o ponteiro esquerdo está no índice 2.

PASSO 5: Agora, compare o valor no 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 para a direita.

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

PASSO 7: Mova os dois ponteiros mais um passo.

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 realizar a partição conforme mencionado nas etapas acima

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

Execute a operação recursiva

Depois de executar 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. Portanto, é chamado de algoritmo Divide and Conquer.

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

Nota: A classificação rápida é executada no mesmo array e nenhum novo array é criado no processo.

Então, precisamos chamar isso partição () explicado acima e com base nisso dividimos o ordem 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 partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var 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 element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]

OBSERVAÇÃO: A classificação rápida é executada com a complexidade de tempo de O(nlogn).