Trabalho Counting Sort 2r4n6p

Universidade do Estado de Santa Catarina

COUNTING SORT

Alunos: Alexsandro Pfleger Diogo Raimondi Borges Curso: Tecnologia em Análise e Desenvolvimento de Sistemas

ville Novembro 2015

Explicação geral Seja o vetor v desordenado de tamanho n: v[0]

v[1]

v[2]

... v[n-2]

v[n-1]

v[n]

A ordenação por contagem assume que cada um dos elementos do vetor, pode ser representado por um numero inteiro, no intervalo de 1 à k (k representa o maior elemento do vetor). O método consiste em determinar a quantidade de elementos menores do que um certo elemento x1, para determinar em qual posição do vetor ordenado esse elemento deve ser inserido.

O Funcionamento O CountingSort faz uso de 3 vetores: vetA: um vetor de tamanho n que será o vetor a ser ordenado; vetB: um vetor de tamanho n que será o vetor utilizado para a ordenação dos elementos; vetC: um vetor de tamanho k (valor do maior elemento do vetor de entrada), que será utilizado para a contagem da quantidade de vezes que cada elemento aparece no vetor de entrada e a posição onde ele deve ser inserido no vetor ordenado. O método pode ser dividido em X os: Inicialização dos vetores, contagem do número de ocorrências de cada elemento, contagem da quantidade de números menores e ordenação. 1.

Inicialização Esse o é extremamente simples: O vetor vetA contém os elementos desordenados e os vetores vetB e vetC devem ser inicializados com 0.

Obs: Note que o vetor C tem 6 posições (o maior elemento do vetor de entrada é 6), em regra, pega-se o maior elemento subtrai do menor e soma 1, assim temos o tamanho k do vetor c. ( MAIOR –MENOR ) + 1 = k

2.

Contagem de ocorrências Nesse o é feita a contagem de quantas vezes cada elemento do vetor de entrada aparece. Ex: No vetor A, o número 1 aparece uma vez apenas, portanto o valor da posição 0 do vetor C será 1. O número 2 aparece quatro vezes, portanto o valor da posição 1 do vetor C será 4, e assim por diante.

Obs: Note que como o elemento 4 não está presente no vetor A, a posição 3 do vetor C continua com 0, sendo que o índice de cada elemento do vetor C somado com 1 representa o próprio elemento em A. Obs2: No código ficaria um for de 0 até N onde: C[ A[i] ]++; 3.

Contagem de número menores Nesse o é possível saber a quantidade de elementos menores do que cada elemento do vetor: basta somar cada elemento do vetor C com o seu elemento anterior. Ex: É possível saber, olhando para a posição 0 do vetor C, que só existe 1 número menor que o nº 2. Olhando para a posição 1 do vetor C, é possível saber que existem 5 números menores do que o nº 3 e assim por diante.

Obs: A expressão que representa esta parte do código é um for de 0 até o tamanho K-1 , somando o o i+1 com ele mesmo e com seu anterior: C [i+1] += C[i]

4.

Ordenação Agora o algoritmo vai percorrendo o vetor A do seu fim até o inicio e ordenando os números no vetor B.

Ex: Começando pela posição 9 do vetor A. O elemento é 3 No índice 2 do vetor C (número de ocorrências do número 3 no vetor A) o número é 7. Agora o índice 2, é decrementada em -1 no vetor C sendo que muda de 7 para 6. O número 3 é inserido na posição 6 do vetor.

E assim é feito com cada elemento do vetor,até que o vetor esteja ordenado

Obs: No código esse ultimo o pode ser traduzido como um for de N-1 até 0, f azendo o calculo: B[ --C[ A[i] ] = A[i];

Aspectos positivos •

Ordena vetores em tempo linear para o tamanho do vetor inicial;

•

Não realiza comparações;

•

É um algoritmo de ordenação estável;

Aspectos Negativos •

Necessita de dois vetores adicionais para sua execução, utilizando, assim, mais espaço na memória.

Particularidades para implementar o CountingSort com String Na implementação com string, o primeiro o é reconfigurar as bases de dados, de tal forma que cada palavra tenha associada a ela um numero inteiro, referente a seu tamanho ou ordenação. No caso, para usar as bases de dados do openOffice, foi necessário utilizar um algoritmo que associasse a cada palavra um numero, referente a sua posição em um vetor ordenado. Nesse algoritmo foi primeiro gerado um vetor A com as palavras ordenadas usando o quickSort, depois comparando com a base original openOffice, gerou-se um base onde cada palavra tinha um numero inteiro, representando sua posição no vetor A ordenado, como no exemplo abaixo da base de dados de 194M: bentil 71511 adar 30657 darfuost 106533 aminopirinu 42846 angisilo 46719 Com a base de dados devidamente alterada, criou-se uma estrutura de dados (CountingSort) , aonde cada palavra estava com seu respectivo número. Assim os vetores A e B, são vetores do tipo CountingSort, como demostrado abaixo: typedef struct{ int number; char palavra[50]; }CountingSort; CountingSort A[MAX]; CountingSort B[MAX]; Após isso o método é feito usando o number do vetor A e B, e procedendo normalmente como para um vetor de inteiros. Aspectos positivos: •

Os tempos da ordenação ficam absurdamente rápidos, uma vez que, a base de dados das palavras venha com a informação de um numero inteiro que represente ela, e seja compatível com sua ordenação.

•

Mantêm as características da ordenação com inteiros

Aspectos negativos: •

As bases de dados ficam maiores, como também a memória utilizada no processo de ordenação do vetor A e B;

•

Na maioria das vezes a obtenção do numero que represente a palavra, não é trivial, e despende um consumo de tempo muito grande para ser gerado, alem do mais, tem-se que utilizar um método de ordenação auxiliar e comparações; Obs: A medição dos tempos não se levou em conta o tempo para a criação das bases de tempo, este processo tem O(n²), e levou muito mais tempo para gerar a base de 194M que para ordenar todos as bases geradas, uma vez que na obtenção das bases teve tempo da ordem de dezenas de minutos, e na ordenação dessas bases, dezenas e centenas de milisegundos.

Simulação com String Vetor Inicial hélice

gás

tocha

armário

vinícola

dado

boca

Associando os números 0

1

2

3

4

5

6

hélice

gás

tocha

armário

vinícola

dado

boca

5

4

6

1

7

3

2

3

4

Contagem de Ocorrências 0

1

2

1 1 1 1 1 Obs: Note que o vetor tem o tamanho do maior número associado: 6

5

6

1

1

0

1

2

3

4

5

6

1

2

3

4

5

6

7

0

1

2

3

4

5

6

hélice

gás

tocha

armário

vinícola

dado

boca

5

4

6

1

7

3

2

Ordenação o 1 vetor A

vetor B 0

1

2

3

4

5

6

1

2

3

4

5

6

1

3

4

5

6

7

4

5

boca vetor C 0

1 o 2 vetor A 0

1

hélice

gás

5

4

2

tocha

3

armário

vinícola dado

6

boca

6

1

7

3

2

2

3

4

5

6

vetor B 0

1

boca

dado

vetor C 0

1

2

3

4

5

6

1 1 Após os outros os vetor A

3

4

5

5

7

2

3

4

5

6

0

1

hélice

gás

5

4

tocha 6

armário 1

vinícola dado 7

3

boca 2

vetor B 0

armário vetor C

1

boca

2

dado

3

4

gás

hélice

5

tocha

6

vinícola

0

1

2

3

4

5

6

0

1

2

3

4

5

6

Complexidade O código que ordena o vetor A com o método CountingSort é: typedef struct { int number; char palavra[50]; }CountingSort; CountingSort Base[MAX]; CountingSort VectorSort[MAX]; int aux[MAX];

void CountingSortIni() { int i = 0; //inicia o vetor auxiliar for(i = 0; i <MAX;i++)

aux[i]=0; // guarda no vetor auxiliar quantas vezes um índice esta contido no vetor Base for(i = 0; i < MAX;i++) aux[Base[i].number]++; //guarda em cada posição do vetor auxiliar a verdadeira posição do índice for(i = 0;i<(MAX-1);i++) aux[i+1]+=aux[i]; //ordena os indices do final para o inicio for(i = MAX- 1;i >= 0;i--) VectorSort[--aux[Base[i].number]] = Base[i]; }

Cálculo da Complexidade Vamos Dividir o código em 3 partes sendo cada uma delas um for: de modo que a complexidade será: (n) = (n) + (n) + (n) + (n)

§

Complexidade (n):

for(i = 0; i <MAX;i++) Inicialização = 1

aux[i]=0; Comparações = n Incremento = n Operações = 3 (n) = 1 + 3*n

•

Complexidade (n):

for(i = 0; i < MAX;i++) aux[Base [i].number]++;

Inicialização = 1 Comparações = n

•

Complexidade (n):

Incremento = n Operações = 3

for(i = 0;i<(MAX-1);i++) aux[i+1]+=aux [i]; (n) = 1 + 3*n

•

Complexidade (n):

Inicialização = 1

for(i = MAX- 1;i >= 0;i--) VectorSort[--aux[Base [i].number]] = Base[i];

Comparações = n-1 Incremento = n-1 Operações = 3 (n) = 1 + 3*( n-1)

Inicialização = 1 Comparações = n Incremento = n Operações = 4 (n) = 1 + 4*n

Deste modo a complexidade total será: ()n = 1 + 3*( n-1) + 1 + 3*n + 1 + 3*n + 1 + 4*n ()o = 1 + 13*n

A complexidade do algoritmo é O(n), ou seja, é linear.

Código • include <stdio.h> • include <string.h> • include <stdlib.h> •include #include

#define MAX 194762 typedef struct { int number; char palavra[50];

}CountingSort; CountingSort Base[MAX]; CountingSort VectorSort[MAX]; int aux[MAX];

void CountingSortIni() { int i = 0; //inicia o vetor auxiliar for(i = 0; i <MAX;i++)

aux[i]=0; // guarda no vetor auxiliar quantas vezes um indice esta contido no vetor Base for(i = 0; i < MAX;i++) aux[Base[i].number]++; //guarda em cada posição do vetor auxiliar a verdadeiar posição do indice for(i = 0;i<(MAX-1);i++) inicio

aux[i+1]+=aux[i]; //ordena os indices do final para o

for(i = MAX- 1;i >= 0;i--) VectorSort[--aux[Base[i].number]] = Base[i]; } int main (void) { FILE * arq = fopen("openOffice194M.txt","r"); char pal[50];

int numero=0,i=0; double i1=0.0,f1=0.0; //pega do arquivo o tamanho e a palavra while(!feof(arq)) { fscanf(arq,"%s %d",pal,&numero); stry(Base[i].palavra,pal); Base [i].number=numero;

i++; }

i1=clock(); CountingSortIni(); f1=clock(); printf("Tempo Counting Sort: %lf ",(f1-i1)); system ("pause"); fclose(arq); return 0;

}

Resultados Simulação