Quick Sort é bastante semelhante ao tipo de fusão, no sentido de que este algoritmo ajuda os programadores a dividir e conquistar. Ele escolhe elementos como um pivô, após o qual cria divisórias na matriz. A classificação Quick Sort tem numerosas versões e cada uma delas escolhe o pivô de forma diferente.

O comando partição() é sem dúvida a parte mais importante da ordenação rápida. Os alvos da partição recebem uma matriz juntamente com um elemento de matriz x como pivô. Você tem que colocar o x na posição correta, que é a matriz ordenada, que será seguida pela colocação de elementos menores que o x antes dele. Finalmente, você tem que colocar elementos maiores do que x depois dele. Certifique-se de fazer tudo isso em tempo linear.

Também vale a pena ter em mente que a ordenação rápida cria divisórias em arrays, após o que ela se chama em repetição duas vezes para ordenar os subarrays resultantes dela. Um algoritmo como este vem em incrivelmente útil para grandes conjuntos de dados. Isto porque O(n2) são suas piores complexidades de caso. Os dois termos iniciais existem para chamadas recursivas, enquanto o termo final vem a calhar no processo de partição. Os elementos menores do que o pivô são representados por k.

A quantidade de tempo que a classificação rápida geralmente leva depende da estratégia da partição, juntamente com a matriz de entrada.

Os três casos de classificação rápida

Como vários outros algoritmos de ordenação, a ordenação rápida também tem cenários de casos. Vamos discuti-los abaixo:

Pior caso

Este tipo de caso ocorre sempre que o processo de partição escolhe o menor ou maior elemento como pivô. Considerando a estratégia de partição discutida anteriormente, onde o elemento final é sempre escolhido como pivô, o pior cenário de lugar acabará ocorrendo quando a matriz for ordenada em ordem decrescente ou ascendente. A recorrência para o pior caso é a seguinte:

T(n) = T(0) + T(n-1) + (n)que é equivalente a T(n) = T(n-1) + (n)

Melhor caso

O melhor lugar acontece sempre que o processo de partição escolhe o elemento central para pivô. A recorrência para o melhor caso é a seguinte:

T(n) = 2T(n/2) + (n)

Caso médio

Deve-se considerar cada permutação de matriz e calcular o tempo que cada permutação leva para realizar uma análise de caso. É claro que este processo pode ser bastante complicado, mesmo para programadores experientes. Dito isto, levando o caso em consideração quando a divisória coloca O(n/9) junto com elementos O(9n/10) pode lhe dar uma estimativa de caso médio. A recorrência deste caso é a seguinte.

T(n) = T(n/9) + T(9n/10) + (n)

Perguntas comuns feitas sobre Quick Sort

Embora haja muitas perguntas feitas sobre o tipo rápido, as mencionadas abaixo são indiscutivelmente as mais comuns:

A classificação rápida é um algoritmo estável?

Bem, a implementação padrão da classificação rápida não tem estabilidade. Dito isto, é possível acrescentar estabilidade aos algoritmos de ordenação considerando o índice como parâmetro de comparação.

O que é a classificação rápida de três maneiras?

Sempre que um algoritmo de classificação rápida regular estiver em questão, escolhemos um elemento para atuar como pivô, criando uma partição na matriz. Depois disso, recorremos para os subarranjos presentes nos lados direito e esquerdo do pivô.

Quick Sort é um algoritmo de ordenação rápida no local?

De acordo com a definição ampla do algoritmo in-place, a classificação rápida se qualifica como este tipo de algoritmo de classificação. Isto porque ele utiliza espaço extra para armazenar chamadas recursivas de funções. Entretanto, ele não manipula a entrada de forma alguma.

Mais rápido que a maioria dos algoritmos de ordenação

Embora não se possa negar que a complexidade dos piores casos de classificação rápida é O(n2), mais do que a classificação por pilha, a classificação por fusão e inúmeros outros algoritmos de classificação, a classificação rápida é incrivelmente rápida. Uma das razões para isto é que você pode implementar eficientemente seu loop interno em vários tipos de dados e arquiteturas do mundo real.
Além disso, você pode implementar a classificação rápida de várias maneiras, simplesmente mudando a escolha do pivô. Ao fazê-lo, minimiza-se a ocorrência do pior caso para qualquer tipo de dado. Dito isto, os programadores geralmente preferem usar a ordenação por fusão sempre que houver muitos dados, especialmente se eles estiverem dentro do armazenamento externo.

E quanto ao uso da classificação rápida em listas vinculadas

Quando se trata de listas vinculadas, as coisas são bem diferentes por causa das diferenças presentes na alocação de memória da matriz. Os nós das listas vinculadas são bastante diferentes das matrizes e muitas vezes não são adjacentes na memória. O que há mais listas vinculadas permite que você insira itens no centro, algo que não é possível na matriz. Em tais cenários, os programadores preferem usar a ordenação por fusão, uma vez que esta se mostra uma opção mais viável em comparação com a ordenação rápida.

Por que os programadores preferem a ordenação rápida em vez da ordenação de arrays

Em sua essência, a classificação rápida é uma classificação simples no local, o que significa que não precisa de armazenamento extra. Por outro lado, a separação por fusão precisa de O(N) de armazenamento extra. Para aqueles que estão se perguntando, o N denota o tamanho da matriz, que poderia ser incrivelmente extensa. Desalocar e alocar o espaço extra necessário para a separação de O(N) aumenta o tempo de funcionamento do algoritmo.

Uma vez comparada a complexidade média, é fácil ver que a complexidade média de ambos os tipos de ordenação é O(NlogN). Entretanto, suas constantes tendem a ser diferentes. Quando se trata de matrizes, a classificação de O(N) de fusão não tem sucesso porque utiliza o espaço adicional de armazenamento de O(N). As implementações mais práticas de ordenação rápida fazem uso de versões aleatórias. A complexidade média de tempo desta versão é O(nLogn). Também vale a pena ter em mente que há uma possibilidade de pior caso com a versão randomizada. No entanto, ela não aparece para padrões específicos, tais como a ordenação por matriz.

O algoritmo de classificação rápida é bastante amigável devido a sua excelente localização de referência, particularmente quando se o utiliza para arrays. Além disso, a classificação rápida também é recursiva, o que significa que você tem que realizar otimizações de chamadas de cauda.