Tipo rápido pior caso

Eu estou trabalhando no programa apenas necessário no seguinte para entender melhor.

Qual é o pior momento de execução do Quicksort e o que pode causar esse pior desempenho de caso? Como podemos modificar o programa quicksort para atenuar esse problema?

Eu sei que tem o pior caso O(n^2) e eu sei que ocorre quando o pivot único elemento mínimo ou máximo. Minha pergunta é como posso modificar o programa para atenuar esse problema.

Um bom algoritmo será bom.

O desempenho do Quicksort depende do seu algoritmo de seleção de pivôs. O algoritmo de seleção de pivô mais ingênuo é apenas escolher o primeiro elemento como seu pivô. É fácil ver que isso resulta em um pior comportamento se seus dados já estiverem classificados (o primeiro elemento será sempre o min).

Existem dois algoritmos comuns para resolver esse problema: escolha aleatoriamente um pivô ou escolha a mediana de três. Aleatório é óbvio, então não vou entrar em detalhes. A mediana de três envolve a seleção de três elementos (geralmente o primeiro, o meio e o último) e a escolha da mediana desses como o pivô.

Como os geradores de números randoms são tipicamente pseudo-randoms (portanto determinísticos) e uma mediana não aleatória de três algoritmos é determinística, é possível construir dados que resultem em um comportamento de pior caso, no entanto, é raro que surja em uso normal.

Você também precisa considerar o impacto no desempenho. O tempo de execução do seu gerador de números randoms afetará o tempo de execução do seu quicksort. Com mediana de três, você está aumentando o número de comparações.

Pior Condição de Desempenho:

Quando cada pivô escolhido for “maior” ou “menor” e esse padrão se repetir

Então, para 1 3 5 4 2

Se pivôs são escolhidos em ordem 1,2,3,4,5 ou 5,4,3,2,1

então o pior tempo de execução é O (n * n)

Como evitar o pior caso:

(1) Divida o array em cinco sets. Então se 1..100 os sets são (1..20) (21..40) (41..60) (61..80) (81..100)

(2) Escolha a mediana dos primeiros cinco elementos em cada conjunto (3) (23) (43) (63) (83)

(3) Agora escolha a mediana entre eles como o pivô então aqui está (43)

Uma modificação fácil é escolher o pivô aleatoriamente. Isso dá bons resultados com alta probabilidade .

Já faz um tempo, mas acho que o pior caso para o quicksort foi quando os dados já estavam classificados. Uma verificação rápida para ver se os dados já estão classificados pode ajudar a aliviar esse problema.

O pior tempo de execução depende do método de partição dentro da sorting rápida. Isso tem dois aspectos:

  • selecionando o pivô
  • como particionar em torno do pivô

Boas estratégias para selecionar o pivô foram delineadas em posts anteriores (mediana de medianas, ou mediana de três ou randomização). Mas, mesmo que o pivô seja sabiamente selecionado, no extremo, se um array tiver todos os elementos iguais, ele levará ao pior caso se apenas duas partições forem construídas, porque um carregará os elementos iguais, ou seja, todos os elementos:

  • isso faz com que partion seja chamado n vezes, cada uma tomando n / 2 em média levando a O (n²)
  • isso não é bom, porque não é um cenário de pior caso teórico, mas um bastante comum
  • Observe que isso não é resolvido detectando a partição vazia, porque o pivô pode ter o maior ou o menor valor de elemento (por exemplo, mediana é 5, que é também o maior valor de elemento, mas ainda pode haver alguns valores <5)

Uma forma de contornar esse problema é particionar em três partições, uma partição inferior (elementos Como faço para escolher entre uma tabela de hash e uma tree de prefixo (trie)?

  • Geo Esgrima – ponto dentro / fora do polígono
  • ajuda no algoritmo de Donald B. Johnson, não consigo entender o pseudo código (PARTE II)
  • Descubra se o ponto está no segmento de linha
  • Como mesclar dois BST com eficiência?
  • A maneira mais simples de criar uma matriz de inteiros a partir de 1..20 em JavaScript
  • Como o Algoritmo e o A-Star de Dijkstra se comparam?
  • Calcular o valor de n escolher k