Quick Sort

[rmarquesdm 0]

Meu professor passou a seguinte questão:

"Implemente uma versão modificada do Quicksort, modifique a função partition(partição) dele de modo que o valor do meio (mediano) de x[menor], x[maior] e x[meio] (onde meio= (maior+ meio) / 2) seja usado para particionar o vetor."

Como posso implementar isso a partir do código abaixo ou de outro código de partição?

Grato desde já.

void QuickSort(TItem *v, int n) {
 QuickSort_ordena(v, 0, n-1); 
}
void QuickSort_ordena(TItem *v, int esq, int dir) { 
 int i, j;
 QuickSort_particao(v, esq, dir, &i, &j);
 if (esq < j) QuickSort_ordena(v, esq, j);
 if (i < dir) QuickSort_ordena(v, i, dir);
}

void QuickSort_particao(TItem *v, int esq, int dir,
 int *i, int *j) { 
 TItem pivo, aux;
 *i = esq; *j = dir;
 pivo = v[(*i + *j)/2]; /* obtem o pivo x */
 do { 
 while (!(pivo.chave <= v[*i].chave)) (*i)++;
 while (pivo.chave < v[*j].chave) (*j)--;
 if (*i <= *j) { 
 aux = v[*i]; 
 v[*i] = v[*j]; 
 v[*j] = aux;
 (*i)++; (*j)--;
 }
 } while (*i <= *j);
}