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 com Mesclar classificação by Mozilla Firefox com 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).