Quick Sort

O quick sort é o método de ordenação mais eficiente pra grande maioria dos casos. Sendo seu pior caso O(n²), mas que raramente ocorre. Geralmente ele ocorre como um O(n log n). O quick sorte faz uso de um pivô, que pode ser definido de maneiras diferentes. A forma que se define o vetor influência em sua eficiência. Uma das formas que o pivô pode ser definido é pelo elemento do meio do vetor. Os elementos menores que o pivô são movidos para direita dele e os maiores para sua esquerda, dessa forma se divide o vetor em esquerda e direita. Este mesmo processo é aplicado novamente em esquerda e direita recursivamente, até que o vetor seja totalmente ordenado. Implementação do Quick Sort em C:

int quickSort(int Vet[],int inicio, int fim) {
int i, j, pivot, aux;
    i = inicio;
    j = fim;
    pivot = Vet[(inicio + fim)/2];
    do {
        while (Vet[i] < pivot && i < fim) i++;
        while (pivot < Vet[j] && j > inicio) j--;
        if (i<=j){
            if (i<j){
                aux = Vet[i];
                Vet[i] = Vet[j];
                Vet[j] = aux ;
            }
            i++;
            j--;
        }
    }while (i<=j);
    if(inicio < j) quickSort (Vet, inicio, j);
    if(i< fim ) quickSort (Vet, i, fim);
    return 0;
}

Observe que para chamar o Quick sort é necessário informar o inicio e o fim, sendo que nos outros podemos definir apenas o tamanho. Isso deve acontecer pois, quando ele for chamado recursivamente os valores do inicio e fim será diferente, nesta etapa que ocorre a divisão do vetor. Por isso é dito que ele usa o método dividir para conquistar. Abaixo, a mesma implementação com a chamada da função no main:

#include <stdio.h>
int quickSort(int Vet[],int inicio, int fim) {
int i, j, pivot, aux;
    i = inicio;
    j = fim;
    pivot = Vet[(inicio + fim)/2];
    do {
        while (Vet[i] < pivot && i < fim) i++;
        while (pivot < Vet[j] && j > inicio) j--;
        if (i<=j){
            if (i<j){
                aux = Vet[i];
                Vet[i] = Vet[j];
                Vet[j] = aux ;
            }
            i++;
            j--;
        }
    }while (i<=j);
    if(inicio < j) quickSort (Vet, inicio, j);
    if(i< fim ) quickSort (Vet, i, fim);
    return 0;
}

int main()
{
    int vet[10] = {9,8,6,1,5,2,6,4,0,6}, i;
    quickSort(vet, 0, 9);
    //imprime vetor ordenado
    printf("Vetor ordenado: ");
    for(i = 0; i < 10; i++)
        printf("%d, ",vet[i]);
}

Busca linear ou busca sequencial

A busca linear ou busca sequencial é a forma mais simples de se buscar um resultado em uma lista de dados. O vetor é percorrido comparando cada dado do vetor até encontrar o resultado desejado e retornando o índice do valor encontrado. O dado a ser encontrado é passado como parâmetro para função. O melhor caso nessa situação é se o dado que está sendo procurando é a primeira opção do vetor, e o pior resultado ocorre se este for o ultimo dado do vetor. A complexidade da busca linear é O(n).
Abaixo a implementação desse algoritmo e sua chamada:

#define TAM 10

int buscaLinear(int tamanho, int vetor[], int valor)
{
    int i;
    for(i = 0; i < tamanho; i++)
        if(vetor[i] == valor)
            return i;
        else if(i == tamanho-1)
            return -1;
}

int main(int argc, char *argv[])
{
    int indice, v[TAM] = {9,7,5,2,4,6,10,3,1,8};
    indice = buscaLinear(TAM, v, 6); //chamando a função de busca
    printf("Valor esta na posicao %d", indice);
    getch();
    return 0;
}

Veja também o artigo sobre Busca binária.

Busca binária

A busca binária tem o mesmo objetivo da busca linear, seu tempo de busca é muito mais otimizado que o da busca linear, no entanto, para seu funcionamento, o vetor deve estar ordenado.
Exemplo de vetor ordenado: vetor[10] = {0,1,2,3,4,5,6,7,8,9}; 
A busca binária localiza o meio do vetor com a fórmula (Inicio + Fim) / 2, sendo Inicio a primeira posição do vetor e Fim a ultima posição do vetor. Levando em consideração o exemplo vetor[10] teríamos: (1+10) /2 = 5,5. Em C este valor seria passado para 5, pois ao armazena-lo como inteiro (int) as casas decimais são ignoradas.
Tendo em mãos o meio (5) do vetor ordenado o algoritmo verifica se o valor procurando é ele, se não for ele verificará se é maior ou menor que ele. Sendo maior, a busca será feita apenas na parte direita da metade, se menor, a busca será realizada na parte da esquerda:

O vetor vai sendo divido até que o valor seja encontrado. Se o valor não existir a condição de parada será quando o inicio e o fim for igual e nada foi encontrado. Exemplo do algoritmo de busca binária e sua chamada:

#define TAM 10
//BUSCA BINÁRIA
int buscaBinaria(int vetor[], int tamanho, int valor)
{
    int meio, i, ini = 0, fim = tamanho-1;
    while(ini <= fim)
    {
        meio = (ini + fim) / 2; //encontrando o meio do vetor
        if(valor == vetor[meio]) //valor encontrado?
            return meio; //retorna posição do valor encontrado
        else if(valor < vetor[meio])
            fim = meio - 1;
        else
            ini = meio + 1;
    }
    return -1; //valor não enconrado
}

int main(int argc, char *argv[])
{
    int v[TAM] = {0,1,2,3,4,5,6,7,8,9}, i, indice;

    indice = buscaBinaria(v, TAM, 8);
    printf("\nO valor procurado esta na posicao %d", indice);

    getch();
    return 0;
}

Veja também o artigo sobre Busca linear ou busca sequencial.

Medir tempo de execução em C

Como medir o tempo de execução de um programa ou parte dele?
Talvez você já tenha precisado disso, como eu precisei e tive certa dificuldade. Na verdade é bem simples, oque gera confusão é que muitas vezes o programa é executado tão rapidamente que recebe-se o retorno 0, principalmente se o tempo for mostrado em segundos.
Para a maioria dos casos o ideal é mostra em milissegundos.

Biblioteca time.h

Para fazer uso da função que irá retornar o tempo de execução de um programa é necessário chamar a biblioteca time.h. Aqui no blog já falei sobre ela para fazer o uso das funções rand e srand, para geração de valores aleatórios.
Para chamar essa biblioteca basta por no cabeçalho do seu programa:

#include <time.h>

Dessa vez faremos o uso da função clock, do tipo clock_t, e da macro CLOCKS_PER_SEC.

Função clock() e a macro CLOCKS_PER_SEC

A função clock retorna o tempo de execução exato do momento em que ela foi chamada. Para encontrar o tempo de execução de um programa precisamos usar ela duas vezes, uma para capturar o tempo inicial e outra para capturar o tempo final da execução.
Se fizermos o tempo final - tempo inicial teremos o tempo de execução do programa em milissegundos. Dividindo esse valor pelo CLOCKS_PER_SEC teremos este valor em segundos, pois esta constante tem o valor de 1000000. Para obter o valor em milissegundos, pode-se dividir o CLOCKS_PER_SEC por 1000.
E onde se encaixo o clock_t?
A variável que irá armazenar o valor do tempo da função clock deve ser do tipo clock_t.
Vamos a um exemplo simples usando um algoritmo de ordenção bubble sort:

#include <stdio.h>
#include <stdlib.h>
#include <time.h> //clock(), CLOCKS_PER_SEC e clock_t

#define TAM 10000 //constante para tamanho do vetor

int RandomInteger(int low, int high)
{
    int k;
    srand( (unsigned)time(NULL) );
    k = (rand() % high) + low;
    return k;
}

void bubbleSort (int v[TAM]) {
    int a, b, aux;
    for (a=TAM-1; a>=1; a--) {
        for (b=0; b<a; b++) {
            if (v[b]>v[b+1]) {
                aux = v[b];
                v[b] = v[b+1];
                v[b+1] = aux;
            }
        }
    }
}

int main(){
 clock_t t; //variável para armazenar tempo
 int vetor[TAM]; //vetor com 10000 posições
 int p, r, a;
 p = 0;
 r = TAM;

  //geração aleatório dos valores do vetor
 for(a = 0; a < TAM; a++)
  vetor[a] = RandomInteger(0, TAM);

    //Verificando tempo de execução do bubble sort=> t2
 t = clock(); //armazena tempo
 bubbleSort(vetor);
 t = clock() - t; //tempo final - tempo inicial
 //imprime o tempo na tela
 printf("Tempo de execucao: %lf", ((double)t)/((CLOCKS_PER_SEC/1000))); //conversão para double
}

Observe que ao imprimir o tempo em segundos, como explicado anteriormente, o CLOCKS_PER_SEC foi dividido por 1000, para apresentar o tempo em milissegundos.

Função em Linguagem C - Gerador de CPF

Em outro post expliquei sobre a fórmula do CPF e também publiquei o código fonte de um validador de CPF.
Se você quer saber como funciona a fórmula do CPF acesse: Validador de CPF
Agora estou publicando um gerador de CPF em linguagem C.
Para fazer esta função utilizei também duas funções da biblioteca da linguagem C para gerar números aleatórios: rand e srand. Caso não às conheça acesse o post onde expliquei sobre elas.

#include <stdlib.h>
char cpf[11];

void cpf_generator()
{
    int i, j, dig = 0;
    srand(time(NULL));
    for(i = 0; i <= 9; i++)
        cpf[i] = (rand() % 10) + 48;
    for(i = 0, j = 10; i <= strlen(cpf)-2; i++, j--)
        dig += (cpf[i]-48) * j;
    dig %= 11;
    if(dig < 2)
        cpf[9] = 48;
    else
        cpf[9] = (11-dig)+48;
    dig = 0;
    for(i = 0, j = 11; i <= strlen(cpf)-1; i++, j--)
    {
        dig += (cpf[i]-48) * j;
    }
    dig %= 11;
    if(dig < 2)
        cpf[10] = 48;
    else
        cpf[10] = (11-dig)+48;
}

main()
{
    int i;
    cpf_generator();
    printf("\n");
    for(i = 0; i < 11; i++)
        printf("%c", cpf[i]);
    printf("\n");
    system("pause");
    return 0;
}

Função em linguagem C - Validador de CPF

Fórmula CPF:
Vamos usar como exemplo o CPF 232.315.171-17.
Os 2 últimos dígitos, nesse caso 17, são os "validadores" do CPF. Mas como fazemos para valida-los? Como chegar a esses dígitos?

Primeiro dígito:

Para o primeiro dígito (1) devemos usar os 9 primeiros números do CPF, multiplicando de 10 à 2, como ilustrado na tabela abaixo:

CPF	2	3	2	3	1	5	1	7	1
Multiplicadores	10	9	8	7	6	5	4	3	2
Resultado	20	27	16	21	6	25	4	21	2	Total: 142

O total deve ser dividido por 11 (142/11) e posteriormente 11 deve ser subtraído pelo resto da divisão.
142 / 11 = 12 e resto = 10
Regra: se o resto da divisão for menor que 2 o primeiro dígito será 0.
Como nosso resto não é menor que 2 subtraímos a quantidade de dígitos pelo resto: 11-10 = 1
E assim achamos o nosso primeiro dígito: 1

Segundo dígito:

Para o segundo dígito devemos usar os 10 primeiros dígitos, incluindo o que achamos fazendo a primeira fórmula, multiplicando de 11 à 2, como ilustra a tabela abaixo:

CPF	2	3	2	3	1	5	1	7	1	1
Multiplicadores	11	10	9	8	7	6	5	4	3	2
Resultado	22	30	18	24	7	30	5	28	3	2	Total: 169

O total deve ser dividido por 11 (169/11) e posteriormente 11 deve ser subtraído pelo resto da divisão.
169 / 11 = 15 e resto = 4
Regra: se o resto da divisão for menor que 2 o segundo dígito será 0.
Como nosso resto não é menor que 2 subtraímos a quantidade de dígitos pelo resto: 11-4 = 7
E assim achamos o nosso segundo dígito: 7
Validamos então nosso CPF, pois os dois dígitos que achamos são iguais aos do CPF: 232.315.171-17.
Regra: Além das regras citadas acima o CPF não pode também ter todos os números iguais como, por exemplo: 111.111.111-11.

Função em C para validar o CPF:

int validarCPF(char cpf[])
{
    int i, j, digito1 = 0, digito2 = 0;
    if(strlen(cpf) != 11)
        return 0;
    else if((strcmp(cpf,"00000000000") == 0) || (strcmp(cpf,"11111111111") == 0) || (strcmp(cpf,"22222222222") == 0) ||
            (strcmp(cpf,"33333333333") == 0) || (strcmp(cpf,"44444444444") == 0) || (strcmp(cpf,"55555555555") == 0) ||
            (strcmp(cpf,"66666666666") == 0) || (strcmp(cpf,"77777777777") == 0) || (strcmp(cpf,"88888888888") == 0) ||
            (strcmp(cpf,"99999999999") == 0))
        return 0; ///se o CPF tiver todos os números iguais ele é inválido.
    else
    {
        ///digito 1---------------------------------------------------
        for(i = 0, j = 10; i < strlen(cpf)-2; i++, j--) ///multiplica os números de 10 a 2 e soma os resultados dentro de digito1
            digito1 += (cpf[i]-48) * j;
        digito1 %= 11;
        if(digito1 < 2)
            digito1 = 0;
        else
            digito1 = 11 - digito1;
        if((cpf[9]-48) != digito1)
            return 0; ///se o digito 1 não for o mesmo que o da validação CPF é inválido
        else
        ///digito 2--------------------------------------------------
        {
            for(i = 0, j = 11; i < strlen(cpf)-1; i++, j--) ///multiplica os números de 11 a 2 e soma os resultados dentro de digito2
                    digito2 += (cpf[i]-48) * j;
        digito2 %= 11;
        if(digito2 < 2)
            digito2 = 0;
        else
            digito2 = 11 - digito2;
        if((cpf[10]-48) != digito2)
            return 0; ///se o digito 2 não for o mesmo que o da validação CPF é inválido
        }
    }
    return 1;
}

Há um loop para cada dígito para ser calculado seu valor.
Se um dos dígitos não conferir com o do CPF o programa já retorna 0, informando assim que o CPF é inválido. Caso contrário a função continua para o próximo loop que faz o calculo do segundo dígito. Se este não conferir com o ultimo dígito do CPF o programa retorna 0, senão é retornado o valor 1 indicando que o CPF é válido.
Veja também: Gerador de CPF.

Criando Funções em C

Funções são instruções ou comandos que tem o objetivo de realizar uma tarefa específica.
Em C sempre criamos, pelo menos, a função principal do programa: main
A função main é obrigatória e será sempre a primeira a ser executada ao iniciar o seu programa. Outras funções podem receber qualquer nome, desde que não comecem como números e não contenham caracteres especias.
O uso de funções em seu programa traz muitos benefícios. Evitamos a repetição de um mesmo trecho várias vezes, podemos dividir partes do programa entre a equipe de desenvolvimento, onde cada membro ficará responsável por x função(ões).
Vamos criar uma função simples para imprimir uma linha:

void nl()
{
    printf("\n");
}

main()
{
    printf("Meu programa.");
    nl(); nl();
    printf("Uso de funcoes - linguagem C.");
    nl();
    system("pause");
}

Neste exemplo criei um função do tipo void bem simples que imprimi uma linha nova. O nome da função pode ser escolhida pelo programador, utilizei neste exemplo o nome nl referente a Nova Linha e fiz a chamada dessa função 3 vezes em meu programa.
Sempre que o programa é executado ele é iniciado pelo main, e todas as vezes em que fiz a chamada por nl(); ele vai até essa função e executa suas instruções.
Mais por que utilizar o tipo void?
As funções podem retornar valores depois de executar suas instruções, então, devemos informar o tipo do valor que ela retornará. Nesse caso a nossa função não retorna nenhum valor, por isso devemos inicia-la como void.
Exemplo de função que retorna um valor inteiro:

int soma()
{
    int num1 = 5, num2 = 10;
    return num1 + num2;
}

main()
{
    printf("%d\n",soma());
    system("pause");
}

No programa principal (main), pedimos para imprimir o valor da função soma, como o valor retornado por ela é do tipo inteiro, definimos seu espaço de impressão como "%d". Então a função é executada e ao fazer todas suas instruções nos devolve o valor 15.
É obvio que neste caso não era necessário o uso de uma função para fazer uma soma tão simples. Mais podemos ainda enviar parâmetros para as funções.
Vamos então melhorar as nossas funções nl e soma:

void nl(int n)
{
    int i;
    for(i = 0; i < n; i++)
        printf("\n");
}

main()
{
    printf("Meu programa.");
    nl(3);
    printf("Uso de funcoes - linguagem C.");
    nl(2);
    system("pause");
}

Implementamos na função nl a passagem de um parâmetro. Ao iniciar a função declaramos entre seus parenteses uma variável inteira. Ao chamar a função colocamos entre os parenteses o valor que desejamos passar para a função. Em nosso exemplo fizemos uma chamada enviando o valor 3 e outra enviando o valor 2, que define a quantidade de novas linhas que nossa função deve abrir.

int soma(int num1, int num2)
{
    return num1 + num2;
}

main()
{
    int n1, n2;
    printf("Digite os numeros a somar: \n");
    scanf("%d %d",&n1,&n2);
    printf("%d + %d = %d\n",n1,n2,soma(n1,n2));
    system("pause");
}

Implementamos na função soma a passagem de dois parâmetros. Ao iniciar a função declaramos entre seus parenteses duas variáveis do tipo inteiro. Ao chamar a função colocamos entre os parenteses o valor que desejamos passar para a função. Nesse caso passamos outras variáveis como valores para os parâmetros da função soma (n1 e n2), que receberam valores que foram digitados pelo usuário.

Linguagem C - Função rand e srand

A função rand na linguagem C tem o objetivo de gerar números aleatórios.
Exemplo:

main()
{
int i, aleatorio;
for(i = 0; i < 10; i++)
{
    aleatorio = rand();
    printf("%d\n",aleatorio);
}
system("pause");
}

Observe que a sintaxe é bem simples. Mas por que a cada vez que o laço se repete devemos aplicar o valor da função rand a nossa variável?
A função rand utiliza um número como "semente" para gerar os números aleatórios e esse número só mudará quando a função for chamada novamente.
O resultado do código que temos acima foi:

Perceba que sempre que abrimos nosso programa, os números gerados são o mesmos. Então não temos, ainda, números realmente aleatórios.

E se mudarmos nossa variável para receber o valor da função rand apenas um vez, dessa forma:

main()
{
int i, aleatorio = rand();
for(i = 0; i < 10; i++)
    printf("%d\n",aleatorio);
system("pause");
}

Nossa variável terá sempre o mesmo valor. E esse será nosso resultado:

Para que você gere números que realmente serão imprevisíveis com a função rand, devemos usar no mesmo programa outra função chamada srand (seed randomic) usada para que o número usado como semente seja sempre diferente. O uso mais comum da função srand é junto com a função time da biblioteca <time.h>, que busca a data/hora do seu computador. Como o horário da execução de cada parte do seu programa nunca será o mesmo, tornaremos a semente imprevisível:

#include 
main()
{
srand(time(NULL));
int i, aleatorio;
for(i = 0; i < 10; i++)
{
    aleatorio = rand();
    printf("%d\n",aleatorio);
}
system("pause");
}

O meu resultado foi:

Observe agora que a cada vez que executamos nosso programa um resultado diferente é fornecido.

E como colocar um intervalo especifico para os nossos números? Pois os números gerados pela função rand vão de 0 à 32767.

Podemos utilizar o operador "%" (mod) que nos retorna o resto de uma divisão. Se queremos, por exemplo, simular a jogada de um dado, deveremos limitar nossos números aleatórios entre 1 à 6.

Usando o operador "%" aplicaríamos ao valor da variável que receberá os números aleatórios o seguinte calculo: (rand() % 6)  + 1;

Qualquer número dividido por 6 retornará o resto entre 0 e 5, somando isso a 1 teremos o intervalo de 1 à 6.

Exemplo de um programa que simula a jogada de um dado:

#include 
main()
{
srand(time(NULL));
int i, aleatorio = (rand() % 6) + 1;
printf("%d\n",aleatorio);
system("pause");
}

Exemplo de um programa que simula a retirada de um número de um bingo de 1 à 100:

#include <time.h>
main()
{
srand(time(NULL));
int i, aleatorio = (rand() % 100) + 1;
printf("%d\n",aleatorio);
system("pause");
}