C Algoritmo C em ranksort para ordenação de vetores.

[Kaio123]

Poderiam me ajudar a entender o código abaixo, pois preciso preparar o programa para que seja possível ajustar a dimensão do vetor. 

 

int A[N], R[N]; 
main() { 
  ... 
  for (k = 0; k < 100; k++) 
    compute_rank(A[k]); 
  ... 
} 
compute_rank(int elem) { 
  int i, rank = 0; 
  for (i = 0; i < N; i++) 
    if (elem > A[i]) 
    rank++; 
  R[rank] = elem; 
} 

 

[V!OLADOR]

Numa lista, no caso A, com N elementos fora de ordem, pra ordená-los (R) em ordem crescente, uma técnica pouco eficiente mas bem popular é o "rank sort". Pro n-ésimo elemento (n := 1, 2, ..., N) da lista, basta compará-lo com todos os demais e contar quantos são menores que ele. O total de valores menores que o elemento n é o seu rank, ou seja, sua posição numa lista devidamente ordenada, no caso R.

No trecho de código que você postou, a função compute_rank( ) testa o k-ésimo elemento de A (a.k.a elem) contra todos os demais e conta cada ocorrência (rank++) de valores menores que ele. Terminado o calculo do rank, na ultima linha de compute_rank( ), copia-se o k-ésimo elemento para a lista ordenada, R, usando agora o rank do elemento k.

 

O "rank sort" é da família de algorítimos nos quais a complexidade do calculo aumenta com ~ O(N^2).

 

Edit: aparentemente falta um void na definição do retorno da função compute_rank( ).