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