Análise e Técnicas de Algoritmos
Período 2003.1

Análise de Algoritmos de Ordenação


Análise de Algoritmos de Ordenação

Formalmente, o problema da ordenação pode ser assim definido:

Entrada:
Uma seqüência de $n$ números $\langle a_1, a_2, ..., a_n \rangle$.
Saída:
Uma reordenação $\langle a\prime_1, a\prime_2, ..., a\prime_n \rangle$ da seqüência de entrada, em que $a\prime_1 \leq a\prime_2 \leq ... \leq a\prime_n$.

Em geral, consideramos a seqüência de entrada como um array de $n$ elementos.

Insertion Sort


\begin{algorithmic}
\STATE {\bf InsertionSort(A)}
\STATE
\FOR{$j \leftarrow 2$\ ...
...1$ \ENDWHILE
\STATE $A[i + 1] \leftarrow chave$\ENDFOR
\STATE
\end{algorithmic}

A análise do algoritmo InsertionSort é muito simples e pode ser efetuada com as regras básicas para análise de algoritmos simples, apresentadas anteriormente.

É trivial observar que o algoritmo é $O(n^2)$.

MergeSort

Alguns algoritmos clássicos que utilizam recursão se baseiam na estratégia de divisão-e-conquista que estudaremos mais adiante. A solução, nestes casos, pode ser definida em 3 passos:

  1. Quebra a entrada original em duas partes.
  2. De forma recursiva ordena cada uma das partes.
  3. Combina as duas partes ordenadas, produzindo a saída ordenada.

Diferentes algoritmos recursivos foram definidos. Algumas soluções concentram os esforços na fase de quebrar o tamanho do problema, fazendo com que a fase de combinação das partes ordenadas seja simples. Outras soluções definem uma forma simples de quebrar o problema, deixando o maior esforço para a combinação dos resultados.

O mergesort faz parte dos algoritmos em que a partição é simples e a combinação é mais trabalhosa.



\epsfig{file=mergesort1.eps}

O algoritmo:


\begin{algorithmic}
\STATE {\bf MergeSort(A, inicio, fim)}
\STATE
\IF{inicio $\l...
... fim)
\STATE Intercala(A, inicio, meio, fim)
\ENDIF
\STATE
\par\end{algorithmic}

A análise do MergeSort requer a resolução de uma relação de recorrência. Para simplificação mas, sem perda de generalidade, vamos considerar $n$ como sendo uma potência de 2. Isso possibilita sempre dividir em duas partes iguais com um número par de elementos. Para $n = 1$, o tempo do mergesort é constante. Nos outros casos, o tempo de execução do algoritmo é o tempo de execução de duas chamadas recursivas com $n/2$ elementos, mais o tempo de intercalação que é linear.

A relação de recorrência é:


\begin{displaymath}\left\{ \begin{array}{ll}
\mbox{$T(n) = 1$} & \mbox{$n \leq ...
...= 2.T(n/2) + n$} & \mbox{nos demais casos}
\end{array}\right. \end{displaymath}

Resolvendo a relação de recorrência temos:


\begin{algorithmic}
\STATE
\STATE $T(n) = 2.T(n/2) + n$\STATE \hspace{0.7cm} $= ...
...ferior}
\STATE
\STATE \hspace{0.7cm} $=O(n.logn)$\STATE
\STATE
\end{algorithmic}

QuickSort

Como o MergeSort, o QuickSort também é um algoritmo que utiliza a estratégia de divisão-e-conquista. Entretato, ao contrário do MergeSort, a parte mais complicada é a quebra ou partição da seqüência de entrada. A combinação das partes é trivial.

O QuickSort é talvez o algoritmo de ordenação mais usado. É fácil de implementar e muito rápido na prática.



\epsfig{file=quicksort1.eps}

O algoritmo:


\begin{algorithmic}
\STATE {\bf QuickSort(A, inicio, fim)}
\STATE
\IF{inicio $\l...
...io, meio - 1)
\STATE QuickSort(A, meio + 1, fim)
\ENDIF
\STATE
\end{algorithmic}

A função de particionamento pode ser definida de diferentes formas. Por exemplo:

\epsfig{file=partquick.eps}

A análise do QuickSort também requer a resolução de uma relação de recorrência. Como nem sempre os dados são divididos em duas metades de igual número de elementos, é necessário fazer análise para o melhor caso, pior caso e o caso médio.

Assumindo que o tempo de partição é $O(n)$, e que a posição final do pivô é $i$, a relação de recorrência é


\begin{displaymath}\left\{ \begin{array}{ll}
\mbox{$T(n) = 1$} & \mbox{$n \leq ...
... - 1) + T(n-i)$} & \mbox{nos demais casos}
\end{array}\right. \end{displaymath}

Algumas considerações:

O Melhor Caso

O melhor caso é quando o pivô sempre fica no meio. Nesse caso, podemos considerar que as duas partes têm a metade de elementos do problema original. Na verdade, estamos super-estimando um pouco mas isso é perfeitamente aceitável pois estamos interessados no big-oh. Logo, $T(n) = 2.T(n/2) + n$ e, como vimos no mergesort, isso indica $O(n.logn)$.

O Pior Caso

No pior caso, o pivô está sempre na primeira ou última posição:


\begin{algorithmic}
\STATE
\STATE $T(n) = n + T(n - 1)$\STATE \hspace{0.7cm} $= ...
...n + 1)/2$}
\STATE
\STATE \hspace{0.7cm} $=O(n^2)$\STATE
\STATE
\end{algorithmic}

Caso Médio


\begin{algorithmic}
\STATE
\COMMENT{Vamos assumir que o pivô tem a mesma probabi...
...(n)/(n + 1)$}
\STATE
\STATE $T_a(n) = O(n.logn) $\STATE
\STATE
\end{algorithmic}

Ordenação por Comparação

Todos os algoritmos de ordenação que estudamos até agora utilizam comparação de elementos. Em uma ordenação por comparação, informação sobre a ordem relativa de dois elementos $a_i$ e $a_j$ em uma sequência é obtida utilizando testes de comparação: $a_i < a_j$, $a_i \leq a_j$, $a_i = a_j$, $a_i \geq a_j$ ou $a_i > a_j$.

É possível usar árvores de decisão para visualizar ordenação por comparação.

A figura a seguir mostra um exemplo de árvore de decisão para ordenação de uma entrada de seqüência de 3 elementos.



\epsfig{file=decisiontree.eps}

As folhas desta árvore indica uma possível ordenação para os elementos. O número de permutações possível é $n!$.

Prova de um limite inferior para o pior caso:

Para definir este limite inferior, vamos utilizar algumas propriedades de árvore:

O caminho mais longo da raiz de uma árvore de decisão para qualquer uma de suas folhas representa o pior caso do número de comprações que o algoritmo de comparação executa (a maior profundidade de todas as folhas).


\begin{algorithmic}
\STATE Para $n$\ elementos, temos $n!$\ folhas.
\STATE Logo,...
...\ e $\log n! = \Theta (n.\log n)$\STATE $d = \Omega (n.\log n)$\end{algorithmic}

Ordenação em Tempo Linear

Counting Sort

Esse algoritmo considera que cada um dos $n$ elementos a serem ordenados é um inteiro entre $1$ e $k$. A idéia básica deste algoritmo é determinar para cada elemento de entrada $x$, o número de elementos menores do que $x$. Desta forma é possível posicionar $x$ no array de saída.

Esse algoritmo requer dois arrays auxiliares: $B[1 .. n]$ que corresponde ao array com a saída ordenada e $C[1..k]$ que provê armazenamento temporário.

O algoritmo:


\begin{algorithmic}
\STATE {\bf Counting-Sort(A, B, k)}
\STATE
\FOR{$i \leftarr...
...leftarrow A[j]$ \STATE $C[A[j]] \leftarrow C[A[j]] - 1$\ENDFOR
\end{algorithmic}

A análise deste algoritmo é trivial. O primeiro e o terceiro laços correspondem a $O(k)$, enquanto o segundo e o quarto laços são $O(n)$. O tempo total é, portanto, $O(n + k)$.

Na prática, utiliza-se CountingSort quando $k = O(n)$, proporcionando um tempo d execução $O(n)$.

Um exemplo:



\epsfig{file=countingsort.eps}



Jorge C. A. de Figueiredo 2003-05-20