Engenharia Informática e de Telecomunicações
Algoritmo e estrutura de dados
(3° ano)
Trabalho em grupo
Tema: Quick Sort
Nomes dos Discentes:
- Abel Xavier;
- Alberto Matola;
- Anibal Salvador;
- Melaine Tukhae;
Docente:
Eng. Tincogolo
Maputo, março de 2021
Indice
1. INTRODUÇÃO
2. DEFINIÇÃO
Quicksort é um dos métodos avançados para ordenação de dados.
Ordenação de dados é a organização de dados idênticos em grupos, para melhor consulta ou
pesquisa a posterior.
Esta estrutura de ordenação não necessita de espaço extra e é o mais rápido de todos
“organizadores-gerais”.
Este método ordena uma lista de elementos, inicialmente selecionando um destes elementos como
pivô. Depois a lista é organizada em duas partições, de modo que todos os elementos menores se
encontrem antes deste pivô e todos os maiores depois deste pivô. Então, o processo se repete para
estas partições, até que a ordenação esteja completa.
3. Particionamento
O particionamento é o mecanismo que sustenta o Quicksort. Além disso, o particionamento é
uma operação útil por si só.
3.1. O que é particionar dados?
Particionar é dividir estes dados em dois grupos, o que significa que todos dados com os valores-
chave maiores que uma amostra específica estão num grupo e os dados com os valores-chave
menores que essa amostra estão em outro grupo.
Um exemplo prático é quando a Secretária Académica quer dividir os estudantes com uma média
semestral maior que 15 e os estudantes com a média menor que 15.
Mas particionar não significa que se ordena os nossos dados. Por um lado, temos os dados
divididos em grupos abaixo e acima de um valor pivot, mas nesses subgrupos, os dados ainda se
encontram desorganizados.
Vale a pena esclarecer que o particionamento não divide os dados pela metade, isso depende do
valor pivot que for selecionado.
Quanto a eficiência, o particionamento é executado em tempo O(N).
4. Funcionamento
O algoritmo quicksort funciona da seguinte forma: o algoritmo particiona (como apresentado
anteriormente) o array em dois subarrays e recursivamente, ele ordena rapidamente (quick-
sorting) cada um dos subarrays.
Há versões mais sofisticadas do quicksort que recorrem a seleção do pivot e a ordenação de
pequenas partições. Mas iremos focar no algoritmo básico. A baixo será apresentado código
recursivo utilizado no quicksort.
public void recQuickSort(int left, int right){
if(right-left <= 0) // if size is 1,
return; // it’s already sorted
else{ // size is 2 or larger
// partition range
int partition = partitionIt(left, right);
recQuickSort(left, partition-1); // sort left side
recQuickSort(partition+1, right); // sort right side
}
}
Apresentado no código acima, há três passos básicos:
1. Particionar o array em grupos da esquerda (que contêm os valores menores) e da direita
(que contêm os valores maiores).
2. Chamamo-nos para ordenar o grupo da esquerda.
3. Chamamo-nos para ordenar o grupo da direita.
5. Vantagens e desvantagens
5.1. Vantagens
•É extremamente eficiente para ordenar arquivos de dados;
• Necessita de apenas uma pequena pilha como memória auxiliar;
• Requer O(n log n) comparações em média (caso médio) para ordenar n itens;
• Na maior parte das situações, ele é rápido, com complexidade O(N*logN).
5.2. Desvantagens
Tem um pior caso O(n2) comparações;
• Sua implementação é delicada e difícil;
•Um pequeno engano pode levar a efeitos inesperados para algumas entradas de dados;
• O método não é estável.
Quicksort
Como já foi apresentado o particionamento, que é parte do quicksort, pode-se debruçar sobre o
quicksort.
6. CONCLUSÃO
7. REFERÊNCIAS BIBLIOGRÁFICAS
[Link]
[Link]
%C3%A7%C3%A3o/[Link]