Atividades supervisionadas

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (338 palavras )
  • Download(s) : 0
  • Publicado : 5 de junho de 2012
Ler documento completo
Amostra do texto
Quick sort



O Quick Sort é um dos método mais rápidos de ordenação, apesar de às vezes partições desequilibradas poderem conduzir a uma ordenação lenta. Esse método de ordenação dividi oproblema inicial em dois subproblemas e resolve um problema menor utilizando a recursividade.

Este método baseia-se na divisão da tabela em duas sub-tabelas, dependendo de um elementochamado pivô, normalmente o 1º elemento da tabela. Uma das sub-tabelas contém os elementos menores que o pivô enquanto a outra contém os maiores. O pivô é colocado entre ambas, ficando na posiçãocorrecta. As duas sub-tabelas são ordenadas de forma idêntica, até que se chegue à tabela com um só elemento.

Esse método de ordenação divide-se em vários passos:
Escolher para pivô o primeiroelemento da tabela (p=x[1])
Se os elementos de x forem rearranjados de forma a que o pivô (p) sejam colocados na posição j e sejam respeitadas as seguintes condições:

1. todos oselementos entre as posições 1 e j-1 são menores ou iguais que o pivô (p)
2. todos os elementos entre as posições j+1 e n são maiores que o pivô (p)

Então p permanecerá na posiçãoj no final do ordenamento.
Se este processo for repetido para as sub-tabelas x[1] a x[j-1] e x[j+1] a x[n] e para todas as sub-tabelas criadas nas iterações seguintes obteremos no final umatabela ordenada.

Portanto a parte mais difícil deste método é o procedimento parte que divide a tabela em 2 sub-tabelas dependendo do pivô.


Algoritmo de Escolha de Pivô

Método Simples:Usar sempre o primeiro elemento da parte do array/vector que está sendo ordenado.
Método Melhor: Olhar para três elementos diferentes, e usar o elemento médio entre os três.


Algoritmo dePartição
O procedimento de partição deve reorganizar os elementos de forma a que:
1.Escolha do pivô: Considere p=a[lim_inferior] como o elemento pivô

· Usa-se o primeiro elemento para facilitar a...
tracking img