Bucket Sort

Um exemplo de ordenação por distribuição é o algoritmo bucket sort (ordenação balde). Esse algoritmo cria “baldes” com valores atribuídos a estes, esses baldes receberão os números referente ao seu valor depois estes são “esvaziados” seguindo a ordem.
Exemplo vetor = {2,1,3,5,1,3,3,5,4,2}
Levando em consideração o exemplo acima, seria necessário a criação dos baldes 1, 2, 3, 4 e 5. Os números seriam distribuídos nos baldes da seguinte forma:

 Após isso, basta esvaziar os baldes a partir do primeiro para que os números fiquem na ordem.
Os baldes não necessariamente precisam ser numerados dessa forma, para um conjunto muito grande de números a quantidade de baldes seria muito grande e podemos ainda encontrar vetores que não possuem números repetidos, assim, a criação de um balde para cada vetor faz com que a ordenação se torne muito trabalhosa. Para organizar um conjunto grande de número que não se repetem cada balde pode ter um intervalo. Por exemplo: balde 1 receberá número de 0 a 9, balde 2 de 10 a 19, balde 3 de 20 a 29 e assim por diante. Implementação do bucket sort em C (EPPSTEIN, 1996):

#include

 #define tam_balde 100
 #define num_balde 10
 #define max 10

 typedef struct {
         int topo;
         int balde[tam_balde];
 }balde;

 void bucket_sort(int v[],int tam){
     balde b[num_balde];
     int i,j,k;
     for(i=0;i<num_balde;i++)
             b[i].topo=0;

     for(i=0;i<tam;i++){
             j=(num_balde)-1;
             while(1){
                     if(j<0)
                             break;
                     if(v[i]>=j*10){
                             b[j].balde[b[j].topo]=v[i];
                             (b[j].topo)++;
                             break;
                     }
                     j--;
             }
     }

     for(i=0;i<num_balde;i++)
             if(b[i].topo)
                     bubble(b[i].balde,b[i].topo);

     i=0;
     for(j=0;j<num_balde;j++){
             for(k=0;k<b[j].topo;k++){
                     v[i]=b[j].balde[k];
                     i++;
             }
     }
 }

void bubble(int v[],int tam){
    int i,j,temp,flag;
    if(tam)
    for(j=0;j<tam-1;j++){
        flag=0;
        for(i=0;i<tam-1;i++){
            if(v[i+1]<v[i]){
                temp=v[i];
                v[i]=v[i+1];
                v[i+1]=temp;
                flag=1;
            }
        }
        if(!flag)
        break;
    }
}

int main(int argc, char *argv[])
{
    int v[6] = {5,3,7,1,2,9}, i, j, aux, menor, pos;
    bucket_sort(v, 6);

    //mostrar vetor ordenado
    printf("\nVetor ordenado: ");
    for(i=0;i<6;i++)
        printf("%d, ", v[i]);

}

Observe no código acima que o bucket sort não é exatamente um algoritmo de ordenação, mas sim uma distribuição para tornar a organização mais efetiva. Por esse motivo é encontrado no código a função bubble, que é utilizada para organizar os elementos dentro de cada balde. Pode-se substituir o bubble sort por qualquer outro algoritmo de ordenação.

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]);
}

Merge Sort

A ordenação por intercalação faz a divisão do vetor para organiza-lo, ou seja, dividir o problema em subproblemas. O Merge Sort é um exemplo de algoritmo que usa essa técnica “dividir para conquistar”. Os subproblemas são resolvidos recursivamente, mas se forem suficientemente pequenos podem ser resolvidos de maneira mais simples. Após as solução dos subproblemas estes são combinados na solução do problema original. Para a implementação é necessário uma função pra fazer a divisão dos problemas e outra pra implementar a ordenação por intercalação, no algoritmo abaixo podemos ver respectivamente as funções merge e mergeSort
.
A figura abaixo mostra exatamente oque é feito pelo Merge Sort:

A parte azul da imagem representa a função de intercalação, que faz a divisão do vetor. O vetor é dividido até que fique em várias partes com um elemento. Isso por que um vetor de um elemento já está ordenado.
Na parte verde é feita a união desses "subvetores" ordenando-os durante a sua junção, essa é a ilustração da função merge.

Implementação do merge sort em C:

#include <stdio.h>
void merge(int vet[], int tamanho) {
  int *tmp, meio, i, j, k;

  //alocando memória pro tamanho do vetor
  //exemplo: vetor tamanho 5 int = 4 bytes -> 5*4 = 20bytes alocados.
  tmp = (int*) malloc(tamanho * sizeof(int));
  //tmp armazena endereço inicial do espaço alocado

  //se o tmp for vazio sair da função e retornar 1 (falha)
  if (tmp == NULL) {
    exit(1);
  }

  meio = tamanho / 2; //meio do vetor

  i = 0;
  j = meio;
  k = 0;
  while (i < meio && j < tamanho) {
    if (vet[i] <= vet[j]) {
      tmp[k] = vet[i++];
    }
    else {
      tmp[k] = vet[j++];
    }
    ++k;
  }

  if (i == meio) {
    while (j < tamanho) {
      tmp[k++] = vet[j++];
    }
  }
  else {
    while (i < meio) {
      tmp[k++] = vet[i++];
    }
  }

  for (i = 0; i < tamanho; ++i) {
    vet[i] = tmp[i];
  }

  free(tmp); //liberar espaço alocado
}

void mergeSort(int vet[], int tamanho) {
  int meio;

  if (tamanho > 1) {
    meio = tamanho / 2;
    mergeSort(vet, meio);
    mergeSort(vet + meio, tamanho - meio);
    merge(vet, tamanho);
  }
}

int main(int argc, char *argv[])
{
    int v[10] = {9,8,6,1,5,2,6,4,0,6}, i;
    mergeSort(v, 10); //chamada a função merge

    //mostrar vetor ordenado
    printf("\nVetor ordenado: ");
    for(i=0;i<10;i++)
        printf("%d, ", v[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.