Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort - Coggle Diagram
Quicksort
Complexidade
-
Caso médio
Partições feitas em qualquer parte do vetor, sem entrar na regra do melhor caso ou caso médio.
-
-
-
Execução
Seleção de pivô
A[i]
Percorre o lado esquerdo do pivô de forma crescente, ignorando elementos menores que o mesmo, parando ao encontrar elementos maiores ou iguais.
A[j]
Percorre o lado direito do pivô de forma decrescente, ignorando elementos maiores que o mesmo, parando ao encontrar elementos menores ou iguais.
OBS: Interrompendo a procura ao encontrar um elemento equivalente ao pivô, ajuda no desempenho do algoritmo, fazendo com que fique mais rápido, pois tende a render divisões mais uniformes das matrizes ao qual está se submetendo o método.
Quando os índices se cruzam, trocamos eles de posição e retornamos a varredura incrementando i e decrementando j.
Escolha do pivô
Uma das informações mais importantes do Quicksort a qual faz toda diferença no desempenho de execução do mesmo.
-
Pivô médio
Encontrar valor mediano entre três elementos do array. Primeiro elemento, elemento do meio e ultimo elemento.