[Enunciado] Não é difícil escrever uma versão iterativa do Quicksort: basta providenciar pilhas para armazenar os índices que delimitam cada um dos segmentos de vetor que aparecem durante a execução do algoritmo. Assim, pilhap[0..t] armazenará os extremos inferiores dos segmentos, enquanto pilhar[0..t] armazenará os extremos superiores.
// A função rearranja o vetor v[p..r],
// com p <= r+1, de modo que ele fique em
// ordem crescente.
void quicksort_it (int v[], int p, int r)
{
int j, *pilhap, *pilhar, t;
pilhap = malloc ((r-p+1) * sizeof (int));
pilhar = malloc ((r-p+1) * sizeof (int));
pilhap[0] = p; pilhar[0] = r; t = 0;
while (t >= 0) {
p = pilhap[t]; r = pilhar[t]; --t;
if (p < r) {
j = separa (v, p, r);
++t; pilhap[t] = p; pilhar[t] = j-1;
++t; pilhap[t] = j+1; pilhar[t] = r;
}
}
}
Como já fizemos na versão recursiva, podemos deixar de empilhar o segundo par de índices, uma vez que ele seria desempilhado logo em seguida:
pilhap[0] = p; pilhar[0] = r; t = 0;
while (t >= 0) {
p = pilhap[t]; r = pilhar[t]; --t;
while (p < r) {
j = separa (v, p, r);
++t; pilhap[t] = p; pilhar[t] = j-1;
p = j + 1;
}
}