Analise de Algoritmos


Exemplo Divide and Conquer: Quicksort

Quicksort

• Algoritmo Básico
• Particionamento em Quicksort
• Exemplo
• Visão da Recursividade do Quicksort como Árvore:
• Método para o Particionamento
• Algoritmo de Particionamento
• Comentários sobre o Quicksort

Exercicio

Algoritmo Básico

• Quicksort trabalha particionando um arquivo em duas partes e então as ordenando separadamente.
• Pode ser definido recursivamente:

quicksort (tipoInfo : a[], inteiro : esq, dir)
        inteiro i;
        início
                se dir > esq então
                        i <- particione(a, esq, dir);
                        quicksort(a, esq, i-1);
                        quicksort(a, i+1, dir);
                fim se
        fim

• Os parâmetros dir e esq delimitam os subarquivos dentro do arquivo original, dentro dos quais a ordenação ocorre.
• A chamada inicial pode ser feita com quicksort(a, 1, N);
• O ponto crucial é o algoritmo de partição.

---

Particionamento em Quicksort

• O procedimento de particionamento deve rearranjar o arquivo de maneira que as seguintes condições valham:

1. o elemento a[i] está em seu lugar final no arquivo para um i dado,
2. nenhum dos elementos em a[esq],...,a[i-1] são maiores do que a[i],
3. nenhum dos elementos em a[i+1],...,a[dir] são menores do que a[i].

---

Exemplo

• Ordenação do vetor inicial 25 57 48 37 12 92 86 33.
• Se o primeiro elemento (25) for colocado na sua posição correta, teremos: 12 25 57 48 37 92 86 33.
  Neste ponto:
• todos os elementos abaixo de 25 serão menores e
• todos os elementos acima de 25 serão maiores que 25.
• Como 25 está na sua posição final, o problema foi decomposto na ordenação dos subvetores: (12) e (57 48 37 92 86 33).
• O subvetor (12) já está classificado.
• Agora o vetor pode ser visualizado: 12 25 (57 48 37 92 86 33).
• Repetir o processo para a[2]...a[7] resulta em:
  12 25 (48 37 33) 57 (92 86)
• Se continuarmos particionando 12 25 (48 37 33) 57 (92 86), teremos:
• 12 25 (37 33) 48 57 (92 86)
• 12 25 (33) 37 48 57 (92 86)
• 12 25 33 37 48 57 (92 86)
• 12 25 33 37 48 57 (86) 92
• 12 25 33 37 48 57 86 92

---

Visão da Recursividade do Quicksort como Árvore:

---

Método para o Particionamento

• Considere x=a[limInf] como o elemento cuja posição final é a procurada.
• Usar sempre o primeiro é só um artifício p/facilitar a implementação.
• Dois ponteiros alto e baixo são incializados como os limites máximo e mínimo do subvetor que vamos analisar.
• Em qualquer ponto da execução, todo elemento acima de alto é maior do que x e todo elemento abaixo de baixo é menor do que x.
• Os dois ponteiros alto e baixo são movidos um em direção ao outro da seguinte forma:
• 1. Incremente baixo em uma posição até que a[baixo] > x.
• 2. Decremente alto em uma posição até que a[alto] <= x.
• 3. Se a alto > baixo , troque a[baixo] por a[alto].
• O processo é repetido até que a condição descrita em 3. falhe (quando
  alto <= baixo ). Neste ponto a[alto]será trocado por a[limInf],cuja posição final era procurada, e alto é retornado em i.

---

Algoritmo de Particionamento

inteiro partição(tipoInfo : a[], inteiro : limInf, limSup)
        variáveis
                tipoInfo : x, temp; inteiro : baixo, alto;
        início
                x <- a[limInf]; alto <- limSup; baixo <- limInf;
                enquanto (baixo < alto) faça
                        enquanto (a[baixo] <= x E baixo < limSup) faça
                                incremente baixo;               /* Sobe no arquivo */
                        enquanto (a[alto] > x) faça
                                decremente alto;                /* Desce no arquivo */ 
                        se (baixo < alto) então /* Troca */
                                temp <- a[baixo];
                                a[baixo] <- a[alto];
                                a[alto] <- temp;
                        fim se
                fim enquanto
                a[limInf] <- a[alto];
                a[alto] <- x;
                retorne alto;
        fim

Comentários sobre o Quicksort

• Para evitar o pior caso e casos ruins onde elementos estão em grupos ordenados pode-se utilizar uma estratégia probabilística:
• Selecione, ao invés do primeiro elemento para ser a, um elemento aleatório. Critérios:
• Seleção totalmente randômica: selecione qualquer elemento do subvetor usando um gerador de números aleatórios.
• Desvantagem: tempo de processamento extra para o gerador.
• Seleção pseudorandômica: selecione um elemento do subvetor com base em um cálculo qualquer baseado em valores que você tem à mão (alto, baixo, chave do primeiro)
• Seleção média: pegue ao invés do elemento inicial, sempre o do meio.
• Todos estes métodos melhoram a performance média.

Exercício (entrega 10.10.1997)

• Execute o algoritmo de particionamento no papel para o exemplo de arquivo dado no exemplo de QuickSort.
• Implemente o QuickSort:
• A implementação deve ser capaz de ler um arquivo contendo uma série de números reais, um por linha.
• A implementação deverá ser capaz de escrever em um arquivo o tempo necessário para ordenar os dados.
• Serão fornecidos diversos arquivos. O tempo deverá ser escrito sempre no fim de um arquivo só.