Resumo de Quicksort (ordenação rápida)
Quicksort (Ordenação Rápida): Guia Completo para Estudantes
Quicksort: Algoritmo de Ordenação Rápida
Quicksort, ou ordenação rápida, é um dos algoritmos de ordenação mais eficientes e amplamente utilizados na ciência da computação. Desenvolvido por Tony Hoare em 1960, ele se baseia na estratégia de "dividir para conquistar", que envolve quebrar um problema grande em subproblemas menores, resolvê-los independentemente e, em seguida, combinar suas soluções para resolver o problema original. No contexto da ordenação, isso significa dividir um array em partes menores, ordenar essas partes e, finalmente, ter o array completo ordenado.
Princípio de Funcionamento
O Quicksort opera em três etapas principais:
- Escolha do Pivô: Um elemento do array é selecionado e designado como "pivô". A escolha do pivô é um aspecto crítico que afeta o desempenho do algoritmo.
- Particionamento: Os elementos restantes do array são rearranjados de forma que todos os elementos menores que o pivô fiquem à sua esquerda, e todos os elementos maiores que o pivô fiquem à sua direita. Após esta etapa, o pivô estará em sua posição final ordenada.
- Recursão: Os dois sub-arrays (elementos à esquerda do pivô e elementos à direita do pivô) são então ordenados recursivamente aplicando-se o Quicksort a cada um deles. O processo continua até que os sub-arrays tenham um ou nenhum elemento, momento em que são considerados ordenados.
Um pivô é um elemento escolhido de um array que é usado para dividir os outros elementos em dois subconjuntos: aqueles menores que o pivô e aqueles maiores que o pivô.
O Processo de Particionamento: Esquema de Lomuto
Existem várias estratégias para particionar um array, mas uma das mais comuns e fáceis de entender é o esquema de particionamento de Lomuto. Este esquema funciona da seguinte maneira:
- Seleção do Pivô: Geralmente, o último elemento do sub-array é escolhido como pivô. No entanto, outras escolhas são possíveis e serão discutidas mais adiante.
- Inicialização: Um índice $i$ é inicializado para apontar para a posição imediatamente anterior ao início do sub-array (ou seja, $i = \text{início} - 1$). Este $i$ rastreará o limite entre os elementos menores que o pivô e os elementos maiores ou iguais ao pivô.
- Iteração: Percorre-se o sub-array com um índice $j$ do início até o elemento anterior ao pivô. Se o elemento $\text{array}[j]$ for menor ou igual ao pivô, incrementa-se $i$ e troca-se $\text{array}[i]$ com $\text{array}[j]$. Isso garante que todos os elementos à esquerda de $i$ (inclusive) são menores ou iguais ao pivô.
- Posicionamento do Pivô: Após a iteração, todos os elementos menores ou iguais ao pivô estão à esquerda de $i$. O pivô (que estava na última posição) é então trocado com $\text{array}[i + 1]$. Assim, o pivô é colocado em sua posição final, com todos os elementos menores à sua esquerda e todos os maiores à sua direita. A função de particionamento retorna o índice final do pivô.
Exemplo Detalhado de Particionamento (Lomuto)
Vamos considerar o array $[7, 2, 1, 6, 8, 5, 3, 4]$ e particioná-lo usando o esquema de Lomuto, escolhendo o último elemento como pivô.
Array inicial: $[7, 2, 1, 6, 8, 5, 3, 4]$ Início $= 0$, Fim $= 7$. Pivô $= \text{array}[7] = 4$. $i = -1$ (inicialmente, para indicar que a seção de elementos menores está vazia)
- $j = 0$, $\text{array}[0] = 7$. $7 > 4$. Não faz nada. Array: $[7, 2, 1, 6, 8, 5, 3, 4]$
- $j = 1$, $\text{array}[1] = 2$. $2 \le 4$. Incrementa $i$ para $0$. Troca $\text{array}[0]$ (7) com $\text{array}[1]$ (2). Array: $[2, 7, 1, 6, 8, 5, 3, 4]$
- $j = 2$, $\text{array}[2] = 1$. $1 \le 4$. Incrementa $i$ para $1$. Troca $\text{array}[1]$ (7) com $\text{array}[2]$ (1). Array: $[2, 1, 7, 6, 8, 5, 3, 4]$
- $j = 3$, $\text{array}[3] = 6$. $6 > 4$. Não faz nada. Array: $[2, 1, 7, 6, 8, 5, 3, 4]$
- $j = 4$, $\text{array}[4] = 8$. $8 > 4$. Não faz nada. Array: $[2, 1, 7, 6, 8, 5, 3, 4]$
- $j = 5$, $\text{array}[5] = 5$. $5 > 4$. Não faz nada.
Regista-te para o resumo completoJá tem uma conta? Entrar
Algoritmo Quicksort
Klíčová slova: Algoritmo Quicksort
Klíčové pojmy: Quicksort é um algoritmo de ordenação "dividir para conquistar"., As três etapas principais são: escolha do pivô, particionamento e recursão., O particionamento rearranja elementos em menores e maiores que o pivô., O esquema de Lomuto é uma forma comum de particionamento, geralmente escolhendo o último elemento como pivô., A escolha do pivô afeta drasticamente o desempenho do Quicksort (aleatório ou mediana de três são melhores)., A complexidade de tempo média e de melhor caso é $O(n \log n)$., A complexidade de tempo de pior caso é $O(n^2)$, ocorrendo com pivôs desequilibrados., A complexidade de espaço é $O(\log n)$ no caso médio e $O(n)$ no pior caso (devido à recursão)., Quicksort é eficiente e "in-place", mas não é um algoritmo de ordenação estável., Erros comuns incluem má escolha do pivô e manipulação incorreta dos limites dos sub-arrays.