Vinícius Massuchetto

Sobre o programa

Uma imagem é, em geral, representada por uma matriz em que cada posição contém a informação de cor (RGB ou tons de cinza) de um pixel (ponto) da imagem. Um dos formatos para representação de imagens em tons de cinza é o PGM. Este formato, simplificadamente, consiste de um arquivo com um cabeçalho em formato ASCII e um corpo em formato binário, contendo a seguinte informação:

Cabeçalho (em ASCII):

Corpo:

Deseja-se fazer mosaicos com imagens PGM. Um mosaico é construído pela composição de diversas imagens. Assim, deve ser possível efetuar operações para adicionar, mover, e retirar os componentes do mosaico, e uma operação que gere a imagem resultante.

Entrada de dados
Os dados de entrada do programa consistem de arquivos de imagens no formato PGM.

Execução do Programa

O pacote de software a ser construído consiste do programa mosaico , que deve ser executado da seguinte forma:
mosaico [opções] [parâmetros...]
Uma das seguintes opções devem ser fornecidas ao programa:

-a adiciona uma imagem ao mosaico em uma certa posição deste.
O uso desta opção exige 4 parâmetros obrigatórios:

Se já existir uma imagem no mosaico com o mesmo valor de id, a imagem existente deve ser substituída pela imagem nova.

-m move uma imagem dentro do mosaico.
Com esta opção, devem ser fornecidos 3 parâmetros:

-r remove uma imagem do mosaico. Esta opção pede como único parâmetro o identificador id da imagem a ser removida;

-p gera a imagem do mosaico em formato PGM. Deve ser fornecido neste caso um nome de arquivo onde a imagem do mosaico será armazenada. A ordem de sobreposição é a ordem crescentes dos identificadores id: imagens id’s pequenos ficam sob imagens com id’s maiores;

A dimensão final da imagem do mosaico depende da posição das diversas imagens colocadas no mosaico e deve ser calculada pelo programa. Nos espaços entre as imagens inseridas a cor deve ser definida como a média dos valores MAXVAL das imagens que compõem o mosaico.

Além do arquivo com a imagem final do mosaico montado, quaisquer dados intermediários (usados para controlar as operações acima) que devam ser persistentes em disco devem ser armazenados em um único arquivo. Cada uma das operações acima (com excessão de -p) deve ser efetivada em tal arquivo.

Finalmente, se houver algum erro durante as operações, o programa deve terminar ou prosseguir conforme a gravidade do erro, mostrando mensagens de erro adequadas ao usuário. Lembre-se que mensagens de erro devem ser enviadas para a saída padrão de erros.

Resultados do Programa

O resultado da execução do programa mosaico deve ser um arquivo com a imagem do mosaico conforme gerada pela opção -p.

Documentação
O pacote deve conter um arquivo de documentação em texto plano (ASCII). Este arquivo, chamado LEIAME, deve conter as seguintes informações:

Além disso, o código fonte deve estar documentado de acordo com o padrão aceito pelo doxygen. A documentação html deve ser gerada a partir da execução deste comando via make.

Arquivo Makefile
O arquivo Makefile deve possuir as regras necessárias para compilar os módulos individualmente e gerar o programa executável. As seguintes regras devem existir obrigatoriamente:

Arquivos Fonte

O programa deve ser implementado exclusivamente em linguagem C , e deve ser composto de no mínimo 3 (três) módulos, sendo obrigatória a criação do módulo mosaico.c. Este módulo deve conter apenas a função main() e diretivas #include e #define que se fizerem necessárias.

As definições de macros, tipos de dados, estruturas e protótipos de funções devem estar em arquivos de cabeçalho (extensão .h). A implementação das diversas funções do software deverá estar em arquivos com extensão .c.

Critério de Avaliação

Legibilidade, elegância, eficiência, modularidade, coesão e acoplamento entre módulos, e uso adequado de estruturas de dados serão levados em conta na avaliação.

Os algoritmos de manipulação das estruturas de dados (inserção, ordenação, etc.) devem ser tão eficientes quanto possível, usando todos os conceitos vistos nas disciplinas de Algoritmos do Curso. Ponteiros e alocação dinâmica de memória devem ser usados onde for eficiente e conveniente. Estruturas dinâmicas abordadas em Alg II, devidamente utilizadas, colaboram fortemente para uma avaliação positiva.

Caso seu programa possua bugs conhecidos, descreva-os no arquivo LEIAME. A documentação de um bug pode evitar que o grupo receba nota Zero. Os itens de avaliação do trabalho e respectivas pontuações são:

Dica: Para transformar uma imagem PGM para PPM, basta replicar o valor do pixel PGM para os três componentes de cor no formato PPM.

Arquivo LEIAME

                                    Arquivos
                    =======================================

LEIAME    Este arquivo
Doxyfile  Arquivo de configuração do doxygen(1)
Makefile  Arquivo com diretivas para make(1)
src/      Diretório contendo arquivos com código-fonte
bin/      Diretório com o executável (criado após `make install')
html/     Diretório com a documentação do doxygen (criado após `make doc')

                                   Compilação
                    =======================================

Para compilar o código-fonte digite

    $ make

    Para instalar o programa use

    $ make install

    Para gerar a documentação use

    $ make doc

    Para compilar, instalar e gerar a documentação use

    $ make all
    ou
    $ make tudo

    Para limpar use

    $ make clean
    ou
    $ make limpa
    ou
    $ make faxina

Exemplos de uso:

    $ bin/mosaico -a 1 arquivo0.pgm 0 0
    $ bin/mosaico -a 2 arquivo1.ppm 10 10
    $ bin/mosaico -m 1 3 3
    $ bin/mosaico -p mosaico.ppm

                 Algoritmos, estrutura de dados e implementação
                    =======================================

1  Banco de dados
-----------------

O banco de dados é divido basicamente em duas partes:

1) Metainformações (sobre os dados).
2) Imagens (os dados);

            +-----------------------------------+------------------+
            | Imagens                           | Metainformações  |
            +-----------------------------------+------------------+
            Banco de dados

1.1  Metainformações
--------------------

As metainformações contêm a posição de cada imagem no banco de dados, o número
idenficador da imagem, entre outros. Essas informações são alteradas a cada ação
no banco de dados, podendo aumentar ou diminuir (em bytes). Por isso, a escolha
de escrever as metainformações no final do arquivo evita movimentações
desnecessárias nos dados. Para adicionar uma imagem, por exemplo, basta ler as
metainformações em memória, escrever a nova imagem a partir do posição de início
das metainformações e, em seguinda, reescrever as metainformações, incluindo os
dados da nova imagem.

Internamente, as metainformações são dividas em duas partes: tabela com dados
sobre as imagens e número de imagens. O número de imagens é o último elemento de
todo o arquivo.

                          +---------------------+---+
                          | Tabela              | N |
                          +---------------------+---+
                          Metainformações

A tabela, por sua vez, guarda em cada "linha" as seguintes colunas:
identificador da imagem (ID), posição da imagem no mosaico (coluna e linha),
posição do início dos dados da imagem no banco de dados e tamanho da imagem no
banco de dados (em bytes).

                  +----+--------+-------+---------+---------+
                  | ID | Coluna | Linha | Posição | Tamanho |
                  +----+--------+-------+---------+---------+
                  |    |        |       |         |         |
                  +----+--------+-------+---------+---------+
                  Tabela

1.2  Imagens
------------

As imagens no banco de dados são guardadas em sequência, uma após a outra. Cada
imagem é dividida em duas partes: o cabeçalho e a grade de pixels.

???

Ao final, o arquivo de banco de dados é organizado como na representação
abaixo.

                     +-------------------------+----------+
                     | 00000000000000000000000 | 11111111 |
                     +----------+-----------+--+----------+
                     | 11111111 | 222222222 | 33333333333 |
                     +----+-----+-----------+-------------+
                     | 33 | 44444444444444444444444444444 |
                     +----+---+---------------------+-----+
                     | 444444 | Tabela          | N |
                     +--------+---------------------+

1.2.1  Formatos das imagens
---------------------------

Os possíveis tipos de imagens aceitas pelo mosaico são Portable Gray Map
(PGM) e Portable Pixel Map (PPM). Estes formatos podem ser ter duas versões:
em texto puro ou em binário. Os formatos e versões são representados no
cabeçalho do arquivo da imagem por um "número mágico". Abaixo, uma tabela
com todos os números mágicos para as imagens conhecidas como Portable AnyMap
(PNM):

                      +---------+------------+-----------+
                      | formato | texto puro |  binário  |
                      +---------+------------+-----------+
                      |   PBM   |     P1     |    P4     |
                      |   PGM   |     P2     |    P5   * |
                      |   PPM   |     P3     |    P6   * |
                      +---------+------------+-----------+
                      Números mágicos

Atualmente o mosaico aceita apenas os formatos P5 e P6.

Cada versão de imagem em binário tem ainda duas variações, dependendo do valor
máximo dentro da imagem, MAXVAL. Se MAXVAL for maior que 255, então cada valor
da matriz da imagem será representado por dois bytes; caso contrário, apenas um
byte. Não são permitidos valores maiores que 65535.

A generalização dos formatos pode ser feita considerando que cada pixel é um
"bloco". Esses blocos, por sua vez, são compostos por "elementos". Dependendo do
valor de MAXVAL esses elementos podem ter tamanho de 1 ou 2 bytes. O número de
elementos de cada bloco pode ser 1 ou 3, dependendo se a imagem é em escala de
cinza ou em cores. Resumindo em termos de blocos e elementos, as possíveis
combinações aceitas pelo mosaico são as seguintes:

               +--------+------------+------------+------------+
               | mágico | núm. elem. | tam. elem. | tam. bloco |
               +--------+------------+------------+------------+
               |   P5   |     1      |     1      |     1      |
               |   P5   |     1      |     2      |     2      |
               |   P6   |     3      |     1      |     3      |
               |   P6   |     3      |     2      |     6      |
               +--------+------------+------------+------------+
               Formatos aceitos pelo mosaico

1.2.2  Conversões das imagens
-----------------------------

O mosaico, imagem final gerada pela composição das imagens no banco de dados,
precisa ter o como MAXVAL o maior valor de todas as imagens, tamanho de elemento
igual ao maior tamanho de todas as imagens e número de elementos igual ao maior
número de elementos das imagens. 

Como todas as imagens finais, que serão coladas no mosaico, precisam ter o mesmo
tamanho de bloco. Essa condição resulta nas possíveis conversões:

         tam. bloco da imagem                  tam. de bloco do mosaico
                   1                ----->                 2
                   1                ----->                 3
                   1                ----->                 6
                   2                ----->                 6
                   3                ----->                 6

A conversão 2->3 não acontece, pois caso existam imagens como tamanho de bloco 2
e 3 dentro do banco de dados o mosaiso terá tamanho de bloco 6.

Cada imagem é armazenada em arquivo em formato sequencial, linha a linha. E
desta mesma forma elas são lidas para a memória. Portanto, essas conversões
podem ser visualizadas mais detalhadamente desenhando os blocos de bytes.

                      +---+             +---+---+
      1->2            | v |   ----->    | 0 : v |
                      +---+             +---+---+

                      +---+             +---+---+---+
      1->3            | v |   ----->    | v : v : v |
                      +---+             +---+---+---+

                  +---+---+             +---+---+---+---+---+---+
      2->6        | 0 : v |   ----->    | 0 : v : 0 : v : 0 : v |
                  +---+---+             +---+---+---+---+---+---+

              +---+---+---+             +---+---+---+---+---+---+
      3->6    | r : g : b |   ----->    | 0 : r : 0 : g : 0 : b |
              +---+---+---+             +---+---+---+---+---+---+

Nesse desenho, cada quadrado separadado por ":" representa um byte e separado
por "|" representa um bloco. "v" é usado para valor em escala de cinza e "r",
"g" e "b" para cores. A conversão de escala de cinza para cores é feita com a
repetição do valor em cinza no tripleto vermelho, verde e azul.

Download

O programa pode baixado aqui.

É fato comum nestes últimos anos que, especialmente adolescentes e jovens, utilizem habitualmente a palavra tipo como advérbio, aposto, vocativo, artigo, entre outros não previstos para tal palavra.

Preocupado com a deficiência no vernáculo português que tal hábito representa, o professor da turma A de Ocina de Computação solicita a seus alunos que escrevam um programa que ajude pessoas com tal vício de linguagem a se recuperarem.

Para tanto, implemente um programa em linguagem C que leia diversas linhas de texto (cada linha é terminada pelo caractere ‘\n’) até encontrar o sinal ‘EOF’. Ao final da leitura o programa deve imprimir as linhas lidas eliminando todas as ocorrências da palavra tipo.

Entretanto, as linhas devem ser impressas na ordem inversa à leitura. Devem ser eliminadas apenas as ocorrências da palavra tipo, ou seja, variações como: tipos, logotipo, tipografia, etc não devem ser afetados.

Pode acontecer que a frase que sem sentido, especialmente se a palavra tipo estava empregada corretamente. Mas isso é aceitável e não precisa ser levado em consideração.

Entrada:

Professor, tipo eu tenho uma dúvida tipo sobre o trabalho
O tipo de problema depende dos tipos de dados
Uma tipografia trabalha com tipos
Pô meu, tipo, tenho uma parada que é do tipo, sacou?

Saída:

Pô meu,, tenho uma parada que é do, sacou?
Uma tipografia trabalha com tipos
O de problema depende dos tipos de dados
Professor, eu tenho uma dúvida sobre o trabalho

Programa:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define LINHA 50
 
char* le_frase() {
	int i = 0, j = LINHA;
	char c, *str;
 
	str = malloc (sizeof(char) * j);
	while ((c = getc(stdin)) && (c != '\n')) {
		if (c == EOF) return 0;
		if (i >= j) str = realloc (str, j *= 2);
		str[i++] = c;
	}
	str[i] = '';
 
	return str;
}
 
int e_letra (char c) {
	if ((65 <= c) && (c <= 122))
		return 1;
	return 0;
}
 
int busca_palavra (char *frase, char *palavra) {
	int i = 0, j = 0;
	int t = strlen(palavra);
 
	for (i = 0; i < strlen(frase); i++) {
		if (frase[i] == palavra[j]) {
			j++;
			if ((j == t) && (!e_letra(frase[i+1])) && (!e_letra(frase[i-t])))
				return i-t+1;
		} else j = 0;
	}
 
	return -1;
}
 
char* remove_palavra (int pos, char *frase, char *palavra) {
	int i, j = 0;
	int tp = strlen(palavra);
	int tf = strlen(frase);
 
	char *nfrase = malloc(sizeof(char) * tf);
	if (pos >= 0) {
		for (i = 0; i < pos; i++)
			nfrase[j++] = frase[i];
		for (i = pos + tp; i < tf; i++)
			nfrase[j++] = frase[i];
	} else {
		strcpy(nfrase,frase);
	}
 
	nfrase[j] = '';
 
	return nfrase;
}
 
char* strtolower (char *str) {
	int i = 0;
 
	while (str[i]) {
		if ((65 <= str[i]) && (str[i] < 97))
			str[i] += 97-65;
		i++;
	}
 
	return str;
}
 
int main () {
	char *frase;
	//char palavra[sizeof(int) * 3] = "tipo";
 
	while ((frase = le_frase())) {
		printf("%s\n",frase);
		printf("%s\n",remove_palavra (busca_palavra(strtolower(frase),palavra), frase, palavra));
		free(frase);
	}
 
	return 0;
}

Há um problema em estatística bastante interessante, e que consiste resumidamente em uma simples pergunta:

Quantas pessoas precisaremos para que haja ao menos uma coincidência de aniversários entre elas?

Esta pergunta desafia nosso senso comum, afinal, uma coincidência de aniversários parece ser algo tão raro, e ao mesmo tempo sabemos que outras milhares de pessoas nascem no mesmo dia em que fazemos aniversário.

Na dúvida simulamos por força bruta, ou seja: Repetimos as possibilidades milhares de vezes até encontrar uma resultado razoável.

Podemos fazer isso através do seguinte programa em C:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int numeroAleatorio(int max, int min, int seed) {
	int numero;
	srand(seed*time(NULL));
 	numero = rand();
	while (numero > max) numero = (numero % (max+1)) + min;
	return numero;
}
 
int buscaAniversariantes(int n) {
	int i, j, coincidencias = 0, dias = 365;
	int aniversariantes[n];
 
	for (i = 1; i <= n; i++) {
		aniversariantes[i] = numeroAleatorio(dias,1,i);
	}
 
	for (i = 1; i <= n-1; i++) {
		for (j = i+1; j <= n; j++) {
			if (aniversariantes[i] == aniversariantes[j]) coincidencias++;
		}
	}
 
	return coincidencias;
}
 
int main() {
	int pessoas;
 
	printf("Número de pessoas: ");
	scanf("%d",&pessoas);
 
	printf("Coincidências: %d \n",buscaAniversariantes(pessoas));
 
	return 0;
}

Vejamos então uma simulação para cada quantidade (sem empregar força bruta).

Número de pessoas: 10; Coincidências: 0
Número de pessoas: 20; Coincidências: 0 
Número de pessoas: 30; Coincidências: 0 
Número de pessoas: 40; Coincidências: 1 
Número de pessoas: 50; Coincidências: 7 
Número de pessoas: 60; Coincidências: 6

Se repetirmos estas execuções diversas vezes, podemos concluir que a partir de 60 pessoas é praticamente impossível não termos ao menos uma coincidência de datas de aniversário. A grosso modo: Não fique achando que a data do seu aniversário é muito sua.

Enunciado:

Considerando o transporte coletivo de Curitiba, mais restritamente os Ligeirinhos e seus respectivos Tubos, o obejtivo desse trabalho é desenvolver um sistema capaz de identificar dois melhores caminhos entre dois Tubos:

• o caminho com o menor número de Tubos; e
• o caminho com o menor número de Ligeirinhos.

A entrada deve ser feita pela entrada padrão (stdin). O arquivo será composto por uma linha com os Tubos inicial e final que se deseja procurar o menor caminho, e uma lista de rotas dos Ligeirinhos e seus Tubos, uma por linha, como no exemplo abaixo:

2 12
1 2 3 4 5 #
5 6 2 7 8 #
2 9 10 11 5 12 #

O # no final de cada linha é para facilitar a leitura. Considere que o número do Ligeirinho começa em 1. Este processo já está implementado no arquivo main.c disponibilizado.

A saída deve ser feita pela saída padrão (stdout). O arquivo será composto por duas linhas: a primeira com o caminho composto pelo menor número de Tubos; e a segunda com o caminho composto pelo menor número de Ligeirinhos. Cada Tubo destes caminhos deve ser mostrado entre parênteses e cada Ligeirinho entre “-”. Por exemplo um conteúdo do arquivo de saída válido.

(2)-1-(3)-1-(4)-1-(5)-3-(12)
(2)-3-(9)-3-(10)-3-(11)-3-(5)-3-(12)

Solução:

1. Introdução

São inúmeras as estruturas que podem ser representadas através de grafos em nosso cotidiano, e da mesma forma são inúmeras as aplicações - muitas vezes implícitas - de algoritmos que efetuem buscas de determinados dados nestas estruturas.

Uma forma interessante e elucidativa de imaginar um grafo são as possibilidades de percorrimento de rotas reais, tais como estradas, pontes ou linhas de ônibus.

No presente trabalho foi proposto como modelo a utilização do famoso, inovador e sofrido sistema de transporte de Curitiba com suas futurísticas estações tubo. Dentre tantas possíveis conexões, qual o menor caminho e o menor número de conexões que podem ser feitas entre dois tubos do sistema integrado?

2. Métodos e Discussões

Utilizou-se a linguagem C e o compilador GCC para a elaboração de um programa que recebe uma listagem de dados que consistem no ponto inicial, final e as rotas dos ônibus.

Toma-se o custo de percorrimento como constante entre cada aresta da estrutura, o que é especialmente ideal ao considerar as voltas e desvios de algumas linhas de ligeirinhos. Justamente esta consideração é a que promove o uso do algoritmo de busca em largura, pois a solução encontrada será sempre a melhor [3], além de ser mais adequada para grafos menores [2].

Aproveitaram-se as funções da biblioteca fornecida pela especificação do trabalho, sendo que o esforço de implementação girou mais sobre as funções `caminho_minimo_tubos` e `caminho_minimo_linhas`.

Uma forma conveniente de tratar este conjunto de dados é através da construção de uma lista de adjacência [2] para então empregar a busca. Esta busca funciona de modo exastivo examinando todas as possibilidades de caminho nível a nível [1].

busca em largura (Início , Alvo)
  entra (Fila, Início)
  enquanto (a Fila não for vazia)
	Nó := sai (Fila)
     se (Nó = Alvo)
	retorna Nó
     para cada (Filho em Expande(Nó))
	 se (não visitado(Filho))
	        marca como visitado (Filho)
	        entra (Fila, Filho)

Já para o menor número de conexões de um ponto a outro empregou-se um algoritmo de cálculo do fecho transitivo. Novamente faz-se um processo exaustivo que detecta todos os vértices que podem ser alcançados a partir do vértice de origem, e os percorre de acordo com a função já utilizada anteriormente.
Retorna-se então a menor rota que passa pelo menor número de trocas.

Como o trabalho deve utilizar a função de escrita de lista já proposta, foi feita uma segunda função para inserção de elementos na lista, `insere_final`. Esta função extra percorre toda a lista no ato da inserção para viabilizar a utilização da `escreve_caminho`, colocando os elementos na ordem devida.

3. Conclusão:

O algoritmo de busca em largura mostra-se eficiente para a tarefa de encontrar o menor número de linhas e tubos entre dois pontos de Curitiba. Suposições ideais são feitas para simplificar o processo e, dependendo da cisrcusntância, é empregado o encontro do fecho transitivo através de `calcula_fecho`.

O que comumente é feito em distâncias reais é a conversão das distâncias do grafo em valores unitários, sempre iguais, e desta maneira pode-se empregar o algoritmo de busca em largura de maneira eficiente e uniforme para encontrar o menor caminho [7].

Embora talvez para uma aproximação real este algoritmo possa não ser o mais adequado, a circunstância é válida devido ao exercício de trabalhar com buscas em árvores de dados, servindo também de uma introdução para a ampliação de conceitos de busca em grafos.

Código fonte: Download.

Referências:

[1] Wikipedia: Breadth-first search - Acessado em 06/12/09
[2] SEDGEWICK, Robert - Algorithms in C
[3] Prof. Paulo Feofiloff: Grafos: Busca em largura - Acessado em 06/12/09
[4] Prof. Paulo Feofiloff: Algoritmos para grafos: listas de adjacência - Acessado em 06/12/09
[5] INF-UFSC: Busca em grafos - Acessado em 06/12/09
[6] Wikipedia: Floyd–Warshall algorithm
[7] Wikipedia: Uniform-cost search

Questão: Implemente um programa em linguagem C que leia (da entrada padrão) diversos nomes de pessoas, um nome por linha (cada linha terminada pelo caractere ‘\n’) até encontrar o sinal ‘EOF’. Linhas em branco devem ser ignoradas, e ao final da leitura o programa deve imprimir os nomes ordenados lexicograficamente (em ordem alfabética).

Utilize alocação dinâmica de meḿória e apontadores.

Exemplo :

Entrada:
Silveira Pereira
Jose da Silva Xavier Mendonca de Barros Pereira
Joao Hilton
Maria dos Santos

Saída:
Joao Hilton
Jose da Silva Xavier Mendonca de Barros Pereira
Maria dos Santos
Silveira Pereira

Modifique o programa anterior de forma que agora os dados de entrada consistam de Nome, Endereç̧o e Telefone das pessoas, cada item destes em uma linha. Ao final da leitura o programa deve imprimir os dados (nome, endereçoo e telefone) ordenados lexicograficamente pelo Nome.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define STRING_INIT 50
#define LINES_INIT 25
 
struct item {
	char *nome;
	char *endereco;
	int telefone;
};
 
char* le_linha() {
	int i = 0, j = STRING_INIT;
	char c, *str;
 
	str = malloc(sizeof(char) * j);
	while ((c = getc(stdin)) && (c != '\n')) {
		if (c == EOF) return 0;
		if (i >= j) {
			str = realloc(str, j *= 2);
		}
		str[i++] = c;
	}
	str[i] = '';
 
	return str;
}
 
char** le_texto() {
	int i = 0, j = LINES_INIT;
	char **txt, *tmp;
 
	txt = malloc(j * (sizeof(char*)));
	while ((tmp = le_linha())) {
		txt[i] = tmp;
		if (i >= j) txt = realloc(txt, j *= 2);
		i++;
	}
 
	return txt;
}
 
char** ordena_texto (char** txt) {
	int i = 0, j = 1;
	char **ret, *tmp;
 
	while (txt[i]) {
		while(txt[j]) {
			if (strcmp(txt[i], txt[j]) >= 0) {
				tmp = txt[i];
				txt[i] = txt[j];
				txt[j] = tmp;
			}
			j++;
		}
		i++;
		j = i;
	}
	return ret;
}
 
struct item* le_itens() {
	int i = 0, j = LINES_INIT;
	struct item *p;
 
	p = malloc (sizeof(*p) * j);
 
	while (1) {
		if (i >= j) p = realloc (p, j *= 2);
		p[i].nome = le_linha();
		if (!p[i].nome) break;
		p[i].endereco = le_linha();
		scanf("%d\n", &p[i].telefone);
		i++;
	}
 
	return p;
}
 
void imprime_itens (struct item *p) {
	int i = 0;
 
	while (p[i].nome) {
		printf ("Nome: %s\n", p[i].nome);
		printf ("Endere&ccedil;o: %s\n", p[i].endereco);
		printf ("Telefone: %d\n\n", p[i].telefone);
		i++;
	}
 
}
 
void imprime_texto (char** txt) {
	int i = 0;
	while (txt[i])
		printf("%s\n",txt[i++]);
}
 
void troca (void *coisa1, void *coisa2) {
	void *tmp;
	tmp = &coisa1;
	coisa1 = &coisa2;
	coisa2 = &tmp;
}
 
struct item* ordena_itens (struct item *p) {
	int i = 0, j = 1, tmpi;
 
	char *tmp;
 
	while (p[i].nome) {
		while (p[j].nome) {
			if (strcmp(p[i].nome, p[j].nome) >= 0) {
				tmp = p[i].nome;
				p[i].nome = p[j].nome;
				p[j].nome = tmp;
 
				tmp = p[i].endereco;
				p[i].endereco = p[j].endereco;
				p[j].endereco = tmp;
 
				tmpi = p[i].telefone;
				p[i].telefone = p[j].telefone;
				p[j].telefone = tmpi;
			}
			j++;
		}
		i++;
		j = i;
	}
 
	return p;
}
 
int main () {
	// Primeira solução
	//char **txt;
	//txt = le_texto();
	//imprime_texto(ordena_texto(txt));
 
	// Segunda solução
	struct item *p = malloc (sizeof(char*));
	p = le_itens();
	imprime_itens(ordena_itens(p));
 
	return 0;
}

Algoritmos de ordenação são fundamentais para uma série de processos computacionais utilizados cotidianamente pela sociedade, e é de igual importância que saibamos em quais condições uns são mais adequados do que outros para o melhor tratamento dos dados. O presente artigo expõe um estudo a respeito dos algoritmos ’selection sort’ e ‘merge sort’, procurando relacionar suas especificidades e custos computacionais.

Os processos de ordenação “selection sort” e “merge sort” compõem o conjunto básico de algoritmos que têm por finalidade a ordenação de dados. Ambos foram tomados como objeto de estudo para a análise de custo de algoritmos.

A análise de custos de algoritmos é feita de maneira ampla e diversificada de acordo com cada aplicação. Tomam-se parâmetros de medição como tempo de execução, tempo do processador, número de acessos à memória, atribuições, trocas, passagem de parâmetros, comparações e outros.

O Selection Sort possui complexidade quadrática por possuir duas instâncias de percorrimento da lista de dados: uma que permanece sobre o limiar da porção ordenada e desordenada do vetor, e outra que percorre a porção desordenada em busca do menor ou maior valor, dependendo do sentido da ordenação.

Já o Merge Sort possui complexidade logarítmica , e faz parte de um grupo de algoritmos do tipo “dividir para conquistar”, dividindo a sequência original em pares de dados ordenados, e depois juntando-os.

Utilizou-se a linguagem C e o compilador GCC para implementação dos dois algoritmos e do gerador de números aleatórios do kernel do Unix através do Bash. Este último gerou a sequência de números aleatórios submetidos à um arquivo de entrada lido pelo programa e ordenado pelos dois algoritmos.

for i in {1..1000000}; do
    echo $RANDOM;
done > teste.in

O custo foi computado através do incremento de variáveis de acordo com o número de interações de cada algoritmo, o que no caso da versão interativa do Selection Sort é o número total de comparações. O Merge Sort teve seu custo contado a cada chamada recursiva de intercalamento.

Custo analítico do Merge Sort:

Custo analítico do Selection Sort:

Com as descrições das complexidades dos algoritmos (quadrádica e logarítmica) das fórmulas 1 e 2, pode-se verificar que em algum momento haverá um cruzamento dos custos, pois um tenderá ao crescimento de custo muito rapidamente, enquanto o outro terá um crescimento linear.

O objetivo aqui seria verificar em que ponto um algoritmo torna-se mais custoso do que outro.
Com alguns procedimentos de ordenação chegou-se os seguintes valores que parecem ser suficientes para expor os resultados:

Referenciando-se aos custos dos algoritmos pode-se traçar o seguinte gráfico.

Para fins de confirmação, gerou-se um arquivo com 106 números aleatório, o qual foi submetido à ordenação somente pelo Merge Sort, e em outra instância pelo algoritmo combinado juntamente com o comando time do Unix.

O custo de cerca de seis a sete elementos de um vetor passa a ser maior em um algoritmo de seleção do que em um algoritmo de mistura. Por tais motivos pode-se construir um algoritmo combinado a fim de verificar o tamanho do fragmento de dados que o Merge Sort gera, e se este fragmento é maior ou melhor do que o limiar de custo entre os dois algoritmos.

Desta maneira, em uma larga ordenação o custo dos fragmentos menores do que sete elementos podem ser ordenados com o Selection Sort para alguma economia de processamento.

Modo de uso do algoritmo:

Os arquivos teste.in e teste.out são listas de inteiros, um por linha, respectivamente desordenadas e ordenadas.

./programa < teste.in > teste.out

Código Final:

# include <stdio.h>
# include <stdlib.h>
# include <time.h>
# include <string.h>
 
// @brief Imprime um vetor com um elemento por linha
// @param v Vetor a ser ordenado
// @param tam Tamanho do vetor a ser ordenado
void ImprimirVetor(int *v,int tam) {
        int i;
        for (i = 0; i < tam; i++) printf("%d\n",v[i]);
}
 
// @brief Intercala blocos de elementos do Merge Sort
// @param v Vetor a ser ordenado
// @param tam Tamanho do vetor a ser ordenado
void Intercala(int *v, int tam) {
        int meio;
        int i, j, k;
        int</em> tmp;
        tmp = (int*) malloc(tam * sizeof(int));
        if (tmp == NULL) exit(1);
        meio = tam / 2;
        i = 0;
        j = meio;
        k = 0;
        while (i < meio && j < tam) {
                if (v[i] < v[j]) {
                        tmp[k] = v[i];
                        ++i;
                } else {
                        tmp[k] = v[j];
                        ++j;
                }
                ++k;
        }
        if (i == meio) {
                while (j < tam) {
                        tmp[k] = v[j];
                        ++j;
                        ++k;
                }
        } else {
                while (i < meio) {
                        tmp[k] = v[i];
                        ++i;
                        ++k;
                }
        }
        for (i = 0; i < tam; ++i) {
                v[i] = tmp[i];
        }
        free(tmp);
}
 
// @brief Ordena um vetor pelo método de seleção
// @param v Vetor a ser ordenado
// @param tam Tamanho do vetor a ser ordenado
void SelectionSort(int *v, int tam) {
        int i, j, min, aux;
        for(i=0; i<tam-1; i++) {
                min = i;
                aux = v[i];
                for(j=i+1; j<tam; j++) {
                        if (v[j] < aux) {
                                min=j;
                                aux=v[j];
                        }
                }
                aux = v[i];
                v[i] = v[min];
                v[min] = aux;
        }
}
 
// @brief Ordena um vetor pelo método de mistura
// @param v Vetor a ser ordenado
// @param tam Tamanho do vetor a ser ordenado
void MergeSort(int *v, int tam) {
        int meio;
        if (tam >= 7) {
                meio = tam / 2;
                MergeSort(v, meio);
                MergeSort(v + meio, tam - meio);
                Intercala(v, tam);
        } else {
                SelectionSort(v,tam);
        }
}
 
int main() {
        int vtam, i = 1;
        int *v;
        v = malloc (i + sizeof(int));
        v[0] = 0;
        while (scanf("%d",&v[i-1]) != EOF) {
                ++i;
                v = (int*) realloc(v, i * sizeof(int));
        }
        --i; --i;
        vtam = i;
        MergeSort(v,vtam);
        ImprimirVetor(v,vtam);
        return 0;
}

Referências:
CORMEN, T.H.; CHARLES, E.L.; RONALD, L.R; CLIFFORD S. Algoritmos Teoria e Pratica. Editora Campus, 2000
MUSSER, David - Measuring Computing Times and Operation Counts of Generic Algorithms. Acessado em 21/10/09
REBELSKY, Samuel – MergeSort – Fundamentals of CSc. Acessado em 19/10/09
SZWARCFITER, J.L.; MARKENZON, . Estruturas de Dados e seus Algoritmos. LTC-Livros Técnicos e Científicos, Rio de Janeiro, RJ, 1994.
WIKIPEDIA. Merge Sort. Acessado em 23/10/09
WIKIPEDIA. Selection Sort. Acessado em 23/10/09

Os métodos de ordenação sistemática são os mais variados, e dessa vez surgiu a ideia de fazer uma ordenação do estilo “AaBbCcDdEeFf…Zz”. Duas principais maneiras são usar posições de vetores como índice, ou simplesmente usar a tabela ASCII, o que por sua vez não é muito seguro uma vez que não sabemos em que sistema o programa irá rodar.

O seguinte exemplo utiliza a tabela ASCII.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <stdio.h>
 
void TrocaLetras(char palavra[],int pos1, int pos2) {
	char aux;
	aux = palavra[pos1];
	palavra[pos1] = palavra[pos2];
	palavra[pos2] = aux;
}
 
int MedeTamanho(char palavra[]) {
	int i = 0;;
	while (palavra[i]) i++;
	return i;
}
 
void OrdenaPalavra(char palavra[],int n) {
	int i, j, menor, auxj, auxmenor;
 
	for (i = 0; i < n-1; i++) {
		menor = i;
		for (j = i+1; j < n; j++) {
			if (palavra[j] >= 97) auxj = -32; else auxj = 0;
			if (palavra[menor] >= 97) auxmenor = -32; else auxmenor = 0;
			if (palavra[j]+auxj == palavra[menor]+auxmenor) {
				if (auxj < 0) auxj = 1; else auxmenor = 1;
			}
			if (palavra[j]+auxj < palavra[menor]+auxmenor) menor=j;
		}
		TrocaLetras(palavra,i,menor);
	}
}
 
int main() {
	int tamanho;
	char palavra[100];
 
	printf("Entre com uma palavra: ");
	scanf("%s",palavra);
	tamanho = MedeTamanho(palavra);
	OrdenaPalavra(palavra,tamanho);
	printf("%s\n",palavra);
	return 0;
}

E este daqui utiliza-se de um vetor com ordem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <stdio.h>
#define MAX 100
 
void VerificaOrdem(char string[], char ordem[], int i) {
     int j;
     for (j=0; string[j] != '\n'; j++)
         if (string[j] == ordem[i])
            printf("%c", ordem[i]);
}
 
int main() {
    char string[MAX];
    char ordem[] = "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz";
    int i;
    printf("Digite a string:\n");
    fgets(string, MAX, stdin);
    printf("\nString ordenada:\n");       
    for (i=0; i<52; i++)
        VerificaOrdem(string, ordem, i);
    printf("\n");
    return 0;
}