Lesson11

Counting sort

Pressupostos:

• Ordenar $N = r -l + 1$ elementos.
• Chaves podem tomar valor inteiro entre $0$ e $M - 1$.

Consideremos o seguinte exemplo com $N=18$ e $M=7$. Vector original:

/*
 *  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
 *  |  5 |  2 |  1 |  6 |  5 |  3 |  3 |  4 |  0 |  1 |  2 |  4 |  6 |  0 |  4 |  6 |  3 |  1 |
 *  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
 */

A ideia é contar o número de ocorrências de cada elemento no vector original e produzir o vector ordenado:

/*
 *  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
 *  |  0 |  0 |  1 |  1 |  1 |  2 |  2 |  3 |  3 |  3 |  4 |  4 |  4 |  5 |  5 |  6 |  6 |  6 |
 *  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
 *  : 2 x 0's :   3 x 1's    : 2 x 2's :   3 x 3's    :   3 x 4's    : 2 x 5's :   3 x 6's    :
 */

Implementação

A implementação típica do Counting sort utiliza dois vectores auxiliares para além do vector original, o vector cnt com dimensão M+1 e o vector b com dimensão pelo menos igual à do vector a a ordenar. O vector cnt é utilizado para contar os elementos no vector a e para determinar a sua posição final do vector ordenado. O vector b é utilizado para construir o vector ordenado temporariamente uma vez que no Counting sort não é possível em geral ordenar no lugar.

Desta forma, utilizamos os vectores auxiliares

int cnt[M + 1];
int b[maxN];

em que maxN é o maior número de elementos que podemos ordenar, e executamos os seguintes passos:

1. inicializar cada posição de cnt a 0;
2. para cada posição i de a, fazer cnt[a[i]+1]++ (notar que, no fim deste passo, cada posição i+1 de cnt tem o número de vezes que o elemento i ocorrer em a);
3. acumular em cada posição de cnt os valores das posições anteriores por forma que cnt[i] indique a posição no vector ordenado do primeiro elemento com chave i;
4. guardar em b os valores de a ordenados, i.e., b[cnt[a[i]]++]=a[i];
5. copiar b para a.

Implementação em C (incluindo exemplo):

/*
 * int a[]
 *  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
 *  |  5 |  2 |  1 |  6 |  5 |  3 |  3 |  4 |  0 |  1 |  2 |  4 |  6 |  0 |  4 |  6 |  3 |  1 |
 *  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
 *    l                                                                                     r
 *
 * N = r-l+1 = 18 e M = 7
 */
void distcount(int a[], int l, int r)
{
  int i, j, cnt[M+1];
  int b[maxN];

  /*
   * Inicializar cnt[M+1] a 0
   *  +----+----+----+----+----+----+----+----+
   *  |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |
   *  +----+----+----+----+----+----+----+----+
   */
  for (j = 0; j <= M; j++)
    cnt[j] = 0;

  /*
   * Contar elementos em a[], cnt[a[i]+1] fica com o numero de ocorrencias de a[i]
   *  +----+----+----+----+----+----+----+----+
   *  |  0 |  2 |  3 |  2 |  3 |  3 |  2 |  3 |
   *  +----+----+----+----+----+----+----+----+
   */
  for (i = l; i <= r; i++)
    cnt[a[i]+1]++;

  /*
   * Acumular valores em cnt[] por forma a que cnt[i] indique a posicao final de i
   *  +----+----+----+----+----+----+----+----+
   *  |  0 |  2 |  5 |  7 | 10 | 13 | 15 | 18 |
   *  +----+----+----+----+----+----+----+----+
   */
  for (j = 1; j < M; j++)
    cnt[j] += cnt[j-1];

  /*
   * Guardar em {{{b}}} os valores de {{{a}}} ordenados
   *
   * int cnt[]
   *  +----+----+----+----+----+----+----+----+
   *  |  2 |  5 |  7 | 10 | 13 | 15 | 18 | 18 |
   *  +----+----+----+----+----+----+----+----+
   *
   * int b[]
   *  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   *  |  0 |  0 |  1 |  1 |  1 |  2 |  2 |  3 |  3 |  3 |  4 |  4 |  4 |  5 |  5 |  6 |  6 |  6 |
   *  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   *
   * Notar que cnt[] e' actualizado 'a medida que são colocados os elementos em b[]
   */
  for (i = l; i <= r; i++)
    b[cnt[a[i]]++] = a[i];

  /*
   * Copiar {{{b}}} para {{{a}}}
   *
   * int a[]
   *  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   *  |  0 |  0 |  1 |  1 |  1 |  2 |  2 |  3 |  3 |  3 |  4 |  4 |  4 |  5 |  5 |  6 |  6 |  6 |
   *  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   */
  for (i = l; i <= r; i++)
    a[i] = b[i - l];
}

Complexidade

Segundo a implementação acima, temos dois ciclos relativos à dimensão das chaves $M$ e três ciclos relativos às $N$ chaves. Portanto a complexidade em relação ao tempo é $\Theta(N + M)$.

Notar que, uma vez que a ordenação não ocorrer no lugar, precisamos de pelo menos $\Theta(N)$ espaço extra.

O Counting sort é estável.

Implementação alternativa

Neste caso temos o vector cnt com dimensão $M$ em vez de dimensão $M-1$ e, portanto, após acumularmos os valores em cnt, cnt[i] indica a última posição dos elementos i no vector ordenado em vez de indicar a primeira posição.

void distcount2(int a[], int l, int r)
{
  int i, j, cnt[M];
  int b[maxN];
  for (j = 0; j < M; j++)
    cnt[j] = 0;
  for (i = l; i <= r; i++)
    cnt[a[i]]++;
  for (j = 1; j < M; j++)
    cnt[j] += cnt[j-1];
  for (i = r; i >= l; i--)
    b[--cnt[a[i]]] = a[i];
  for (i = l; i <= r; i++)
    a[i] = b[i - l];
}

Exercício: Com esta implementação o Counting sort é estável?

Radix sort

O Radix sort baseia-se na estrutura dos elementos a ordenar. Em geral o processo de ordenação considera cada dígito, bit, ou carácter separadamente utilizando, por exemplo, o Counting sort. Portanto, no caso de ordenarmos palavras, consideramos cada letra como um elemento distinto, ou seja, assumindo que utilizamos o Counting sort internamente no Radix sort, temos $M=26$. No caso de ordenarmos inteiros, consideramos cada dígito como um elemento distinto, ou seja, $M=10$.

Vamos considerar duas versões do Radix sort, Radix LSD e Radix MSD. No caso do Radix LSD (Less Significant Digits) aplicamos o Counting sort sucessivamente dos dígitos menos significativos para os dígitos mais significativos. No caso do Radix MSD (Most Significant Digits) começamos pelos dígitos mais significativos.

Radix LSD

Neste exemplo vamos ordenar as palavras na primeira coluna.

         v     v     v  
for    tea    tag    ace
tip    ace    tar    ago
ilk    fee    ace    cow
tar    wee    tea    fee
ace    tag    fee    for
fee    ilk    wee    ilk
ago    ago    ago    tag
cow    tip    tip    tar
tag    for    ilk    tea
tea    tar    for    tip
wee    cow    cow    wee
         ^     ^     ^

Neste caso, na segunda coluna temos as palavras ordenadas pelo último carácter, utilizando o Counting sort. Na terceira coluna temos as palavras ordenadas pelo segundo carácter. E, na quarta e última coluna, temos as palavras ordenadas pelo primeiro carácter.

Como descrito, a ordenação processa-se pela aplicação sucessiva do Counting Sort, dos caracteres menos significativos para os caracteres mais significativos. Notar que este algoritmo é aplicável apenas a chaves de dimensão fixa e funciona porque o Counting sort é estável, caso contrário ao ordenarmos por um dado dígito podíamos estragar a ordenação já realizada para dígitos menos significativos.

A complexidade neste caso resume-se ao tempo de correr o Counting sort para cada carácter das palavras. Assumindo que o número de caracteres em cada palavra é $k$, temos que a complexidade é $\Theta(k (N + M))$. Uma vez que neste caso temos $N> M$ em geral, podemos escrever a complexidade como $\Theta(k N)$, em que $N$ é o número de palavras a ordenar.

Radix MSD

Considerando o mesmo exemplo que no caso anterior, vamos ordenar as palavras na primeira coluna.

       v       v       v
for    ace   *ace   *ace
tip    ago   *ago   *ago
ilk   *cow   *cow   *cow
tar    for   *fee   *fee
ace    fee   *for   *for
fee   *ilk   *ilk   *ilk
ago    tip    tar   *tag
cow    tar    tag   *tar
tag    tag   *tea   *tea
tea    tea   *tip   *tip
wee   *wee   *wee   *wee
       ^       ^       ^

Neste caso, na segunda coluna temos as palavras ordenadas pelo primeiro carácter, utilizando o Counting sort. Na terceira coluna temos as palavras ordenadas pelo segundo carácter. E, na quarta e última coluna, temos as palavras ordenadas pelo primeiro carácter. Notar que, para cada coluna, as palavras já na posição final estão marcadas com *.

Como descrito, a ordenação processa-se pela aplicação sucessiva do Counting Sort, dos caracteres mais significativos para os caracteres menos significativos. Notar que, para cada carácter, do de maior peso para o de menor peso, as chaves são colocadas em $M$ caixas (uma para cada valor possível) e os elementos em cada caixa são ordenados utilizando os caracteres subsequentes. Podemos optimizar o algoritmo executando o algoritmo Insertion sort em vez do algoritmo Counting sort quando o número de elementos a ordenar (em cada caixa) é menor ou igual a $M$.

Binary MSD radix ou Quick sort binário

                           v                       v                       v                       v
32   1 0 0 0 0 0       1   0 0 0 0 0 1       1   0 0 0 0 0 1       1   0 0 0 0 0 1       1   0 0 0 0 0 1
 1   0 0 0 0 0 1       9   0 0 1 0 0 1       9   0 0 1 0 0 1       6   0 0 0 1 1 0       2   0 0 0 0 1 0
34   1 0 0 0 1 0       6   0 0 0 1 1 0       6   0 0 0 1 1 0       2   0 0 0 0 1 0       6   0 0 0 1 1 0
 9   0 0 1 0 0 1       2   0 0 0 0 1 0       2   0 0 0 0 1 0       9   0 0 1 0 0 1       9   0 0 1 0 0 1
 6   0 0 0 1 1 0      20   0 1 0 1 0 0      10   0 0 1 0 1 0      10   0 0 1 0 1 0      10   0 0 1 0 1 0
 2   0 0 0 0 1 0      18   0 1 0 0 1 0      20   0 1 0 1 0 0      20   0 1 0 1 0 0      18   0 1 0 0 1 0
20   0 1 0 1 0 0      10   0 0 1 0 1 0      18   0 1 0 0 1 0      18   0 1 0 0 1 0      20   0 1 0 1 0 0
18   0 1 0 0 1 0      32   1 0 0 0 0 0      32   1 0 0 0 0 0      32   1 0 0 0 0 0      32   1 0 0 0 0 0
10   0 0 1 0 1 0      34   1 0 0 0 1 0      34   1 0 0 0 1 0      34   1 0 0 0 1 0      34   1 0 0 0 1 0
                           ^                       ^                       ^                       ^

Podemos de facto considerar mais do que apenas um bit, de facto as instruções são em geral feitas de modo a manipular múltiplos de bits. Neste contexto, temos que:

• 1 byte = sequência de tamanho fixo de bits (8!)
• 1 string = sequência de tamanho variável de bytes
• 1 word = sequência de tamanho fixo de bytes

Implementação

/* Definicoes no caso de strings ASCII
 * 
 * +---------------+---------------+---------------+
 * |       A       |       C       |       E       |
 * +---------------+---------------+---------------+
 * \----digito-----\----digito-----\----digito-----\
 * \---------------------word----------------------\
 * 
 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 * | | | | | | | | | | | | | | | | | | | | | | | | |
 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 * \---bitsbyte----\---bitsbyte----\---bitsbyte----\
 * \-------------------bitsword--------------------\
 */
#define bitsword 24
#define bitsbyte 8
#define bytesword 3
#define digit(a,b) a[b]

/* Numero de valores possiveis para um digito */
#define R (1 << bitsbyte)


/* Definicoes no caso de unsigned ints
 * 
 * +---------------+---------------+---------------+---------------+
 * |      09       |      21       |      45       |      03       |
 * +---------------+---------------+---------------+---------------+
 * \----digito-----\----digito-----\----digito-----\----digito-----\
 * \-----------------------------word------------------------------\
 * 
 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 * \---bitsbyte----\---bitsbyte----\---bitsbyte----\---bitsbyte----\
 * \---------------------------bitsword----------------------------\
 */
#define bitsword 32
#define bitsbyte 8
#define bytesword 4
#define digit(n,w) (0xff & ((n) >> ((bytesword - (w) - 1) << 3)))
#define nbit(n,w)  (0x01 & ((n) >> (bitsword - (w) - 1)))

/* Numero de valores possiveis para um digito */
#define R (1 << bitsbyte)


void radixLSD(Item a[], int l, int r)
{
  int i, j, w, count[R+1];
  for (w = bytesword-1; w >= 0; w--) {

    /* Counting sort para o digito w */
    for (j = 0; j < R; j++)
      count[j] = 0;
    for (i = l; i <= r; i++)
      count[digit(a[i], w) + 1]++;
    for (j = 1; j < R; j++)
      count[j] += count[j-1];
    for (i = l; i <= r; i++)
      aux[count[digit(a[i], w)]++] = a[i];
    for (i = l; i <= r; i++)
      a[i] = aux[i - l];
  }
}


void quicksortB(int a[], int l, int r, int w)
{
  int i = l, j = r;
  if (r <= l || w >= bitsword)
    return;

  /* Particiona o vector em duas áreas:
   *  - chaves com bit w a 0
   *  - chaves com bit w a 1
   */
  while (j != i) {
    while (nbit(a[i], w) == 0 && (i < j)) i++;
    while (nbit(a[j], w) == 1 && (j > i)) j--;
    exch(a[i], a[j]);
  }
  if (nbit(a[r], w) == 0)
    j++;

  /* Ordena recursivamente cada área */
  quicksortB(a, l, j-1, w+1);
  quicksortB(a, j, r, w+1);
}


#define bin(A) l+count[A]
void radixMSD(Item a[], int l, int r, int w)
{
  int i, j, count[R+1];

  if (w > bytesword)
    return;

  /* Optimizacao */
  if (r-l <= M) {
    insertion(a, l, r);
    return;
  }

  /* Counting sort para o digito w */
  for (j = 0; j < R; j++)
    count[j] = 0;
  for (i = l; i <= r; i++)
    count[digit(a[i], w) + 1]++;
  for (j = 1; j < R; j++)
    count[j] += count[j-1];
  for (i = l; i <= r; i++)
    aux[count[digit(a[i], w)]++] = a[i];
  for (i = l; i <= r; i++)
    a[i] = aux[i - l];

  /* Os bins denotam as caixas discutidas acima */
  radixMSD(a, l, bin(0)-1, w+1);
  for (j = 0; j < R-1; j++)
    radixMSD(a, bin(j), bin(j+1)-1, w+1);
}

Complexidade

Eficiência dos Radix sort em que $k$ é o número de dígitos por palavra:

• Radix sort geral, tempo de execução cresce com número de bytes dos elementos a ordenar, i.e., $O(k N)$;
• Radix MSD, pode ser sublinear na quantidade total de informação das chaves;
• Radix LSD, $O(N \frac{w}{\log R})$ tempo para chaves com $w$ bits, ou com maior precisão, $O(\frac{w}{\log R} (N+2^{\log R}))$ tempo, em que o mínimo ocorre para $\log R = 0.83 \log N$, e espaço adicional para $R$ contadores e um vector com tamanho $N$.

Avaliação experimental

Ordenação de $N$ inteiros (32 bits):

Exercícios

Exerc.1: Considere a aplicação do algoritmo radix sort LSD, em que em cada passo os elementos são ordenados considerando um dígito, ao seguinte vector:

A = {4327, 5126, 1111, 0721, 1231}

Qual é o terceiro número da sequência, após o algoritmo ter considerado três dígitos?

Exerc.2: Considere a aplicação do algoritmo radix sort LSD, em que em cada passo os elementos são ordenados considerando um dígito, ao seguinte vector:

A = {48372, 62309, 83861, 91874, 18913, 33829, 47812, 95954, 52377, 22394, 56108, 60991}

Qual é o terceiro número da sequência, após o algoritmo ter considerado três dígitos?