12 Ordenando

Esse capítulo descreve funções para ordenação de dados, tanto direta quanto indireta (usando um índice). Todas as funções usam o algoritmo heapsort. A ordenação por partes (32)é um algoritmo O(N \log N) que opera localmente e não requer qualquer armazenamento adicional. Essa ausência de armazenamento adicional também fornece performace consistente, o tempo de execução para seu pior caso (dados ordenados) sendo não significativamente maior que os casos médio e o melhor. Note que o algoritmo heapsort não preserva a relativa ordenação de elementos iguais—isso torna o heapsort um algoritmo que produz o que se chama de ordenação instável. Todavia a ordem resultante de elementos iguais irá ser consistente através das diferentes plataformas quando se usa essas funções.

12.1 Ordenando objetos

A seguinte função fornece uma alternativa simples à função padrão de biblioteca qsort. A seguinte função foi pensada para sistemas que não possuem a qsort, não como um substituto da mesma. A função qsort deve ser usada sempre que possível, pois será mais rápida e pode fornecer ordenação estável de elementos iguais. Documentação para qsort está disponível em GNU C Library Manual de Referência.

As funções descritas nessa seção são definidas no arquivo de cabeçalho ‘gsl_heapsort.h’.

Function: void gsl_heapsort (void * array, size_t count, size_t size, gsl_comparison_fn_t compare)

Essa função ordena os count elementos do vetor estático array, cada um de tamanho size, em ordem ascendente usando a função de comparação compare. O tipo de dado usado na função de comparação é definido por,

int (*gsl_comparison_fn_t) (const void * a,
                            const void * b)

Uma função de comparação deve retornar um inteiro negativo se o primeiro argumento for menor que o segundo argumento, 0 se os dois argumentos forem iguais e um inteiro positivo se o primeiro argumento for maior que o segundo argumento.

Por exemplo, a seguinte função pode ser usada para ordenar números do tipo double em ordem numérica ascendente.

int
compare_doubles (const double * a,
                 const double * b)
{
    if (*a > *b)
       return 1;
    else if (*a < *b)
       return -1;
    else
       return 0;
}

A chamada de função apropriada para executar a ordenação é,

gsl_heapsort (array, count, sizeof(double), 
              compare_doubles);

Note que diferentemente de qsort o algoritmo heapsort não pode ser aplicado a uma ordenação estável através de um apontador aritmético. O artifício de comparar ponteiros para elementos iguais na função de comparação não trabalha para o algoritmo heapsort. O algoritmo heapsort executa um rearranjo interno dos dados que destrói sua ordem inicial.

Function: int gsl_heapsort_index (size_t * p, const void * array, size_t count, size_t size, gsl_comparison_fn_t compare): Essa função indiretamente ordena os count elementos do vetor estático array, cada um de tamanho size, em ordem ascendente usando a função de comparação compare. A permutação resultante é armazenada em p, um vetor estático de comprimento n. Os elementos de p fornecem os índices dos elementos do vetor estático que deve ter sido armazenado naquela posição se o vetor estático tivesse sido ordenado nele próprio. O primeiro elemento de p fornece o índice do menor elemento armazenado no vetor estático array, e o último elemento de p fornece o índice do maior elemento em array. O vetor estático contido na variável array não é modificado.

12.2 Ordenado vetores

As funções seguintes irão ordenar os elementos vetor estático ou não, tanto diretamente como indiretamente. Elas são definidas para todos os tipos de dado tanto reais quanto inteiros usando as regras de sufixo normais. Por exemplo, as versões do tipo float das funções de vetor estático são gsl_sort_float e gsl_sort_float_index. As correspondentes funções para vetor não estático são gsl_sort_vector_float e gsl_sort_vector_float_index. Os protótipos estão disponíveis nos arquivos de cabeçalho ‘gsl_sort_float.h’ ‘gsl_sort_vector_float.h’. O conjunto completo de protótipos pode ser incluído usando os arquivos de cabeçalho ‘gsl_sort.h’ e ‘gsl_sort_vector.h’.

Não existe funções para ordenar vetores estáticos ou não com elementos que pertencem ao campo dos númeors complexos, uma vez que a ordenação dos números complexos não é unicamente definida. Para ordenar um vetor complexo pelo módulo de seus elementos calcule um vetor real contendo os módulos dos elemntos complexos, e ordene esse vetor indiretamente. Os índices resultantes fornecem a ordenação apropriada do vetor complexo original.

Function: void gsl_sort (double * data, const size_t stride, size_t n): Essa função ordena os n elementos do vetor estático data com salto stride em ordem numérica ascendente.

Function: void gsl_sort2 (double * data1, const size_t stride1, double * data2, const size_t stride2, size_t n): Essa função ordena os n elementos do vetor estático data1 com salto stride1 em ordem numérica ascendente, enquanto faz o mesmo rearranjo do vetor estático data2 com salto stride2, também de tamanho n.

Function: void gsl_sort_vector (gsl_vector * v): Essa função ordena os elementos do vetor v em ordem numérica ascendente.

Function: void gsl_sort_vector2 (gsl_vector * v1, gsl_vector * v2): Essa função ordena os elementos do vetor v1 em ordem ascendente numérica, enquanto faz o mesmo rearranjo do vetor v2.

Function: void gsl_sort_index (size_t * p, const double * data, size_t stride, size_t n): Essa função indiretamente ordena os n elementos do vetor estático data com salto stride em ordem ascendente, armazenando a permutação resultante em p. O vetor estático p deve ser alocado com um comprimento suficiente para armazenar os n elementos da permutação. Os elementos de p fornecem o índice do elemento do vetor estático que deveria ter sido armazenado naquela posição caso o vetor estático tivesse sido ordenado em si mesmo. O vetor estático data não é modificado.

Function: int gsl_sort_vector_index (gsl_permutation * p, const gsl_vector * v): Essa função ordena indiretamente os elementos do vetor v em ordem ascendente, armazenando a permutação resultante em p. Os elementos de p fornecem o índice do elemento do vetor que deveria ter sido armazenado naquela posição se o vetor tivesse sido ordenado em sí mesmo. O primeiro elemento de p fornece o índice do menor elemento em v, e o último elemento de p fornece o índice do maior elemento em v. O vetor v não é modificado.

12.3 Selecionando os k menores ou maiores elementos

As funções descritas nessa seção selecionam o menor k ou o maior elemento de um conjunto de dados de tamanho N. As rotinas usam um algoritmo de inserção direta O(kN) que é ajustado a subconjuntos que são pequenos se comparados com o tamanho total do conjunto de dados. Por exemplo, as rotinas são úteis para selecionar os 10 maiores valores de entre um conjunto de um milhão de pontos de dados, mas esse mesmo algoritmo não é adequando para selecionar 100,000 valores nesse mesmo milhão de pontos. Se o subconjunto for uma parte significativa do conjunto total de dados pode ser mais rápido ordenar todos os elementos do conjunto de dados com um algoritmo O(N \logN) e obter os menores ou maiores valores.

Function: int gsl_sort_smallest (double * dest, size_t k, const double * src, size_t stride, size_t n): Essa função copia os k menores elementos do vetor estático src, de tamanho n e salto stride, em ordem numérica ascendente gravando o resultado no vetor estático dest. O tamanho k do subconjunto deve ser menor que ou igual a n. Os dados armazenados em src não são modificados por essa operação.

Function: int gsl_sort_largest (double * dest, size_t k, const double * src, size_t stride, size_t n): Essa função copia os k maiores elementos do vetor estático src, de tamanho n e salto stride, em ordem numérica ascendente guardando o resultado no vetor estático dest. k deve ser menor que ou igual a n. Os dados armazenados em src não são modificados por essa operação.

Function: int gsl_sort_vector_smallest (double * dest, size_t k, const gsl_vector * v)
Function: int gsl_sort_vector_largest (double * dest, size_t k, const gsl_vector * v): Essas funções copiam os k menores ou maiores elementos do vetor v gravando o resultado no vetor estático dest. k deve ser menor ou igual ao comprimento do vetor v.

As funções seguintes encontram os índices dos k menores ou maiores elementos de um conjunto de dados,

Function: int gsl_sort_smallest_index (size_t * p, size_t k, const double * src, size_t stride, size_t n): Essa função armazena os índices dos k menores elementos do vetor estático src, de tamanho n e salto stride, no vetor estático p. Os índices são escolhidos de forma que os dados correspondentes sejam disponibilizados em ordem numérica ascendente. O valor k deve ser menor que ou igual a n. Os dados src não são modificados por essa operação.

Function: int gsl_sort_largest_index (size_t * p, size_t k, const double * src, size_t stride, size_t n): Essa função armazena os índices dos k meiores elementos do vetor estático src, de tamanho n e salto stride, no vetor estático p. Os índices são escolhidos de forma que os dados correspondentes sejam disponibilizados em ordem numérica descendente. O valor k deve ser menor que ou igual a n. Os dados src não são modificados por essa operação.

Function: int gsl_sort_vector_smallest_index (size_t * p, size_t k, const gsl_vector * v)
Function: int gsl_sort_vector_largest_index (size_t * p, size_t k, const gsl_vector * v): Essas funções armazenam os índices dos k menores ou maiores elementos do vetor v no vetor estático p. k deve sr menor ou igual ao comprimento do vetor v.

12.4 Calculando o posto

O posto de um elemento é sua ordem nos dados ordenados. O posto (33) é o inverso da permutação de índice, p. O posto pode ser calculado usando o seguinte algoritmo,

for (i = 0; i < p->size; i++) 
{
    size_t pi = p->data[i];
    rank->data[pi] = i;
}

O posto pode ser calculado diretamente a partir da função gsl_permutation_inverse(rank,p).

A seguinte função irá mostrar o posto de cada elemento do vetor v,

void
print_rank (gsl_vector * v)
{
  size_t i;
  size_t n = v->size;
  gsl_permutation * perm = gsl_permutation_alloc(n);
  gsl_permutation * rank = gsl_permutation_alloc(n);

  gsl_sort_vector_index (perm, v);
  gsl_permutation_inverse (rank, perm);

  for (i = 0; i < n; i++)
   {
    double vi = gsl_vector_get(v, i);
    printf ("element = %d, value = %g, rank = %d\n",
             i, vi, rank->data[i]);
   }

  gsl_permutation_free (perm);
  gsl_permutation_free (rank);
}

12.5 Exemplos

O seguinte exemplo mostra como usar a permutação p para mostrar os elementos do vetor v em ordem ascendente,

gsl_sort_vector_index (p, v);

for (i = 0; i < v->size; i++)
{
    double vpi = gsl_vector_get (v, p->data[i]);
    printf ("order = %d, value = %g\n", i, vpi);
}

O próximo exemplo usa a função gsl_sort_smallest para selecionar os 5 menores números entre 100000 valores uniformemente aleatórios armazenados em um vetor estático,

#include <gsl/gsl_rng.h>
#include <gsl/gsl_sort_double.h>

int
main (void)
{
  const gsl_rng_type * T;
  gsl_rng * r;

  size_t i, k = 5, N = 100000;

  double * x = malloc (N * sizeof(double));
  double * small = malloc (k * sizeof(double));

  gsl_rng_env_setup();

  T = gsl_rng_default;
  r = gsl_rng_alloc (T);

  for (i = 0; i < N; i++)
    {
      x[i] = gsl_rng_uniform(r);
    }

  gsl_sort_smallest (small, k, x, 1, N);

  printf ("%d smallest values from %d\n", k, N);

  for (i = 0; i < k; i++)
    {
      printf ("%d: %.18f\n", i, small[i]);
    }

  free (x);
  free (small);
  gsl_rng_free (r);
  return 0;
}

A saída mostra os 5 menores valores, em ordem ascendente,

$ ./a.out 
5 smallest values from 100000
0: 0.000003489200025797
1: 0.000008199829608202
2: 0.000008953968062997
3: 0.000010712770745158
4: 0.000033531803637743

12.6 Referências e Leituras Adicionais

O assunto de ordenar conjuntos é coberto extensivamente em Knuth Sorting and Searching,

Donald E. Knuth, The Art of Computer Programming: Sorting and Searching (Vol 3, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896850.

O algoritmo Heapsort é descrito no seguinte livro,

Robert Sedgewick, Algorithms in C, Addison-Wesley, ISBN 0201514257.

Esse documento foi gerado em 23 de Julho de 2013 usando texi2html 5.0.