Algoritmo QuickSort em JavaRoteiro com exemplo

O que é Classificação Rápida?

Ordenação rápida é um algoritmo de classificação por comparação que segue o Dividir e conquistar abordagem. Ela seleciona um elemento como pivô, divide a matriz em uma parte que contém valores menores que o pivô e uma parte que contém valores maiores, e então aplica o mesmo procedimento a cada parte até que toda a matriz esteja ordenada.

O Quick Sort é um dos algoritmos de ordenação mais utilizados em todas as linguagens de programação. Se você escrever JavaScript, você provavelmente já usou o recurso integrado ordenar() método, então você pode se perguntar por que vale a pena aprender uma implementação separada do Quick Sort. Para responder a isso, primeiro você precisa saber o que significa ordenação e qual é a ordenação padrão em JavaO roteiro realmente faz isso.

Três propriedades definem o Quick Sort:

• Em vigor: reorganiza o original ordem e não aloca uma segunda matriz do mesmo tamanho.
• Recursivo: Cada partição produz dois intervalos menores que são ordenados pela mesma função.
• Instável: Dois elementos com chaves iguais podem acabar em uma ordem relativa diferente daquela em que começaram.

O que é classificação?

Ordenar significa organizar elementos em uma ordem definida. Você quase certamente já viu isso na escola: colocar números do menor para o maior é... ascendente ordenar e colocá-los do maior para o menor é descendente A ordenação não se limita a números. Cadeias de caracteres podem ser ordenadas alfabeticamente, datas cronologicamente e objetos por qualquer campo que você escolher, como preço ou pontuação.

A ordenação é importante porque dados ordenados permitem operações mais rápidas. Uma busca binária tem complexidade de tempo O(log n), mas apenas em entradas já ordenadas. Operações como remoção de duplicatas, consultas por intervalo, classificação e mesclagem tornam-se muito mais eficientes quando os dados estão ordenados, e é por isso que toda linguagem de programação inclui pelo menos uma rotina de ordenação.

Classificação padrão em JavaScript

Como mencionado anteriormente, JavaO script fornece ordenar()Considere um pequeno array, como [5,3,7,6,2,9], que você deseja ordenar em ordem crescente. Em seguida, chame o método. ordenar() O array parece fazer exatamente isso.

A captura de tela acima mostra o console do navegador imprimindo o array ordenado. Aqui está o mesmo código:

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

Saída:

[ 2, 3, 5, 6, 7, 9 ]

Esse resultado está correto, mas apenas por acaso. O método `Array.prototype.sort()` converte cada elemento em uma string e compara as strings. A menos que você forneça uma função comparadora. Cada valor nesta matriz é um único dígito, portanto a ordem da string coincide com a ordem numérica. Altere os dados e a ilusão se desfaz.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

Saída:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

Qual algoritmo a função sort() utiliza?

A especificação não nomeia um algoritmo, então cada mecanismo escolhe o seu próprio. Os mecanismos modernos usam um algoritmo baseado em mesclagem:

• V8 (Chrome, Edge, Node.js) foi usado TimSort Desde a versão 8.0, lançada no Chrome 7.0.
• Macaco aranha (Firefox) usa mesclar classificação.
• JavaScriptCore (Safari) também usa mesclar classificação.

Desde o ES2019, a linguagem garante que sort() is estável, o que descarta uma simples ordenação rápida (Quick Sort) dentro do mecanismo. A ordenação baseada em mesclagem (merge-based sort) precisa de memória auxiliar O(n) e deve chamar sua função. JavaUm comparador de script para cada comparação. Um algoritmo Quick Sort numérico escrito manualmente compara números diretamente e os ordena no próprio local, sendo, portanto, eficiente em grandes arrays numéricos. Ordenar 1,000,000 de números inteiros aleatórios no Node.js 22 levou aproximadamente [tempo não especificado]. 100 ms com a classificação rápida abaixo e aproximadamente 210 ms com as sort((a, b) => a - b).

Portanto, vale a pena escrever o Quick Sort quando você precisa de classificação no próprio local, controle rigoroso sobre a memória ou simplesmente uma compreensão sólida de como a classificação funciona. Vamos analisar a mecânica em detalhes.

Como funciona a classificação rápida?

A classificação rápida repete uma operação principal, chamada particionamento, em faixas cada vez menores. Aqui estão os passos em ordem:

1. Encontre o articulação elemento na matriz.
2. Inicie o ponteiro esquerdo no primeiro elemento do intervalo.
3. Inicie o ponteiro da direita no último elemento do intervalo.
4. Compare o elemento posicionado pelo ponteiro da esquerda com o pivô. Se for menor que o pivô, mova o ponteiro da esquerda uma posição para a direita. Continue até que o elemento da esquerda seja maior ou igual ao pivô.
5. Compare o elemento posicionado pelo ponteiro da direita com o pivô. Se for maior que o pivô, mova o ponteiro da direita uma posição para a esquerda. Continue até que o elemento da direita seja menor ou igual ao pivô.
6. Se o ponteiro da esquerda ainda for menor ou igual ao ponteiro da direita, troque os dois elementos.
7. Aumente o ponteiro esquerdo e diminua o ponteiro direito.
8. Se o índice da esquerda ainda for menor ou igual ao índice da direita, repita a partir do passo 4. Caso contrário, retorne o índice do ponteiro da esquerda.

O diagrama acima tracsão esses movimentos de ponteiro em um array de exemplo. Cada elemento menor que o pivô acaba à sua esquerda e cada elemento maior acaba à sua direita, que é exatamente o que o índice retornado indica. A seção abaixo percorre o mesmo array passo a passo.

Como determinar o elemento pivô

A escolha do ponto de pivô é a única decisão que diferencia uma classificação rápida do lento. Se você sempre escolher o ponto de pivô, a classificação será mais rápida. primeiro Se um elemento em um array já ordenado produzir a pior divisão possível: um lado vazio e um lado com todos os elementos restantes. Isso torna o algoritmo O(n²). Considerando o meio O elemento (o comprimento da matriz dividido por dois) evita essa armadilha para entradas ordenadas e invertidas, e é por isso que o código abaixo o utiliza.

Estratégias comuns de mudança de rumo:

• Primeiro ou último elemento: Mais simples de codificar, mas O(n²) em dados ordenados.
• Elemento intermediário: Uma boa solução padrão que lida com arrays ordenados e invertidos em O(n log n).
• Elemento aleatório: torna impossível construir antecipadamente a entrada no pior cenário.
• Mediana de três: Utiliza a mediana dos valores inicial, intermediário e final; a escolha padrão em bibliotecas de produção.

Agora, percorra o algoritmo de ordenação rápida (Quick Sort) na matriz. .

PASSO 1: O pivô é o elemento do meio. Com esquerda = 0 e direita = 5, Math.floor((5 + 0) / 2) fornece o índice 2, portanto o valor do pivô é 7.

PASSO 2: Comece os ponteiros nas extremidades da matriz. O ponteiro da esquerda está no índice 0 (valor 5) e o ponteiro direito está no índice 5 (valor 9).

PASSO 3: Compare o valor à esquerda com o pivô. 5 < 7, então mova para a direita para o índice 1. 3 < 7, então mova para a direita para o índice 2. O valor lá é 7, que não é menor que o pivô, então o ponteiro da esquerda para no índice 2.

PASSO 4: Compare o valor à direita com o pivô. 9 > 7, então mova para a esquerda até o índice 4. O valor lá é 2, que não é maior que o pivô, então o ponteiro da direita para no índice 4.

PASSO 5: O índice da esquerda (2) é menor ou igual ao índice da direita (4), então troque os dois valores. O array fica assim: .

PASSO 6: Mova ambos os ponteiros uma posição para dentro. O ponteiro da esquerda agora está no índice 3 e o ponteiro da direita também no índice 3.

PASSO 7: Repita a varredura. O valor no índice 3 é 6, e 6 < 7, então o ponteiro da esquerda avança para o índice 4. O valor no índice 3 não é maior que o pivô, então o ponteiro da direita permanece no índice 3.

PASSO 8: O índice da esquerda (4) agora é maior que o índice da direita (3), então o loop termina e a função retorna. 4Tudo o que for anterior ao índice 4 é menor ou igual ao pivô, e tudo o que for a partir do índice 4 é maior ou igual a ele.

Com base nesse passo a passo, você precisa de código para duas operações: troca.ping dois elementos e particionamento de um intervalo.

Code Trocar dois Numbers in JavaScript

Como mostra a captura de tela do editor acima, a função auxiliar de troca usa uma variável temporária para trocar os valores em dois índices. Ela modifica o array diretamente e não retorna nada.

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

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

Saída:

[ 9, 3, 7, 6, 2, 5 ]

Code Para realizar o particionamento

O código na captura de tela acima transforma os passos 1 a 8 em uma função. Os dois elementos internos laços avançar os ponteiros, o if O bloco realiza a troca e a função retorna o índice de divisão.

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;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

Saída:

[ 5, 3, 2, 6, 7, 9 ]
4

A saída corresponde exatamente ao passo a passo manual: após uma passagem de partição, a matriz é [5,3,2,6,7,9] e o índice de divisão retornado é 4.

Execute o processo recursivo. Operação

Após o particionamento retornar o índice de divisão, use-o para dividir o intervalo e execute o Quick Sort em cada metade. É por isso que ele é chamado de algoritmo de "dividir para conquistar". A recursão continua até que cada subintervalo contenha um único elemento, momento em que toda a matriz está ordenada.

Observação: O Quick Sort opera sempre no mesmo array. Nenhum novo array é criado durante o processo, o que o caracteriza como um algoritmo in-place.

Então você liga para o partição () função explicada acima e use seu valor de retorno para dividir o ordem em partes. Aqui está o código que faz isso:

Observe as duas condições de guarda destacadas na captura de tela. left < index - 1 confirma que pelo menos dois elementos permanecem no lado esquerdo, e index < right Confirma o mesmo para o lado direito. Sem essas proteções, a função se chamaria indefinidamente em intervalos de um único elemento.

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 items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

Saída:

[ 2, 3, 5, 6, 7, 9 ]

Classificação rápida completa Code

A junção das partes de troca, partição e recursão resulta na implementação completa:

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); // swapping 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);

Saída:

[ 2, 3, 5, 6, 7, 9 ]

A captura de tela acima mostra o programa completo no editor, juntamente com o array ordenado no console. Esta implementação foi verificada com um array já ordenado, um array ordenado inversamente, arrays contendo valores duplicados e idênticos, números negativos, um único elemento e um array vazio, retornando o resultado correto em todos os casos.

Complexidade de tempo e espaço da ordenação rápida

Cada passagem de partição toca em cada elemento do intervalo uma vez, portanto, uma única passagem custa O(n). O custo total, portanto, depende de quantas vezes o array pode ser dividido antes que os intervalos se tornem triviais.

A complexidade de espaço é O(log n) Para esta versão in-place, nenhum segundo array é alocado, então a única memória extra é a pilha de recursão, e a divisão balanceada mantém essa pilha com uma profundidade de aproximadamente log₂(n) frames. No pior caso degenerado, a pilha cresce para O(n) frames, razão pela qual arrays muito grandes podem causar estouro da pilha de chamadas.

Dois números tornam isso concreto. Ordenar 4,096 valores aleatórios com o código acima usou aproximadamente 65,000 comparações contra um valor teórico de n·log₂(n) de 49,152, e a recursão mais profunda atingiu 24 quadros, enquanto log₂(4096) é 12. Ambos os valores estão dentro do pequeno fator constante esperado de um algoritmo O(n log n).

Classificação Rápida vs. Outros Métodos de Classificação Algorithms

O Quick Sort raramente é a única opção. A tabela abaixo o compara com os outros algoritmos que você provavelmente encontrará, para que você possa escolher o mais adequado para seus dados.

Na prática, o Quick Sort geralmente se sai melhor porque seu laço interno é compacto e funciona bem em intervalos contíguos com boa gestão de cache. Escolha o merge sort quando precisar de uma resolução limitada por O(n log n) ou de uma ordenação estável, o heap sort quando a memória for extremamente limitada e o insertion sort para arrays muito pequenos ou quase ordenados. Bibliotecas de produção frequentemente combinam esses algoritmos: o introsort começa com o Quick Sort, muda para o heap sort se a recursão ficar muito profunda e termina com o insertion sort em intervalos pequenos.

Como classificar objetos e strings rapidamente

A implementação mostrada até agora compara valores com < e >, o que restringe a números. Aplicações reais precisam classificar. objetos por uma propriedade, strings em ordem alfabética ou datas em ordem cronológica. A solução é mover a comparação para um callback, exatamente como o integrado. sort() faz.

Um comparador recebe dois valores e retorna um número negativo quando o primeiro deve vir primeiro, um número positivo quando o segundo deve vir primeiro e zero quando os dois são equivalentes. Substituir as duas comparações codificadas por chamadas de comparador faz com que o algoritmo funcione com qualquer tipo de dado.

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

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

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

Saída:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

Três detalhes merecem destaque. A proteção contra recursão agora está left >= right, que é correto para qualquer intervalo e não depende do comprimento da matriz externa. A comparação de strings usa localeCompare() para que os caracteres acentuados e as maiúsculas e minúsculas sejam tratados corretamente, em vez de serem tratados pelo ponto de código bruto. E como a Classificação Rápida não é estável, os registros que compartilham o mesmo salário podem trocar de posição; classifique por uma segunda chave de desempate se a ordem original for importante para você.

Pronto para continuar? Fortaleça os fundamentos com o JavaIntrodução ao roteiro, pratique a mecânica do ponteiro em JavaRepetições de script, trabalhe mais prático JavaExemplos de código de script, comparar implementações em Ordem de inserção e Classificação de pilhaou adicione tipos estáticos a este algoritmo com o TypeScript referência.

Perguntas Frequentes