Algoritmos de ordenação

• Nas aulas anteriores estudamos dois algoritmos de ordenação:
  • ordenação por seleção
  • ordenação por inserção
• Vimos que o tempo de execução destes algoritmos cresce de forma quadrática com o tamanho da sequência
• Hoje vamos estudar um algoritmo mais eficiente: a ordenação quicksort

Algoritmo Quicksort

• Desenvolvido em 1960 pelo cientista de computadores britânico Tony Hoare,
• Um dos métodos mais elegantes e eficientes para ordenação por comparações
• Muito utilizado na prática, e.g.:
  • a função da biblioteca de C qsort
  • o método sort da biblioteca de arrays de Java

Ideia do Quicksort

Estratégia "divide and conquer":

1. Escolhemos um valor (designado pivot)
2. Partimos a sequência em duas partes:
   • os valores menores do que o pivot;
   • os valores maiores ou iguais ao pivot;
3. Recursivamente ordenamos as duas sub-sequências

Caso base: se a sequência tem 0 ou 1 valores não há nada a fazer (já está ordenada).

Exemplo

Começamos com a sequência: \[ \begin{array}{|c|c|c|c|c|c|c|c|} \hline 55 & 41 & 59 & 26 & 53 & 58 & 97 & 93 \\ \hline \end{array} \]

Exemplo (cont.)

Recursivamente ordenamos as duas sub-sequências repetindo este método: \[ \begin{array}{ccc} \begin{array}{|c|c|c|} \hline 41 & 26 & 53 \\ \hline \end{array} & \begin{array}{|c|} \hline 55 \\ \hline \end{array} & \begin{array}{|c|c|c|c|} \hline 59 & 58 & 97 & 93 \\ \hline \end{array} \\ \overset{\vdots}{\downarrow} & & \overset{\vdots}{\downarrow} \\ \begin{array}{|c|c|c|} \hline 26 & 41 & 53 \\ \hline \end{array} & & \begin{array}{|c|c|c|c|} \hline 58 & 59 & 93 & 97 \\ \hline \end{array} \end{array} \]

Sequência final ordenada: \[ \begin{array}{|c|c|c|c|c|c|c|c|} \hline 26 & 41 & 53 & 55 & 58 & 93 & 97 \\ \hline \end{array} \]

Algoritmo recursivo

\[ \begin{array}{l} \text{Dados:}\quad v[0], v[1], \ldots, v[n-1] \\[1ex] \textsf{qsort}(l, u): \quad \color{red}{\text{// ordenar}~v[l\ldots u]} \\ \qquad \text{se}~ l\geq u~\text{então termina imediatamente;} \\ \qquad \color{red}{\text{// caso contrário:}} \\ \qquad m \gets \textsf{partition}(l, u)~ \color{red}{\text{// partir usando pivot}}\\ \qquad \textsf{qsort}(l, m-1) ~ \color{red}{\text{// ordenar}~v[l\ldots m-1]}\\ \qquad \textsf{qsort}(m+1, u) ~ \color{red}{\text{// ordenar}~v[m+1\ldots u]} \end{array} \]

Algoritmo Quicksort

• Para ordenar a sequência completa basta executar o procedimento recursivo com \(l=0\) e \(u=n-1\): \[ \textsf{qsort}(0, n-1) \]
• Falta especificar como efetuar a partição de \(v[l\ldots u]\): \[ m \gets \textsf{partition}(l,u) \]
• O "truque" é conseguir efetuar esta partição numa só passagem pela sub-sequência
• Vamos usar a formulação do livro Programming Pearls (J. Bentley)

Partir usando pivot

• Queremos partir a sub-sequência \(v[l\ldots u]\)
• Vamos usar o valor mais à esquerda \(v[l]\) para pivot
• Mantemos um índice \(m\) do "ponto médio"
• Ciclo para \(i\) de \(l+1\) até \(u\) inclusivé mantendo:
  • \(v[l+1\ldots m]\) são menores do que o pivot;
  • \(v[m+1\ldots i-1]\) são maiores ou iguais ao pivot

\[ \begin{array}{|c|ccc|ccc|ccc|} \hline \textit{pivot} & & <\textit{pivot} & & & \geq \textit{pivot} & & & ? & \\ \hline \overset{\uparrow}{l} & \overset{\uparrow}{l+1} & & \overset{\uparrow}{m} & & & & \overset{\uparrow}{i} & & \overset{\uparrow}{u} \end{array} \]

Partir usando pivot (cont.)

• No final: trocamos o pivot com o valor no ponto médio

\[ \begin{array}{|ccc|c|ccc|} \hline & <\textit{pivot} & & \textit{pivot} & & \geq \textit{pivot} & \\ \hline \overset{\uparrow}{l} & & \overset{\uparrow}{m-1} & \overset{\uparrow}{m} & \overset{\uparrow}{m+1} & & \overset{\uparrow}{u} \end{array} \]

• A função partição retorna o índice \(m\) do ponto médio

Partir usando pivot: algoritmo

\[ \begin{array}{l} \textsf{partition}(l,u):\\ \qquad m \gets l\\ \qquad \textsf{para} ~i~\text{de} ~l+1 ~\text{até}~u: \\ \qquad\quad \text{se}~ v[i] < v[l]: \\ \qquad\quad\quad\quad m \gets m+1\\ \qquad\quad\quad\quad \text{trocar}~ v[i], v[m]\\ \qquad \text{trocar}~ v[l], v[m]\\ \qquad \text{retornar}~m \end{array} \]

Implementação (função principal)

void quicksort_rec(int vec[], int l, int u) {
  int m;
  if(l >= u)
    return;   // caso base; termina logo
  // senão: caso recursivo 
  m = partition(vec, l, u);
     // partir usando pivot
  quicksort_rec(vec, l, m-1);
     // ordenar vec[l..m-1]
  quicksort_rec(vec, m+1, u);
     // ordenar vec[m+1..u]
}

Implementação (partição)

int partition(int vec[], int l, int u) {
  int i, m, temp;
  m = l;   // m: indice do ponto médio
  for(i = l+1; i<=u; i++) {
     if(vec[i] < vec[l]) { // fora de ordem
      m ++;
      temp = vec[i];  // trocar vec[i], vec[m]
      vec[i] = vec[m];
      vec[m] = temp;
     }
  }
  temp = vec[l]; // trocar vec[l], vec[m]
  vec[l] = vec[m];
  vec[m] = temp;
  return m;
}

Terminação

\[ \begin{array}{|ccc|c|ccc|} \hline & <\textit{pivot} & & \textit{pivot} & & \geq \textit{pivot} & \\ \hline \overset{\uparrow}{l} & & \overset{\uparrow}{m-1} & \overset{\uparrow}{m} & \overset{\uparrow}{m+1} & & \overset{\uparrow}{u} \end{array} \]

• O tamanho das sub-sequências é estritamente menor que o da sequência original
  • o ponto médio não faz parte das sub-sequências
• Logo: a recursão tem de chegar a um caso base
  (sub-sequência de tamanho 0 ou 1)

Complexidade

• O Quicksort executa em tempo \(\approx n \log_2(n)\) para uma sequência aleatória de tamanho \(n\)
• Isto é melhor do que os algoritmos das aulas anteriores:
  • \(n \log_2(n)\) é muito menor que \(n^2\) para \(n\) "grande"
• O pior caso ocorre se a sequência está por ordem ascendente ou descendente:
  • nesse caso o algoritmo apresentado executa em tempo quadrático

Exemplo: sequência ascendente

• Equivalente à ordenação por seleção (\(n^2\) operações)
• Pode ser evitado com uma melhor escolha de pivot

Resultados experimentais

Tempos para ordenação de \(n\) valores aleatórios (segundos):

Resultados experimentais