Ordenação de Strings - Um teste comparativo

Condições do Teste

Todas as implementações dos algoritmos usaram o mesmo conjunto de dados de teste

• caso 1 - 10000 strings de tamanho 10
• caso 2 - 10000 strings de tamanho 100
• caso 3 - 10000 strings de tamanho 1000

Contagem das operações

Para a contagem das operações foram usadas as seguintes macros:

#define less(A, B) strLess(A,B)

#define exch(A, B) { Item t = A; A = B; B = t; exchCount++; }

#define copy(A, B) { A = B; copyCount++; }

#define compexch(A, B) if (less(B, A)) exch(A, B)

e a seguinte função para a comparação de strings:

/****    comparaçãdo de strings    ****/
/****  e contagem das comparações  ****/
int strLess(char *a, char*b){
  int i = 0;
  compCount++;
  for(;;){
    chCompCount++;
    if(a[i] == '\0')  return (b[i] != '\0');
    if(b[i] == '\0')  return false;
    if(a[i] < b[i])     return true;
    if(a[i++] > b[i++]) return false;
  }   
}   

Implementação

A implementação dos algoritmos de ordenação foi extraída do livro "Algorithms in C" de Robert Sedgewick, com exceção do bucketsort e

está disponível em 'Sorts.c'.

Resultados

A tabela abaixo mostra os resultados obtidos a partir da contagem das operações. Os números representam milhares de operações. Os valores para o bucketsort foram calculados analiticamente. Na tabela, a coluna 'comp.' indica o número de comparações de strings realizadas e 'comp.char' indica o número total de comparações caracter a caracter feitas ao se comparar os strings.

	Número e tamanho dos strings
	10000x10			10000x100			10000x1000
	comp.	comp. char	trocas	comp.	comp. char	trocas	comp.	comp. char	trocas
bublesort	49995	102131	24970	49995	101843	24135	49995	101391	25316
selectionsort	49995	52074	10	49995	52069	10	49995	52078	10
insertionsort	24990	25998	0	25157	26181	0	25336	26348	0
shellsort	229	423	0	237	434	0	262	473	0
quicksort	192	351	31	176	485	31	170	1958	31
mergesort	134	340	0	133	1240	0	133	10239	0
heapsort	235	347	124	235	347	124	235	347	124
bucketsort*	---	100	0.26	---	1000	2.6	---	10000	26