Scribd
Carregar
6 visualizações1 página

Algoritmo QuickSort: Funcionamento e Complexidade

O QuickSort é um algoritmo recursivo de ordenação que utiliza o método de particionamento, garantindo que um elemento-chave esteja em sua posição final, com todos os elementos à esquerda menores ou iguais e à direita maiores ou iguais. O algoritmo apresenta complexidade de pior caso O(N²) e melhor/médio caso O(N log N), sendo mais eficiente para vetores grandes e dependente de uma boa escolha do pivô. O documento também inclui referências sobre a implementação do QuickSort.

Enviado por

Breno klywer Olegario de Moura
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd
6 visualizações1 página

Algoritmo QuickSort: Funcionamento e Complexidade

O QuickSort é um algoritmo recursivo de ordenação que utiliza o método de particionamento, garantindo que um elemento-chave esteja em sua posição final, com todos os elementos à esquerda menores ou iguais e à direita maiores ou iguais. O algoritmo apresenta complexidade de pior caso O(N²) e melhor/médio caso O(N log N), sendo mais eficiente para vetores grandes e dependente de uma boa escolha do pivô. O documento também inclui referências sobre a implementação do QuickSort.

Enviado por

Breno klywer Olegario de Moura
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd

Algoritmo QuickSort

Universidade Federal Rural do Semi-Árido


Breno Klywer Olegário de Moura

December 11, 2024

1. The Algorithm
O QuickSort é um método recursivo para ordenar um vetor. Ele utiliza o método de
“particionamento” ou “dividir para conquistar”, garantindo que as seguintes condições
sejam atendidas:

a. Um elemento-chave V está em sua posição final no vetor. (Se for o j-ésimo


menor, está na posição A[j].)
b. Todos os elementos à esquerda de A[j] são menores ou iguais a V. (Esses
elementos são chamados de “subvetor à esquerda”).
c. Todos os elementos à direita de são maiores ou iguais a V. (Esses elementos
são chamados de “subvetor à direita”).

Após o particionamento, o problema original de ordenar todo o vetor se reduz ao


problema de ordenar independentemente os subvetores esquerdos e direito. Até agora
foi definido apenas a lógica de particionamento do problema em problemas menores,
agora vem a parte que ordena essas partições. O processo de particionamento e
ordenação pode ser mais facilmente entendido assumindo-se incialmente, que os
elementos A[1],..,A[N] são distintos.

O algoritmo começa tomando o elemento mais à esquerda como elemento de


particionamento. Em seguida o restante do vetor é dividido, escaneando-se da esquerda
para encontrar um elemento >V (maior que V), da direita para encontrar um elemento
<V (menor que V), trocando-os e continua o processo até que os ponteiros se cruzem. O
loop termina com J+1 = I, momento em que é garantido que A[l+1],...,A[J] são menores
que V e A[j+1],...,A[r] são maiores que v. A troca A[l] <-> A[j] completa o particionamento.
Igual a todas a chaves A[all],...,A[r] é incluído para parar o ponteiro i no caso de v ser a
maior das chaves. O procedimento de chamada QuickSort(1,N) classificará, portanto,
A[i],...,A[N], “if A[N+1]” é inicializado para algum alor pelo menos tão grande quanto as
outras chaves. Se chaves iguais estiverem presentes entre A[1],...,A[N], então o algoritmo
opera de maneira adequada e eficiente, mas não exatamente como descrito acima.

- Características do QuickSort

1. Complexidade: Pior caso (N²) e Melhor e Médio caso (N log N)


2. Recursivo: Quick É implementado de forma recursiva.
3. Dependência do Pivô: Quick depende de uma boa escolha do pivô.
4. Adequação: Quick é eficiente para vetores grandes.

2. Referências

SEDGEWICK, R. Implementing Quicksort Programs. Communications of the ACM, v. 21, n. 10,


p. 847-857, 1978. Disponível em: [Link] Acesso
em: 11 dez. 2024.

Você também pode gostar