Atividades supervisionadas

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 o problema 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 elemento chamado 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ção correcta. 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 primeiro elemento 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 os elementos 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ção j 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 uma tabela 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 de Partiçã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