Atps

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 utiliza a técnica divide and conquer (dividir o problema inicial em dois subproblemas e resolver 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.

Complexidade: caso médio O(N * log N)

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. 1. todos os elementos entre as posições 1 e j-1 são menores ou iguais que o pivô (p)
2. 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