MAC0122 2013: Exercício da parte "Ordenação: algoritmo Quicksort"

Salve,

A página Ordenação: algoritmo Quicksort do prof. Paulo Feofiloff tem vários exercícios legais.
Sugiro que você façam pelo menos os exercícios:

2: um algoritmo O(n²) é fácil, seria legal uma solução linear;
4, 5: análise do comportamento da função separa()
6: sobre algoritmos de ordenação estáveis
10: a função separa() desse exercício é essencialmente a utilizada no qsort.c que eu mostrei na aula e reponsável pelo comentário:
```
      Extraído do qsort.c da glibc:

      /* Here's the famous ``collapse the walls'' section of quicksort.
         Gotta like those tight inner loops!  They are the main reaso 
         that this algorithm runs much faster than others. */
```
Simulando um pouco é fácil ver a razão da metáfora "collapse the walls".
Veja também a função separa() da página do prof. Paulo que é creditada a
D. Gries [The Science of Programming, 1981, pag.345]
17(!): quicksort com recursão de cauda (tail recursion).

Além desses exercício leiam a seção "Quicksort: altura da pilha de execução". O que está descrito nessa seção é responsável pelo comentário a seguir

      Extraído do qsort.c da glibc: 

      /* Order size using quicksort.  This implementation incorporates
      four optimizations discussed in Sedgewick:
      [. . .]
 
      4. The larger of the two sub-partitions is always pushed onto the
         stack first, with the algorithm then concentrating on the
         smaller partition.  This *guarantees* no more than log (total_elems)
         stack size is needed (actually O(1) in this case)!  */

Vejam também o exercício 23 da pagína do prof. Paulo:

23. Familiarize-se com a função qsort da biblioteca stdlib.

No link que está no stdlib o prof Paulo da uma explicação bem legal sobre como utilizar a função qsort() da biblioteca do C.

Finalmente, para os interessado, coloquei uma cópia do qsort.c junto com as notas de aula, mas o conteúdo desse arquivo também pode ser visto, por exemplo, na página

http://www.cs.umaine.edu/~chaw/200801/capstone/n/qsort.c.html

Re: Exercício da parte "Ordenação: algoritmo Quicksort"

por Renato de Souza - sexta-feira, 1 nov. 2013, 13:54

Minha função do exercício 2 O. Considerei que se todos os elementos forem maiores ou iguais ao primeiro, ou se todos forem menores que o último, isso seria um vetor arrumado; e um vetor V[p...r-1]. Não gostei muito ela, achei que ficou meio 'feia' e provavelmente dá para fazer sem esse vetor auxiliar, mantendo O, mas não pensei em outra forma.

int arrumado(int v[], int p, int r) {
int vAux[r-p];
int max;
int min;
int cont;

for (cont = 0; cont < r - p; cont++) {
if (cont == 0) {
max = v[cont + p];
vAux[cont] = TRUE;
}

else {
if (v[cont + p] >= max) {
vAux[cont] = TRUE;
max = v[cont + p];
}

else
vAux[cont] = FALSE;
}
}

for (cont = (r - p - 1); cont > -1; cont--) {
if (cont == (r - p - 1))
min = v[cont+p];

else {
if (v[cont+p] >= min)
vAux[cont] = FALSE;

else
min = v[cont];
}

if (vAux[cont+p])
return (cont+p);
}

return -1;
}