ordenacao.tex

\chapter{Algoritmos de Ordenação}

O problema da ordenação é central na análise de algoritmos por dois motivos.
Em primeiro lugar, ele é um problema com muitas aplicações em diversas áreas da computação.
Em segundo lugar, são conhecidas diversas soluções bem diferentes para esse problema, o que o torna um excelente exemplo para a teoria que estamos apresentando.

Vamos relembrar o problema:
\vspace{1em}

  {\bf Problema da ordenação}\\

  {\bf Entrada:} Uma sequência de $n$ valores $a_1, \dots, a_n$ em que $a_i \in \mathbb{Z}$ para $1 \leq i \leq n$.\\

  {\bf Saída:} Uma permutação da sequência de entrada $a'_1, \dots, a'_n$ tal que $a_i \leq a_j$ para todo $i < j$.

  \section{Selection Sort}

  Comecemos com uma solução bem simples para o problema, um algoritmo chamado Selection Sort.
  Esse algortimo consiste em identificar o maior elemento da sequência e trocá-lo com o último e repetir o processo até que todos estejam em ordem.

  Assim, podemos começar com a seguinte sub-rotina:

  \begin{codebox}
    \Procname{$\proc{Maximo}(A)$}
    \li \Comment Recebe uma sequência $a_1, \dots, a_n$
    \li \Comment Devolve $i$ tal que $a_i$ é o maior elemento da sequência
    \li $imax \gets 0$
    \li \For $i \gets 2$ até $n$
    \li \Do \If $a_i > a_{imax}$
    \li     \Then $imax \gets i$
        \End
    \End
    \li \Return $imax$
  \end{codebox}

  Para provar que este algoritmo é correto, note que a seguinte propriedade é invariante na linha 2:

  \begin{center}
    $a_{imax}$ é o maior elemento em $a_i, \dots, a_{i-1}$ 
  \end{center}

  {\em Inicialização:} na primeira vez que passamos pela linha 2 temos que $i = 2$.
  Portanto, a sequência $a_1, \dots, a_{i-1}$ tem apenas um elemento ($a_1$) que só pode ser o maior.

  {\em Manutenção:} se na iteração anterior $a_{imax}$ era o maior elemento em $a_1, \dots, a_{i-1}$ temos duas possibilidades: se $a_i$ fosse maior que $a_{imax}$ então teríamos atualizado $imax$ e ele continuaria sendo o maior da sequência, caso contrário $imax$ não teria sido atualizado, mas $a_{imax}$ continuaria sendo o maior elemento.

  {\em Término:} quando chegamos na linha 5 temos que $a_{imax}$ é o maior elemento de $a_1, \dots, a_n$.

  \vspace{1em}

  Analisar o tempo de processamento deste algoritmo também é simples.
  Para facilitar as contas, faremos mais uma simplificação.
  Ao invés de somar o tempo de processamento de cada linha, calcularemos o tempo apenas de uma das linhas que mais se repete, neste caso escolhemos a 3.
  Essa linha é processada $n$ vezes e, portanto, o algortimo é $\Theta(n)$.

  Apresentemos agora o algoritmo Selection Sort.

  
  \begin{codebox}
    \Procname{$\proc{SelectionSort}(A)$}
    \li \For $j \gets n$ até $2$
    \li \Do $imax \gets Maximo(a[1:j])$
    \li     \Then $a_{imax} \leftrightarrow a_j$
        \End
  \end{codebox}

  A propriedade invariante depois da linha 3, neste caso, é:
  \begin{center}
    $a_j, \dots, a_n$ está em ordenada e $a_j$ é o maior elemento de $a_1, \dots, a_j$
  \end{center}

  {\em Inicialização:} Na primeira passagem temos que $j=n$ e, portanto a squência $a_j, \dots, a_n$ tem um único elemento $a_n$, além disso, pela correção do algoritmo $Maximo$, $a_n$ é o maior elemento da sequência $a_1, \dots, a_n$.

  {\em Manutenção:} Pela hipótese de indução $a_j, \dots, a_n$ estava ordenada na iteração anterior e $a_j$ é o maior elemento de $a_1, \dots, a_j$, assim $a_{j-1} \leq a_j$ e temos que $a_{j-1}, \dots, a_n$ está em ordem crescente.
  Além disso, pela correção do algortimo $Maximo$ temos que $a_{j-1}$ é o maior elemento em $a_1, \dots, a_{j-1}$.

  {\em Término:} Quando saimos do laço, $j=2$ e o invariante garante, portanto, que $a_2, \dots, a_n$ está ordenado.
  Além disso, ele garante que $a_2$ é o maior elemento da sequência $a_1, a_2$.
  Concluímos que ao término $a_1, \dots, a_n$ está ordenado.

  \vspace{1em}
  

  Para analisar o tempo de processamento deste algoritmo, consideraremos a linha 2 que se repete $n$ vezes.
  A operação executada nessa linha, porém, não é atômica.
  Como vimos, ela toma tempo proporcional ao tamanho da entrada que varia em cada iteração.
  Na primeira iteração toma tempo proporcional a $n$, na segunda $n-1$, então $n-2$ e assim por diante.

  O tempo de processamento em função do tamanho $n$ da entrada, então, é:

  \begin{displaymath}
    T(n) = n + (n-1) + (n-2) + \dots + 1 = \sum_{i=1}^{n}i = \frac{n(n+1)}{2} \in \Theta(n^2)
  \end{displaymath}

  Assim se calcularmos o tempo de processamento de uma implementação desse algoritmo para entradas de diferentes tamanhos, devemos observar uma parábola (Figura \ref{}):

  \begin{figure}
    \includegraphics[width=\textwidth]{imagens/SelectionSort1.png}
  \end{figure}

  Podemos testar que se trata de fato de uma parábola poltando os mesmo valores em um gráfico em que ambos os eixos estão em escala logarítmica.
  Se a função tiver o formato $T(n) = an^2$, como nossa análise sugere, ao aplicar o $log$ nos dois lados, temos que:
  \begin{displaymath}
  log(T(n)) = log(an^2) = 2(log(n) + log(a)) = 2log(n) + 2log(a)
  \end{displaymath}
  
  Assim, o que obtemos é a equação de uma reta com inclinação $2$.
  Na Figura \ref{} observamos que de fato em uma gráfico log-log o que obtemos é uma reta com inclinação $1,94$, valor bem próximo do esperado.

  \begin{figure}
    \includegraphics[width=\textwidth]{imagens/SelectionSort2.png}
  \end{figure}

  
  \section{Insertion Sort}

  Nosso segundo algoritmo segue uma ideia também simples.
  Ele ordena uma sequência de maneira análoga a forma como muitas pessoas ordenam cartas de baralhos nas mãos.

  A princípio as cartas estão todas viradas para baixo.
  Elas são inseridas uma por uma na mão do jogador cada qual em sua posição relativa correta.

   \begin{codebox}
     \Procname{$\proc{InsertionSort}(A)$}
     \li \For $j \gets 2$ até $n$
     \li \Do $chave \gets a_j$
     \li    \For $i \gets j-1$ até $1$
     \li    \Do $a_{i+1} \gets a_i$
     \li       \If $a_i > chave$
     \li       \Then sai do laço
               \End
            \End
     \li    $a_{i+1} \gets chave$
     \End
   \end{codebox}

   Para provar a correção deste algoritmo, note que a seguinte propriedade é invariante na linha 2:

   \begin{center}
     a sequência $a_1, \dots, a_{j-1}$ está em ordem crescente
   \end{center}

   A análise do consumo de tempo é similar à do SelectionSort.
   Uma diferença está no fato de que independente da entrada, o SelectionSort sempre processa todos elementos já o InsertionSort pode sair do laço interno precocemente.
   Note então que, quando o pior caso ocorre quando os elementos originalmente estão em ordem descrescente.
   Neste caso, a análise do consumo de tempo é idêntica à do SelectionSort:

   \begin{displaymath}
     T(n) = n + (n-1) + (n-2) + \dots + 2 = \sum_{i=2}^n = \frac{n(n+1)}{2} - 1 \in \Theta(n^2)
   \end{displaymath}

   Assim, no pior caso os algoritmos são identícos.
   Veremos como analisar o caso médio na seção sobre o QuickSort, por ora basta dizer que ela também é $\Theta(n^2)$ neste caso, porém a constante multiplicadora é menor.
   Isso fica evidente quando verificamos o modelo.
   Plotando o tempo e processamento dos dois algoritmos que vimos até aqui em um mesmo gráfico com escala log nos dois eixos, vemos que ambos apresentamos uma reta praticamente com a mesma inclinação -- o primeiro tinha inclinação 1,94 e este 1,88.
   A diferença é no fato de deslocamento vertical que indica uma diferença no fator multiplicador do termo dominante.
   Essa diferença é significativa porque testamos o algoritmo com uma entrada aleatória e, nesse caso, o InsertionSort é um pouco mais eficiente:

   
  \begin{figure}
    \includegraphics[width=\textwidth]{imagens/SelectionInsertion.png}
  \end{figure}   
  
\section{Merge Sort}

Antes de apresentar o próximo algoritmo, estudaremos um paradigma de projeto de algoritmos chamado {\em divisão-e-conquista} que consiste nos seguintes passos:

\begin{itemize}
  \item {\em Divisão:} a instância original do problema é dividida em um número de instâncias menores.
  \item {\em Conquista:} instâncias suficientemente pequenas são resolvidas diretamente.
    \item {\em Combinação:} se necessário, as soluções das instâncias menores são combinadas em para resolver a instância original.
\end{itemize}

Para exemplificar o paradigma, revisitaremos o algoritmo da busca binária em uma versão recursiva.

\begin{codebox}
  \li \Comment recebe uma sequência ordenada $a_1, \dots, a_n$ e um valor $b$
  \li \Comment devolve V se $b$ está na sequência e F c.c.
  \Procname{$\proc{BuscaBinaria}(A, b)$}
  \li \If $n = 1$
  \li \Then \If $a_1 = b$
  \li \Then \Return V
  \End
  \li \Else
  \li \Return F
  \End 
  \li $m \gets \left \lfloor{\frac{n}{2}}\right\rfloor$
  \li \If $b \leq a_m$
  \li     \Then \Return $BuscaBinaria(A[1:m])$
  \End
  \li \Else \Return $BuscaBinaria(A[m+1:n])$
  \End
\end{codebox}

As linhas 1 a 5 resolvem o caso base ({\em conquista}) enquanto as linhas 6 a 10 dividem o problema em instâncias menores.
Neste caso, não há necessidade de combinar as soluções pois a cada passo, metade da instância original pode ser ignorada.

Para analisar o tempo de processamento deste algoritmo primeiro estabelecemos que as linhas 1 a 5 tomas tempo constante ($c_2$), assim comas as linhas 6, 7 e 9 ($c_1$).
Jás as linhas 8 e 10 são chamadas recursivas.
Assim, o tempo de processamento do pior caso em função do tamanho da entrada $n$ é descrito pela seguinte recorrência:

\begin{eqnarray*}
  T(n) & = & c_1 + T(\left \lceil{\frac{n}{2}}\right \rceil) \\
  T(1) & = & c_2
\end{eqnarray*}

Resolveremos essa recorrência utilizando o método da árvore de recorrência:

% Árvore de recorrência
\begin{center}
\begin{tikzpicture}
\node {$T(n)$}[sibling distance = 6cm]
child {node {$T(\frac{n}{2}) + c_1$}[sibling distance = 3cm] 
  child {node {$T(\frac{n}{4}) + c_1$}
    child {node {$T(\frac{n}{2^i}) + c_1$} edge from parent [dashed]
      child {node {$T(\frac{n}{n}) + c_1$} 
        child {node {$c_2$} edge from parent [solid]}}}}};
\end{tikzpicture}
\end{center}

A árvore chega no caso base $T(1)$ quando $2^i = n$, ou seja, quando $i = lg(n)$.
Portanto, a altura da árvore é $lg(n)$.
Em cada passo, é somado $c_1$ e no último é somado $c_2$.
Concluímos que:

\begin{displaymath}
  T(n) = c_1.lg(n) + c_2
\end{displaymath}


Talvez um exemplo melhor do paradigma da divisão-e-conquista seja um versão do algoritmo de busca para sequências arbitrárias.
Dividiremos a sequência ao meio, mas neste caso, é preciso buscar nas duas metades dela.
Por fim, precisamos combinar os resultados.
O elemento $b$ está na sequência se ele está na metade direita ou na metade esquerda.

\begin{codebox}
  \li \Comment recebe uma sequência $a_1, \dots, a_n$ e um valor $b$
  \li \Comment devolve V se $b$ está na sequência e F c.c.
  \Procname{$\proc{BuscaRecursiva}(A, b)$}
  \li \If $n = 1$
  \li \Then \If $a_1 = b$
  \li \Then \Return V
  \End
  \li \Else
  \li \Return F
  \End 
  \li $m \gets \left \lfloor{\frac{n}{2}}\right\rfloor$
  \li \Return $BuscaRecursiva(A[1:m])$ ou $BuscaRecursiva(A[m+1:n])$
  \End
\end{codebox}

Como no exemplo anterior, o caso base (linhas 3 a 7) toma tempo constante $c_2$ e as operações de divisão, atribuição e o ou lógico (linhas 8 e 9) também tomam tempo constante $c_2$.
Desta vez, porém, a recursão é aplicada nas duas metades da sequência.
Assim, a recorrência que devemos resolver é:

\begin{eqnarray*}
  T(n) & = & c_1 + T(\left \lceil{\frac{n}{2}}\right \rceil) + T(\left \lfloor{\frac{n}{2}}\right \rfloor)\\
  T(1) & = & c_2
\end{eqnarray*}

Para calcular o resultado dessa recorrência, vamos novamente analisar sua árvore:

% Árvore de recorrência
\begin{center}
\begin{tikzpicture}
\node {$T(n)$}[sibling distance = 6cm]
child {node {$T(\frac{n}{2}) + c_1$}[sibling distance = 3cm]
  child {node {$T(\frac{n}{4}) + c_1$}
    child {node {$T(\frac{n}{2^i}) + c_1$} edge from parent [dashed]
      child {node {$T(\frac{n}{n}) + c_1$} 
        child {node {$c_2$} edge from parent [solid]}}}}
  child {node {$T(\frac{n}{4}) + c_1$}
    child {node {$T(\frac{n}{2^i}) + c_1$} edge from parent [dashed]
      child {node {$T(\frac{n}{n}) + c_1$} 
        child {node {$c_2$} edge from parent [solid]}}}}}
child {node {$T(\frac{n}{2}) + c_1$}[sibling distance = 3cm] 
  child {node {$T(\frac{n}{4}) + c_1$}
    child {node {$T(\frac{n}{2^i}) + c_1$} edge from parent [dashed]
      child {node {$T(\frac{n}{n}) + c_1$} 
        child {node {$c_2$} edge from parent [solid]}}}}
  child {node {$T(\frac{n}{4}) + c_1$}
    child {node {$T(\frac{n}{2^i}) + c_1$} edge from parent [dashed]
      child {node {$T(\frac{n}{n}) + c_1$} 
        child {node {$c_2$} edge from parent [solid]}}}}};
\end{tikzpicture}
\end{center}

Como no caso anterior, essa árvore chega às folhas quando $2^i = n$, ou seja, quando $i = lg(n)$.
Portanto, a altura dela é $lg(n)$.
Em cada nível dessa árvore dobramos a quantidade de $c_1$ somadas.
Assim, no i-ésimo nível são somados $2^i$ constantes e no último são somados $2^{lg(n)} = n$ constantes.
Portanto, o resultado de nossa recorrência é:

\begin{eqnarray*}
  T(n) & = & c_1.\sum_{i=1}^{lg(n)}2^i + c_2.n\\
  & = & c_1.\frac{1 - 2^{lg(n)}}{1-2} + c_2.n \\
  & = & c_1.(n-1) + c_2.n \\
  & = & (c_1 + c_2).n - c_1 \\
  & \in & \Theta(n)
\end{eqnarray*}

O merge sort, ou algoritmo de ordenação por intercalação, também segue o paradigma da divisão-e-conquista.
A ideia é quebrar a instância original ao meio até que ela tenha apenas um elemento.
Neste caso, o caso base, não é preciso fazer nada pois qualquer sequência com um único elemento está trivialmente ordenada.
O segredo está na combinação das instâncias menores para resolver a instância original.
Para este passo, usaremos um algoritmo de intercalação.

Podemos enunciar o problema da intercalação da seguinte forma:
\vspace{1em}

{\bf Problema da intercalação}\\

{\bf Entrada:} Duas sequências $a_1, \dots, a_n$ e $b_1, \dots, b_m$ ambas em ordem crescente.

{\bf Saída:} Uma sequência $c_1, \dots, c_{m+n}$ em ordem crescente cujos elementos são os mesmos das sequências da entrada.

Para resolver esse problema utilizamos o seguinte algoritmo:

\begin{codebox}
  \Procname{$\proc{Merge}(A, B)$}
  \li $i \gets 1$
  \li $j \gets 1$
  \li \For $k \gets 1$ até $n+m$
  \li \Do \If ($a_i \leq b_j$ e $i \leq n$) ou $j > m$
  \li \Then $c_k \gets a_i$
  \li $i \gets i + 1$
  \li \Else
  \li $c_k \gets b_j$
  \li $j \gets j + 1$
  \End
  \End
  \li \Return $C$
\end{codebox}

Com isso, podemos escrever o algoritmo de ordenação da seguinte forma:

\begin{codebox}
  \Procname{$\proc{MergeSort}(A)$}
  \li \If $n > 1$
  \li \Then  $m \gets \left \lfloor{\frac{n}{2}}\right\rfloor$
  \li $MergeSort(A[1:m])$
  \li $MergeSort(A[m+1:n])$
  \li $A \gets Merge(A[1:m], A[m+1:n])$
\end{codebox}

O caso base do algoritmo ocorre quando $n = 1$.
Neste caso, nada precisa ser feito e o tempo tomado é constante $c$.
Já a linha 4 toma tempo linear no tamanho da entrada $n$.
Com isso, temos que o tempo de execução do algoritmo em função de $n$ é:

\begin{eqnarray*}
  T(n) & = & c_1.n + T(\left \lfloor{\frac{n}{2}}\right\rfloor) + T(\left \lceil{\frac{n}{2}}\right\rceil)\\
  T(1) & = & c_2
\end{eqnarray*}

Analisaremos, então a seguinte árvore de recorrência:

% Árvore de recorrência
\begin{center}
\begin{tikzpicture}
\node {$T(n)$}[sibling distance = 6cm]
child {node {$T(\frac{n}{2}) + c_1.n$}[sibling distance = 3cm]
  child {node {$T(\frac{n}{4}) + c_1.\frac{n}{2}$}
    child {node {$T(\frac{n}{2^i}) + c_1.\frac{n}{2^{i-1}}$} edge from parent [dashed]
      child {node {$T(\frac{n}{n}) + c_1.2$} 
        child {node {$c_2$} edge from parent [solid]}}}}
  child {node {$T(\frac{n}{4}) + c_1.\frac{n}{2}$}
    child {node {$T(\frac{n}{2^i}) + c_1.\frac{n}{2^{i-1}}$} edge from parent [dashed]
      child {node {$T(\frac{n}{n}) + c_1.2$} 
        child {node {$c_2$} edge from parent [solid]}}}}}
child {node {$T(\frac{n}{2}) + c_1.n$}[sibling distance = 3cm] 
  child {node {$T(\frac{n}{4}) + c_1.\frac{n}{2}$}
    child {node {$T(\frac{n}{2^i}) + c_1.\frac{n}{2^{i-1}}$} edge from parent [dashed]
      child {node {$T(\frac{n}{n}) + c_1.2$} 
        child {node {$c_2$} edge from parent [solid]}}}}
  child {node {$T(\frac{n}{4}) + c_1.\frac{n}{2}$}
    child {node {$T(\frac{n}{2^i}) + c_1.\frac{n}{2^{i-1}}$} edge from parent [dashed]
      child {node {$T(\frac{n}{n}) + c_1.2$} 
        child {node {$c_2$} edge from parent [solid]}}}}};
\end{tikzpicture}
\end{center}

Em cada nível da árvore, é somado $2.c_1.n$.
Como a altura dessa árvore também é $lg(n)$ temos que:
\begin{displaymath}
  T(n) = 2.c_1.n.lg(n) + 2.n.c_2 \in \Theta(n.lg(n))
\end{displaymath}

Ambos os algoritmos de ordenação que vimos nas seções anteriores, selection sort e insertion sort, tomam tempo $\Theta(n^2)$ no pior caso.
Comparado a esses, o merge sort é muito mais eficiente.
Isso porque a função $lg(n)$ cresce muito mais devagar do que a função $n$.
Na Figura \ref{fig:comp1} plotamos em um grafíco log-log o resultado de um experimento em que foi computado o tempo de processamento de sequências aleatórias para cada um três algoritmos.
Para sequências de 100 mil elementos, o tempo de processamento dos algoritmos básicos tomou tempo próximo a 10 segundo e esse tempo aumentou para cerca de 100 segundos quando aumentamos o número de elementos para 300 mil.
Já o tempo de processamento do merge sort variou próximo de 0,1 segundos.
Além disso, note que as inclinações das retas nos dois primeiros casos é próxima de $2$.
Como discutido anteriormente esse era o resultado esperado visto que os algoritmos tomam tempo $\Theta(n^2)$.
A inclinação da reta que corresponde ao tempo de processamente do merge sort é menor, mais próxima de $1$ do que de $2$.

\begin{figure}
  \label{fig:comp1}
  \includegraphics[width=\textwidth]{imagens/comparacao1.png}
  \caption{Resultado de experimento para calcular o processamento dos algoritmos de ordenação vistos até agora em um gráfico log-log.}
\end{figure}


Agora que vimos como resolver três recorrências diferentes usando o método da árvore de recorrência, apresentaremos um resultado geral para resolver recorrências:

\begin{theorem}[Mestre]
  Sejam $a \geq 1$, $b > 1$ e $T(n) = aT(\frac{n}{b}) + f(n)$, então:
  \begin{enumerate}
  \item se $f(n) \in O(n^{log_b(a - \epsilon)})$ para algum $\epsilon > 0$ então $T(n) \in \Theta(n^{log_ba})$
  \item se $f(n) \in \Theta(n^{log_ba})$ então $T(n) \in \Theta(n^{log_ba}lg(n))$
  \item se $f(n) \in \Omega(n^{log_b(a + \epsilon)})$ para algum $\epsilon > 0$ e se $af(\frac{n}{b}) \leq cf(n)$ para algum $c < 1$ e todo $n$ suficientemente grande então $T(n) \in \Theta(f(n))$
  \end{enumerate}
\end{theorem}

\begin{example}
  Comecemos pela recorrência que acabamos de analisar
  \begin{displaymath}
    T(n) = 2T\left(\frac{n}{2}\right) + cn
  \end{displaymath}

  O primeiro passo é avaliar $n^{log_ba}$ que neste caso é $n^{log_22} = n$.
  Então temos que verificar se $f(n) = cn \in \Theta(n)$.
  Neste caso, isso vale.
  Portante se aplica o caso 2 do teorema e temos que:

  \begin{displaymath}
    T(n) \in \Theta(n^{log_22}.lg(n)) = \Theta(n.lg(n))
  \end{displaymath}
\end{example}

\begin{example}
  Considere a recorrência que obtivemos ao analisar a busca binária:
  \begin{displaymath}
    T(n) = T\left(\frac{n}{2}\right) + c
  \end{displaymath}

  O primeiro passo é avaliar $n^{log_ba}$ que neste caso é $n^{log_21} = n^0 = 1$.
  Então temos que verificar se $f(n) = c \in \Theta(1)$.
  Neste caso, isso vale.
  Portante se aplica o caso 2 do teorema e temos que:

  \begin{displaymath}
    T(n) \in \Theta(n^{log_21}.lg(n)) = \Theta(1.lg(n)) = \Theta(lg(n))
  \end{displaymath}
\end{example}


\begin{example}
  Considere agora a recorrência que obtivemos ao analisar a busca recursiva:
  \begin{displaymath}
    T(n) = 2T\left(\frac{n}{2}\right) + c
  \end{displaymath}

  Primeiro avaliamos $n^{log_22} = n$.
  Então temos que verificar se $f(n) = c \in \Theta(n)$.
  Neste caso, isso não é verdade $c$ cresce mais lentamente do que $n$.
  
  Se  $\epsilon = 1$ temos que $n^{log_2(2-1)} = n^0 = 1$ e $c \in O(1)$.
  Portanto podemos aplicar o caso 1 do teorema e temos que:

  \begin{displaymath}
    T(n) \in \Theta(n^{log_22} = \Theta(n^1) = \Theta(n)
  \end{displaymath}
\end{example}

\begin{example}
  Para terminar, considera a seguinte recorrência:
  \begin{displaymath}
    T(n) = 2T\left(\frac{n}{2}\right) + n^2
  \end{displaymath}

  Primeiro avaliamos $n^{log_22} = n$.
  Então temos que verificar se $f(n) = n^2 \in \Theta(n)$.
  Neste caso, isso não é verdade $n²$ cresce mais rapidamente do que $n$.
  
  Se $\epsilon = 2$ temos que $n^{log_2(2+2)} = n^2$ e $n^2 \in \Omega(n^2)$ e $2(\frac{n}{2})^2 = \frac{n^2}{2} \leq \frac{1}{2}.n^2$ para todo $n > 0$.  
  Portanto podemos aplicar o caso 3 do teorema e temos que:

  \begin{displaymath}
    T(n) \in \Theta(f(n)) = \Theta(n^2)
  \end{displaymath}
\end{example}


\section{Quick Sort}

O quick-sort é um algortimo eficiente e de simples implementação características que o tornou o mais popular dos algoritmos de ordenação presente nas bibliotecas padrão da grande maioria das linguagens de programação.

Como o merge-sort, ele segue o paradigma divisão-e-conquista.
Enquando o ``segredo'' do mege-sort está na fase de combinação com o algortimo de intercalação, o segredo do quick-sort está na fase de divisão.

Ao invés de dividir a instância sempre ao meio, o quick-sort rearranja os elementos de forma a particioná-lo em dois pedaços.
Na primeira partição todos elementos são menores do que um certo elemento chamado {\em pivo} e na segunda partição todos elementos são maiores do que ele.
A divisão então, é feita na posição do pivô.

\vspace{1em}
{\bf Problema da partição}\\

{\bf Entrada:} Uma sequência $a_1, \dots, a_n$.

{\bf Saída:} Um índice $q$ e uma permutação $a_1', \dots, a_q, \dots, a_n'$ da sequência e forma que $a_i' \leq a_q'$ se $i < q$ e $a_q' \leq a_j'$ se $q < j$.

O seguinte algoritmo resolve esse problema:

\begin{codebox}
  \Procname{$\proc{Particao}(A)$}
  \li $pivo \gets a_n$
  \li $i \gets -1$
  \li \For $j \gets 1$ até $n$
  \li \Do \If $a_j \leq pivo$ 
  \li \Then $i \gets i+1$
  \li $a_i \leftrightarrow a_j$
  \End
  \End
  \li $a_{i+1} \gets a_j$
  \li \Return $i+1$
\end{codebox}

Para a prova da correção note que na linha 4 a seguinte propriedade é invariante:

\begin{center}
  $a_k \leq pivo$ para todo $k$ tal que $k \leq i$ e \\
  $a_k > pivo$ para todo $k$ tal que $i < k \leq j$. 
\end{center}

O tempo de processamento desse algoritmo é $\Theta(n)$ tanto no melhor quando no pior caso.

Como antecipado, o quick-sort é um algoritmo de ordenação baseado em divisão-e-conquista que utiliza do algoritmo da partição para estabelece o ponto em que a instância será dividida.

\begin{codebox}
  \Procname{$\proc{QuickSort}(A)$}
  \li \If $n > 0$
  \li \Then  $q \gets Particao(A)$
  \li $QuickSort(A[1:q-1])$
  \li $QuickSort(A[q+1:n])$
\end{codebox}

O tempo de processamento do quick-sort depende dos valores de $q$, que, por sua vez, dependem da ordem original dos elementos.
O melhor caso ocorre quando $q = \frac{n}{2}$, ou seja, quand o arranjo é sempre dividido ao meio.
Neste caso, a recorrência que descreve o tempo de processamento do algoritmo é a mesma do merge-sort:

\begin{displaymath}
  T(n) = 2T\left( \frac{n}{2}\right) + \Theta(n)
\end{displaymath}

Usando o teorema mestre, temos que:
\begin{displaymath}
 T(n) \in \Theta(n.lg(n))
\end{displaymath}

Já o pior caso ocorre quado sempre dividimos a sequência da maneira mais desigual possível.
Isso acontece se originalmente a sequência já está toda em ordem crescente ou toda em ordem decrescente.
Nesses casos, a recorrência que descreve o tempo de processamento é:

\begin{eqnarray*}
  T(1) & = &  c\\
  T(n) & = & T(n-1) + T(1) + \Theta(n)\\
  & = & T(n-1) + c + \Theta(n)\\
  & = & T(n-1) + \Theta(n)\\
\end{eqnarray*}

Esta recorrência não pode ser resolvida usando o teorema mestre, portanto, voltaremos a usar o método da árvore.

% Árvore de recorrência
\begin{center}
\begin{tikzpicture}
\node {$T(n)$}
child {node {$T(n-1) + c_1.n$}
  child {node {$T(n-2) + c_1.(n-1)$}
    child {node {$T(n - i) + c_1.(n - i)$} edge from parent [dashed]
      child {node {$T(1) + c_1$} 
        child {node {$c_2$} edge from parent [solid]}}}}};
\end{tikzpicture}
\end{center}

Temos, portanto, que:

\begin{eqnarray*}
  T(n) & = & c_1(n + (n-1) + (n-2) + \dots + 1) + c_2 \\
  & = & c_1 \sum_{i=1}^n i + c_2 \\
  & = & c_1.\frac{n(n+1)}{2} + c_2\\
  & \in & \Theta(n^2)
\end{eqnarray*}

Vamos agora estudar o caso médio do quick-sort, mas antes disso, vale a pena estudar um pouco sobre casos médios em geral.

\subsection{Análise de Caso Médio}

Uma {\em variável aleatória} é uma função que associa cada evento de um espaço amostral $\Omega$ a um número real $X: \Omega \to \mathbb{R}$.

Definimos o evento $X = x$ como ${\omega \in \Omega : X(\omega) = x}$ e esrevemos $Pr[X=x] = \sum_{\omega \in \Omega : X(\omega) = x}Pr(\omega)$.

O {\em valor esperado}, ou {\em esperança}, de uma variável aleatória é definida como:

\begin{displaymath}
  E[X] = \sum_i x_i.Pr[X = x_i]
\end{displaymath}

\begin{example}
  Seja $X$ uma variável aleatória que associa cada face de um dado ao seu valor.

  \begin{displaymath}
    E[X] = \sum_{i=1}^6 i.Pr[X = i]
  \end{displaymath}

  Supondo que o dados seja justo, ou seja, que a probabildade de cada valor é igual, temos que:
\begin{displaymath}
    E[X] = \frac{1}{6}.\sum_{i=1}^6 i = \frac{21}{6} = 3,5
  \end{displaymath}
  
\end{example}

A experança satisfaz a propriedade da {\em linearidade}, ou seja:

\begin{displaymath}
  E[aX + bY] = aE[X] + bE[Y]
\end{displaymath}

Agora considere um evento $A$.
A {\em variável indicadora} $I\{A\}$ é dada por:

\begin{displaymath}
  I\{A\} = \left\{ \begin{array}{cl}
                   1 & {\textrm se\ A\ ocorre}\\
                   0 & {\textrm caso\ contrario}
                   \end{array}\right.
\end{displaymath}

\begin{lemma}
  Dado um espaço amostral $\Omega$ e um evento $A \subseteq \Omega$ e seja $X_A = I\{A\}$ então $E[X_A] = Pr[A]$.
\end{lemma}
\begin{proof}
  \begin{eqnarray*}
    E[X_A] & = & E[I\{A\}]\\
    & = & 1.Pr[A] + 0.Pr[\Omega \setminus A]\\
    & = & Pr[A] \\
  \end{eqnarray*}
\end{proof}

\begin{example}
  Seja $X$ uma variável aleatória que devolve o número de caras em três arremessos de moedas justas e seja $X_H$ o evento cara em um arremesso.
\begin{displaymath}
  I\{X_H\} = \left\{ \begin{array}{cl}
                   1 & {\textrm se\ deu\ cara}\\
                   0 & {\textrm se\ deu\ coroa}
                   \end{array}\right.
\end{displaymath}

\begin{eqnarray*}
  E[X] & = & E\left[\sum_{i=1}^3I\{X_H\}\right] \\
  & = & \sum_{i=1}^3E[I\{X_H\}]\\
  & = & \sum_{i=1}^3 Pr[X_H] = \frac{3}{2}
\end{eqnarray*}

\end{example}

Calcular o tempo de processamento de um algoritmo no caso médio consiste em calcular o valor esparedo de $T(n)$ para uma certa distribuição de probabilidade da entrada de tamanho $n$.

\begin{example}
  Considere o algoritmo de busca sequêncial que já vimos anteriormente:

  \begin{codebox}
    \Procname{$\proc{BuscaSequencial}(A, b)$}
    \li \For $i \gets 1$ até $n$
    \li \Do \If $a_i = b$
    \li     \Then \Return $i$
        \End
    \End
    \li \Return $\bot$
  \end{codebox}


O número de vezes que a comparação na linha 2 é executado domina o valor de $T(n)$.
Note que ele varia dependendo não apenas do tamanho da entrada, mas da ordem dos valores em $A$.
Quando $b$ é encontrado, o laço é quebrado e o número de comparações cessa.
Assim, por exemplo, no melhor caso, $a_1 = b$ e o algoritmo é executado em tempo $\Theta(1)$.

Seja $X$ o número de vezes que a comparação da linha 2 é executada e seja $X_i = I\{$ na i-esima iteracao a comparação é executada $\}$.
Queremos calcular $E[X]$.
Para isso, vamos supor que $b$ ocorre na sequência e que ele ocorre com a mesma probabilidade em qualquer uma das posições.
Assim temos que:

\begin{eqnarray*}
  E[X] & = & E\left[\sum_{i=1}^nI\{X_i\}\right] \\
  & = & \sum_{i=1}^nE[I\{X_i\}]\\
  & = & \sum_{i=1}^n Pr[X_i]
\end{eqnarray*}

Para calcular $Pr[X_i]$ note que a i-esima comparação será executada se e somente se $b$ ocorre antes de $i$.
Temos então que $Pr[X_i] = \frac{n-i}{n} = 1 - \frac{i}{n}$.
Finalmente podemos calcular:

\begin{eqnarray*}
  E[X] & = & \sum_{i=1}^n Pr[X_i] \\
  & = & \sum_{i=1}^n \left(1 - \frac{i}{n} \right)\\
  & = & n - \frac{1}{n}. \sum_{i=1}^ni\\
  & = & n - \frac{n(n+1)}{2.n}\\
  & = & \frac{n+1}{2} \in \Theta(n) 
\end{eqnarray*}
\end{example}

Passemos agora para um exemplo de algoritmo de ordenação:

\begin{example}

  Como no algoritmo de busca sequêncial, o tempo de processamento da ordenação por inserção não depende apenas do tamanho da entrada, mas da ordem de seus elementos.
  
   \begin{codebox}
     \Procname{$\proc{InsertionSort}(A)$}
     \li \For $j \gets 2$ até $n$
     \li \Do $chave \gets a_j$
     \li    \For $i \gets j-1$ até $1$
     \li    \Do $a_{i+1} \gets a_i$
     \li       \If $a_i > chave$
     \li       \Then sai do laço
               \End
            \End
     \li    $a_{i+1} \gets chave$
     \End
   \end{codebox}
   
   Vimos que no pior caso o tempo de processamento desse algoritmo é $\Theta(n^2)$.
   O melhor caso ocorre quando a sequência já está em ordem crescente.
   Neste caso, sempre entramos na linha 6 na primeira iteração de $i$ e o tempo de processamento das linhas 2 a 6 é $\Theta(1)$ e, portanto, o tempo de processamento do algoritmo todo é $\Theta(n)$.
   Ou seja, o pior e o melhor caso diferem assintóticamente.

   Para calcular o tempo esperado de processamento assumiremos que todas as permutações de uma sequência de $n$ valores é igualmente provável.
   Vamos calcular o valor esperado de uma variável aleatória $X$ que mede o número de comparações executadas na linha 5.
   Nos será útil a variáevl indicadora $I\{a_i$ é comparado com a chave $\}$ que é idêntica a:
   \begin{displaymath}
     X_{i,j} = \left\{ \begin{array}{cl}
                   1 & {\textrm se } a_i \leq a_j\\
                   0 & {\textrm caso\ contrario}
                   \end{array}\right.
   \end{displaymath}   

   Assim temos que:
   
   \begin{eqnarray*}
     E[X] & = & E\left[\sum_{j=2}^n(\sum_{i=1}^{j-1}\{X_{i,j}\}\right] \\
     & = & \sum_{j=2}^n(\sum_{i=1}^{j-1}E[\{X_{i,j}\}] \\
     & = & \sum_{j=2}^n(\sum_{i=1}^{j-1}Pr[\{X_{i,j}\}] \\
   \end{eqnarray*}

   Supondo a distribuição uniforme da ordem dos valores, a chance de $a_j$ ser o k-ésimo menor elemento em $a_1,\dots,a_j$ é igual para todos os $k$s e é $\frac{1}{j}$.
   Além disso, a comparação ocorre quando $a_j$ está em $a_i, \dots, a_{j-1}$.
   Assim, temos que $Pr[\{X_{i,j}\}] = \frac{j-i}{j}$.

   \begin{eqnarray*}
     E[X] & = & \sum_{j=2}^n\left(\sum_{i=1}^{j-1}Pr[\{X_{i,j}\}]\right) \\
     & = & \sum_{j=2}^n\left(\sum_{i=1}^{j-1}\frac{j-i}{j}\right) \\
     & = & \sum_{j=2}^n\left(\frac{1}{j}.\sum_{i=1}^{j-1}(j-i)\right) \\
     & = & \sum_{j=2}^n\left(\frac{1}{j}.\left(j(j-1)-\sum_{i=1}^{j-1}i\right)\right) \\
     & = & \sum_{j=2}^n\left(\frac{1}{j}.\left(j(j-1)-\frac{j(j-1)}{2}\right)\right) \\
     & = & \sum_{j=2}^n\left(\frac{j-1}{2}\right) \\
     & = & \frac{1}{2}\left(\sum_{j=2}^nj - (n-1)\right) \\
     & = & \frac{1}{2}\left(\frac{n(n+1)}{2} - 1 - n+1\right) \\
     & = & \frac{n^2 - n}{4} \in \Theta(n^2)
   \end{eqnarray*}
   
\end{example}



\section{Heap Sort}