Question

Qual operação no algoritmo Quick Sort está diretamente relacionada com o desempenho do método?

Answer 1

A divisao do conjunto de dados(um vetor) em dois.

A ideia é simples. É mais rápido classificar dois meio vetores e juntá-los novamente ordenados do que classificar um vetor único.

O que o quick sort faz é exatamente isso. Ele pega um vetor, parte em dois. Os valores que forem menores que o mediano, ficam no primeiro vetor. Os valores que forem maiores que o mediano, ficam no segundo vetor. Aí classificamos cada um deles. O pulo do gato do quick sort é que esse raciocínio se aplica recursivamente, ou seja, cada meio vetor é um vetor. Aí partimos o meio vetor pela metade e repetimos o processo.

Estudos indicam que abaixo de um certo tamanho de vetor, algo perto de 50 elementos, a diferença de velocidade entre o quicksort e o bubble sorte é tão pequena que não compensa a complicaçao do quicksort. O bubble sort é menos eficiente porém é mais simples de implementar.

Então imagine um vetor que tem 2000 elementos.
Dividimos em 2 vetores de 1000
cada vetor de 1000 dividimos em 2 de 500
cada 500 divididimos em 2 de 250
cada de 250 dividimos em dois de 125
dividimos em um de 63 e outro de 62
dividimos o de 63 em um de 31 e outro de 32 (o de 62 em dois de 31)
aí temos vetores de 31 ou 32 valores e tacamos um bublle  sorte neles

É muuuuuuito mais rápido.