Cabeçalhos e algoritmos de ordenação em C

Prévia do material em texto

Bibliotecas da linguagem C e 
Algoritmos de Ordenação 
#include <stdio.h> 
Biblioteca de Entrada e Saída Padrão 
 
Principal funcionalidade 
•Todo programa em C que usar funções para entrada ou saída 
de dados como o resgate de valores digitados pelo usuário 
ou então exibição de mensagens de retorno exigirá a 
inclusão do cabeçalho stdio.h. 
 
 
Entrada e Saída 
1.“printf”: A função (print formatted) exibe na tela do monitor uma 
lista “formatada” de números, caracteres, strings etc. O primeiro 
argumento da função é uma string que especifica o formato da 
impressão 
2.“scanf”: A função (scanf format) lê do teclado e “formata” uma 
lista de números, caracteres, strings etc. O primeiro argumento da 
função é uma string que especifica o formato da lista a ser lida. 
Os demais argumentos são os endereços das variáveis onde os valores 
lidos, serão armazenados. A função trata todos os espaços em 
brancos como se fossem ‘ ‘. 
 
Exemplo de programa em C que calcula volume de uma Esfera 
Arquivos 
 Para que um programa possa manipular um arquivo, é preciso 
associar a ele uma variável do tipo FILE (esse tipo está definido no 
arquivo-interface stdio.h). A operação de associação é conhecida como 
"abertura" do arquivo e é executada pela função fopen (= file open). O 
primeiro argumento da função é o nome do arquivo e o segundo argumento é 
"r" ou "w" para indicar se o arquivo deve ser aberto "para leitura" (= 
read) ou "para escrita" (= write). A função devolve o endereço de um 
FILE (ou NULL, se não encontra o arquivo especificado).Depois de usar o 
arquivo, é preciso "fechá-lo" com a função fclose (= file close). 
 Digamos que o arquivo dados.txt contém uma sequência de números 
inteiros separados por brancos. O programa abaixo calcula a média dos 
números. Para ler o arquivo, o programa usa a função fscanf (abreviatura 
de file scanf): 
Programa que calcula média entre dois números usando arquivos 
Funções putc e getc 
 A função mais básica de entrada de dados — mais básica que 
printf — é putc (= put character). Cada invocação da função grava 
um caractere no arquivo especificado. Se c é um caractere e f aponta 
um arquivo, putc( c, f) grava c no arquivo f. Por exemplo, putc( 
'*', stdout) exibe um * na tela do monitor. 
 A função correspondente de leitura de caracteres é getc (= 
get character). Cada chamada da função lê um caractere do arquivo 
especificado. Se f aponta um arquivo então getc( f) lê o próximo 
caractere do arquivo. Em particular, getc( stdin) lê o próximo 
caractere do teclado. 
Funções stdin e stdout 
 Qualquer processo (programa) tem 3 ficheiros automaticamente 
abertos : o da entrada padrão ( standar input), o da saída padrão ( 
standard output), e o da saída de erro ( standard error output). A 
menos que redirecionados, estão normalmente associados ao terminal, 
isto é , ao teclado, ao monitor e monitor respectivamente. A cada um 
destes ficheiros corresponde uma constante, definida em stdio.h que o 
identifica: 
•stdin standard input (teclado) 
•stout standard output (monitor) 
•stderr standard error (monitor) 
 
• O programa abaixo lê uma linha de caracteres do teclado, 
armazena essa linha em um vetor e em seguida exibe esses 
caracteres na tela do monitor. vamos supor que a linha tem no 
máximo 100 caracteres (incluindo o '\n' final): 
#include <ctype.h> 
Biblioteca de manipulação de caracteres 
 
Principal funcionalidade 
•A Biblioteca ctype.h contém funções e macros(um padrão de 
entrada deve ser substituído por um padrão de saída) para 
manipulação de caracteres. 
 
•Utilizando as funções desta biblioteca podemos verificar 
se um caractere é alfabético, numérico, se é maiúsculo, 
minúsculo, representa espaço em branco, etc. 
funções para conversão de caracteres maiúsculos e minúsculos: 
•Tolower() 
 Converte o caractere de maiúsculo para minúsculo. 
 
•Toupper() 
 Converte caractere de minúsculo para maiúsculo. 
funções para manipulação de caracteres : 
•isalnum() 
 Verifica se o caractere é alfanumérico. 
•isalpha() 
 Verificar se o caractere é uma letra do alfabeto. 
•iscntrl() 
 Verificar se o caractere é um caractere de controle. 
 
funções para manipulação de caracteres : 
•isgraph() 
 Verifica se o caractere tem representação gráfica. 
•islower() 
 Verifica se o caractere é uma letra minúscula. 
•isupper() 
 Verifica se o caractere é uma letra maiúscula. 
 
funções para manipulação de caracteres : 
•isprint() 
 Verifica se o caractere é imprimível. 
•ispunct() 
 Verifica se o caractere é um ponto. 
•isspace() 
 Verificar se o caractere é um espaço em branco. 
 
funções para manipulação de caracteres : 
•isdigit() 
 Verificar se o caractere é um número decimal. 
 
•isxdigit() 
Verifica se o caractere é um número hexadecimal. 
 
Exemplos 
 
•Tolower(),Toupper(): 
 
Exemplos 
 
•Isalpha(): 
 
Exemplos 
 
•Isdigit(): 
1.QuickSort 
2.BucketSort 
Algoritmos de Ordenação 
QuickSort 
•Baseia-se em um padrão de projeto fundamental para solução de 
problemas conhecida como Divisão e Conquista (Divide-and-Conquer). 
•O padrão pode ser descrito, de maneira geral, como sendo composto 
de 3 fases: 
1.Divisão: divide-se os dados de entrada em dois ou mais conjuntos 
disjuntos (separados); 
2.Recursão: soluciona-se os problemas associados aos subconjuntos 
recursivamente; 
3.Conquista: obtém-se as soluções dos subproblemas e junta-se as 
mesmas em uma única solução. 
 
QuickSort (Características Gerais) 
•Inicialmente, o vetor de chaves C é particionado em três segmentos 
S1, S2 e S3. 
•S2 deverá conter apenas UMA chave denominada pivô. 
•S1 deverá conter todas as chaves cujos valores são MENORES ou 
IGUAIS ao pivô. Esse segmento está posicionado à esquerda de S2. 
•S3 deverá conter todas as chaves cujos valores são MAIORES do que o 
pivô. Esse segmento está posicionado à direita de S2. 
 
Princípio de Classificação/Ordenação 
•O particionamento é reaplicado aos segmentos S1 e S3 e a todos os 
segmentos correspondentes daí resultantes com quantidade de chaves 
MAIOR que 1. 
•Quando não restarem segmentos a serem particionados, o vetor estará 
ordenado. 
•Perguntas: 
1.Qual é o pivô ideal ? 
2.Como escolher este pivô ? 
QuickSort (Escolha do pivô) 
•O pivô ideal é aquele que produz segmentos S1 e S3 com tamanhos 
(aproximadamente) iguais: chave de valor mediano. 
•A identificação do pivô ideal requer a varredura de todo o vetor (o 
benefício não justifica o custo). 
•Deseja-se um critério de escolha simples e rápido. 
•Sem conhecimento prévio sobre a distribuição de valores das chaves, 
supõe-se que qualquer uma possa ser o pivô e arbitra-se, por 
exemplo, a primeira chave. 
•Caso o vetor já se encontre parcialmente ordenado, pode-se utilizar 
o elemento médio. 
QuickSort: Análise de Desempenho 
•Melhor caso: particionamento produz segmentos com mesmo tamanho. 
•Pior caso: Ocorrerá sempre que o vetor já estiver ordenado ou em 
ordem inversa e escolhermos a menor (ou maior) chave como 
particionadora. 
 
 
BucketSort 
•Bucket sort, é um algoritmo de ordenação que funciona dividindo um 
vetor em um número finito de recipientes. Cada recipiente é então 
ordenado individualmente, seja usando um algoritmo de ordenação 
diferente, ou usando o algoritmo bucketsort recursivamente. O 
bucketsort tem complexidade linear (Θ(n)) quando o vetor a ser 
ordenado contém valores que são uniformemente distribuídos. 
 
Vantagens e Desvantagens 
• O algoritmo de BucketSort é rápido. 
• Possui uma estabilidade através de remoção do primeiro 
 elemento dasequência. 
• É eficiente para entradas de grande quantidade de valores. 
• Complexidade no pior caso é O(n). 
• Não recomendado para pequenas quantidades de entrada. 
 
Código 
Funcionamento do Código 
•Bucket sort funciona do seguinte modo: 
 1. Inicializa um vetor de "baldes", inicialmente vazios. 
 2. Vai para o vetor original, incluindo cada elemento em um 
balde. 
 3. Coloque os elementos dos baldes que não estão vazios no 
vetor original ordenadamente. 
 
Referências 
Página de Tutoriais para programação do GNU/Linux Ubuntu 
http://manpages.ubuntu.com/ 
Página do professor da USP Paulo Feofiloff 
http://www.ime.usp.br/~pf/algoritmos/aulas/io.html