Analise de Algoritmos


Exemplo Divide and Conquer: Quicksort


Quicksort

Exercicio


Algoritmo Básico


Particionamento em Quicksort

  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


Visão da Recursividade do Quicksort como Árvore:


Método para o Particionamento


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


Exercício (entrega 10.10.1997)