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

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.

Insertion Sort - Linguagem C

O método Insertion Sort é simples e bem mais eficiente que os outros métodos vistos: Bubble Sort e Selection Sort.

Um exemplo clássico ao explicar este método é o de ordenar um baralho passando as cartas da mão direita para a mão esquerda passando carta por carta.

#define TAM 10
void insertion_sort(int v[])
{
    int i, j, aux;
    for(i = 1; i < TAM; i++)
    {
        aux = v[i];
        j = i - 1;
        while((j >= 0) && (aux < v[j]))
        {
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = aux;
    }
}

main()
{
    int i, vet[TAM] = {10,9,3,6,7,5,1,8,4,2};
    printf("Vetor atual: ");
    for(i = 0; i < TAM; i++)
        printf("%d ", vet[i]);
    printf("\n");
    system("pause");
    insertion_sort(vet);
    printf("\n\nVetor ordenado: ");
    for(i = 0; i < TAM; i++)
        printf("%d ", vet[i]);
    printf("\n");
    system("pause");
    return 0;
}

Neste método a quantidade de iterações dependerá de quão desordenado está o vetor.
Para verificar a quantidade de iterações podemos criar uma variável global e mandar incrementa-la a cada vez que entrar no laço for e no laço while e mandar imprimi-la no final para ver o resultado.
Dessa forma:

#define TAM 10
int k = 0;
void insertion_sort(int v[])
{
    int i, j, aux;
    for(i = 1; i < TAM; i++)
    {
        aux = v[i];
        j = i - 1;
        while((j >= 0) && (aux < v[j]))
        {
            v[j+1] = v[j];
            j--;
            k++;
        }
        v[j+1] = aux;
        k++;
    }
}

main()
{
    int i, vet[TAM] = {10,9,3,6,7,5,1,8,4,2};
    printf("Vetor atual: ");
    for(i = 0; i < TAM; i++)
        printf("%d ", vet[i]);
    printf("\n");
    system("pause");
    insertion_sort(vet);
    printf("\n\nVetor ordenado: ");
    for(i = 0; i < TAM; i++)
        printf("%d ", vet[i]);
    printf("\nk = %d",k);
    system("pause");
    return 0;
}

O resultado neste caso é 42 iterações. Pode parecer pouco, mais quando aumentamos a quantidade de posições do vetor a diferença aumenta.

Selection Sort - Linguagem C

O método de ordenação Selection Sort é pouca coisa mais eficiente que o método Bubble Sort.
Com o Selection Sort percorremos o vetor e guardamos sempre o menor valor. Chegando ao fim do vetor teremos então a primeira posição. A partir da próxima iteração o primeiro vetor já não precisa mais ser verificado pois ele já está ordenado.
Observaremos que o método Selection Sort terá a mesma quantidade de iterações que o método Bubble Sort. Para descobrir nesse caso a quantidade de iterações podemos fazer a seguinte fórmula para um vetor de 10 posições:
(n-1)+(n-2)+(n-3)+(n-4)+(n-5)+(n-6)+(n-8)+(n-8)
Sendo n o tamanho do vetor, temos o resultado: (9)+(8)+(7)+(6)+(5)+(4)+(3)+(2) = 44 iterações.

Apesar de os 2 terem a mesma quantidade de iterações, no método Selection Sort temos uma leve vantagem quando comparamos a quantidade de trocas. No método Selection Sort armazenamos o menor valor e somente ao final da primeira passada completa pelo vetor que fazemos a troca.

#define TAM 10
void selection_sort(int v[])
{
    int i, j, aux, menor;
    for(i = 0; i < TAM; i++)
    {
        menor = i;
        for(j = i+1; j < TAM; j++)
        {
            if(v[j] < v[menor])
                menor = j;
        }
        if(i != menor)
        {
            aux = v[i];
            v[i] = v[menor];
            v[menor] = aux;
        }
    }
}

main()
{
    int i, vet[TAM] = {10,9,3,6,7,5,1,8,4,2};
    printf("Vetor atual: ");
    for(i = 0; i < TAM; i++)
        printf("%d ", vet[i]);
    printf("\n");
    system("pause");
    selection_sort(vet);
    printf("\n\nVetor ordenado: ");
    for(i = 0; i < TAM; i++)
        printf("%d ", vet[i]);
    printf("\n");
    system("pause");
    return 0;
}

Nesse código criei a função que ordena com o método Selection Sort. Podemos assim mandar o vetor como argumento para ser ordenado por nossa função. Para facilitar a visualização do que ocorreu na função eu criei um vetor com valores de 1 a 10 embaralhados e mandei imprimir esses números antes de serem ordenados e depois de serem ordenados.
O algoritmo do selection sort pode ser desenvolvido usando outras lógicas que no final terão o mesmo resultado.
Tanto o método Selection Sort quanto o método Bubble Sort não apresentam boa eficiência para ordenação de grandes vetores. Porém, é importante estuda-los para melhor entender os outros métodos de ordenação que foram basicamente melhoras desses métodos com menor eficiência.

Métodos de ordenação de vetores

• Bubble Sort - Linguagem C
• Selection Sort - Linguagem C
• Insertion Sort - Linguagem C
• Merge Sort - Linguagem C
• Bucket Sort - Linguagem C
• Quick Sort - Linguagem C

Bubble Sort - Linguagem C

O método de ordenação bubble sort é um método muito simples de ordenação. Porém, seu desempenho é muito ruim. Quanto maior o vetor a ser ordenado por ele, pior será seu desempenho.

Fiz um trabalho em MATLAB recentemente na faculdade onde eu apresentava essa diferença gritante entre o método bubble sort e o método shell sort.
Vou publicar hoje o método bubble sort em C e em breve darei sequencia com outros métodos de ordenação.
O método bubble sort (Ordenação bolha) recebeu esse nome por que durante sua ordenação os maiores números são ordenados primeiro, como as bolhas de um recipiente onde as maiores chegam primeiro a superfície. Ou seja, ele compara todos os números do início ao fim do vetor e sempre que o primeiro for maior ele inverte as posições. Terminando de verificar o vetor a primeira vez ele terá encontrado o maior número e na próxima passada ele não verificará o ultimo número ordenado.

void bubbleSort(int v[], int tam)
{
    int i, j, aux, troca;
    for(i = 0; i < tam; i++)
    {
        troca = 0;
        for(j = 0; j < (tam-1)-i; j++)
        {
            if(v[j] > v[j+1])
            {//realiza troca dos elementos
                aux = v[j];
                v[j] = v[j+1];
                v[j+1] = aux;
                troca = 1;
            }
        }
        //se não foram realizadas trocas, vetor já está ordenado
        if(troca == 0) 
            break; //sai do laço
    }
}

int main(int argc, char *argv[])
{
    int i, vet[10] = {10,9,3,6,7,5,1,8,4,2};
    printf("Vetor atual: ");
    for(i = 0; i < 10; i++) //mostrar vetor desordenado
        printf("%d ", vet[i]);
    printf("\n");
    system("pause"); //pausar
    bubbleSort(vet, 10); //chamada a função bubble enviando vetor e tamanho dele
    printf("\n\nVetor ordenado: ");
    for(i = 0; i < 10; i++) //mostrar vetor ordenado
        printf("%d ", vet[i]);
    printf("\n");
    system("pause"); //pausar
    return 0;
}

Nesse código criei a função que ordena com o método Bubble Sort. Podemos assim mandar o vetor como argumento para ser ordenado por nossa função. Para facilitar a visualização do que ocorreu na função eu criei um vetor com valores de 1 a 10 embaralhados e mandei imprimir esses números antes de serem ordenados e depois de serem ordenados.
O algoritmo do bubble sort pode ser desenvolvido usando outras lógicas que no final terão o mesmo resultado. Porém, além deste método existem outros mais eficientes.

MATLAB - Comparação entre Bubble Sort e Shell Sort

Estou compartilhando hoje um trabalho interessante que eu e mais alguns amigos da faculdade desenvolvemos em MATLAB. Não temos aulas dessa linguagem na faculdade, mas nosso professor de programação estruturada sorteou algumas linguagens e pediu que o grupo desenvolvesse um programa de 30 a 50 linhas nessa linguagem.
Ninguém do nosso grupo tinha conhecimentos sobre MATLAB. Tivemos pouco menos de 2 meses para aprender pelo menos um pouco sobre a linguagem por conta própria. Isso tudo com o intuito de nos incentivar a auto aprendizagem.
Inicialmente não sabia oque fazer...
Nesse semestre fizemos alguns estudos simples sobre métodos de ordenação de vetores. Eu gostei do assunto, pesquisei outros métodos e programei alguns deles em C. Isso me incentivou a fazer esse script e ver o tempo que leva para um script em Bubble Sort ser ordenado e essa mesma ordenação em um método mais eficiente, neste caso o Shell sort.
Tanto o Shell Sort quanto o Bubble Sort são algoritmos curtos, por isso estes foram os escolhidos. Ainda assim nosso programa ficou com 52 linhas (não contamos as linhas de comentários).

Créditos a todos os membros do grupo:
Alessandro Araujo Rodrigues;
Erick Rondinone Chalegre;
Gean Miguel Falcão Dos Anjos;
George Henrique Wurthmann;
Leandro Carvalho Nogueira;

DESCRIÇÃO DO PROGRAMA
Programa desenvolvido com MATLAB para analisar o desempenho do método de organização de dados Bubble sort e também do método Shell sort, os dados do vetor foram lidos a partir de arquivo (planilha do excel). Ao fim da organização é apresentado um gráfico comparativo entre os dois métodos. Em um deles é apresentado a quantidade de iterações realizadas para se fazer a ordenação e no outro é apresentado o tempo em milissegundos utilizado para se fazer toda a ordenação.
Para a realização desses testes foram utilizados 2000 (dois mil) números aleatórios que estão armazenados em um arquivo do Excel (ordenar.xlsx). Esses números foram gerados aleatoriamente através do Excel com auxilio das funções rand e int. Para comprovar a funcionalidade do programa, esse script ainda escreve nesse mesmo arquivo do Excel (ordenar.xlsx) os números ordenados, tanto do bubble sort quanto do shell sort.

PROGRAMA

%%%%% %%%%% %%%%%BUBBLE SORT %%%%% %%%%% %%%%%
        importdata('ordenar.xlsx');
        input('Números a serem ordenados: ');
        disp(xlsread('ordenar.xlsx','B1:B2000'))
        x = [xlsread('ordenar.xlsx','B1:B2000')]; n = length(x); iterations_bs = 0;
        time_aux1 = float('single'); time_aux1 = clock;
        for(i2 = 1:n-1)
            troca = 0;
            for(j2 = 1:n-i2)
             if(x(j2) > x(j2+1))
                 aux = x(j2);
                 x(j2) = x(j2 + 1);
                 x(j2 + 1) = aux;
                 troca = 1;
             end
             iterations_bs = iterations_bs + 1;
         end
         if(troca == 0)
             break;
         end
     end
     time_aux2 = float('single');time_aux2 = clock;
     time_bs = float('single'); time_bs = ((time_aux2(5)- time_aux1(5))*60)+(time_aux2(6)- time_aux1(6));
     input('Ordenação Bubble sort:');
     disp(x)
     xlswrite('ordenar.xlsx',x,'E1:E2000');
     %%%%% %%%%% %%%%%SHELL SORT %%%%% %%%%% %%%%%
     input('Ordenação Shell sort:');
     x = [xlsread('ordenar.xlsx','B1:B2000')]; iterations_ss = 0; time_aux1 = clock;
     inc = cast(n/2,'int16');
     while(inc>0)
       for(i2=inc+1:n)
         aux = x(i2);
         j2 = i2;
         while(j2>inc && x(j2-inc)>aux)
     x(j2) = x(j2-inc);
           j2 = j2-inc;
           iterations_ss = iterations_ss + 1;
         end
         x(j2) = aux;
         iterations_ss = iterations_ss + 1;
       end
       inc = cast(floor(double(inc) /2),'int16');
     end
     time_aux2 = clock;
     time_ss = float('single'); time_ss = ((time_aux2(5)- time_aux1(5))*60)+(time_aux2(6)- time_aux1(6));
     disp(x)
     xlswrite('ordenar.xlsx',x,'H1:H2000');
     %%%%%%%Comparação entre os modos de ordenação%%%%%%%
     graph = [iterations_bs iterations_ss];
     graphtime = float('single'); graphtime = [time_bs time_ss];
     input('Bubble sort: Quantidade de iterações: '); disp(iterations_bs);
     input('Bubble sort: Tempo em segundos: '); disp(time_bs);
     input('Shell sort: Quantidade de iterações: '); disp(iterations_ss);
     input('Shell sort: Tempo em milisegundos: '); disp(time_ss);

EXPLICAÇÃO DO CÓDIGO 
Linha 1: Comentário para separação do método Bubble_Sort.
Linha 2: Importa os dados do arquivo “ordenar.xlsx”.
Linha 3: Informa a seguinte mensagem na tela: “Números a serem ordenados”.
Linha 4: Mostra o que o sistema leu entre as células B1 à B2000.
Linha 5: Atribui ao vetor “x” os dados de B1 à B2000, e em “n”atribuímos o tamanho do vetor “x” (2000 posições) e iniciamos a variável “iterations_bs” com valor zero.
Linha 6: Iniciamos o vetor “time_aux1” como “float” (Real), e atribuímos a mesma os valores relacionados ao relógio do computador local (Função Clock), sendo este o momento em que a ordenação se iniciou. Obs.: A função clock armazena em um vetor de 6 posições, sendo elas para: ano, mês, dia, horas, minutos, segundos.
Linha 7: Iniciamos uma repetição que ira de 1 (i2) até 1999 (n-1). Essa repetição percorrerá o vetor “x”.
Linha 8: Iniciamos a variável troca com o valor zero.
Linha 9: Repetição que irá de 1 até n-i2. Como “n” decrementa o valor de “i2” a cada repetição a posição até qual se percorrerá será diminuída em um.
Linha 10: Condição para trocar/Não Trocar.
Linha 11 à 13: É utilizada a variável “aux”, para inverter os valores de posição caso a condição seja verdadeira (Linha 10).
Linha 14: Atribui a variável “troca” o valor 1 (um). Obs.: Essa variável é utilizada para verificar se houve alguma troca durante o laço.
Linha 15: Fechamento do bloco “if”.
Linha 16: Incrementa a variável “iterations_bs” em 1 (um).
Linha 17: Fechamento do bloco “for”.
Linha 18 à 20: Se não houver troca, interrompe o laço.
Linha 21:Fechamento do bloco “for”.
Linha 22:Iniciamos o vetor “time_aux2” como float (Real), e atribuímos a mesma os valores relacionados ao relógio do computador local (Função Clock), sendo este o momento em que a ordenação se finalizou. Obs.: A função clock armazena em um vetor de 6 posições, sendo elas para: ano, mês, dia, horas, minutos, segundos.
Linha 23:Atribui a variável “time_bs” o calculo do tempo de execução. (time_aux2 - time_aux1). No calculo usamos apenas as posições 5 e 6, que são, respectivamente, referentes a minutos e segundos. Linha 24:Informa a seguinte mensagem na tela: “Ordenação Bubble sort”.
Linha 25: Mostra o vetor “x” já ordenado.
Linha 26: Escreve no arquivo “ordenar.xlsx” o vetor “x” de E1 à E2000.
Linha 27: Comentário para separação do método Shell Sort.
Linha 28: Informa a seguinte mensagem na tela “Ordenação Shell sort”.
Linha 29: Atribui ao vetor “x” novamente os valores desordenados (B1 à B2000),iniciamos a variável “iterations_ss” com valor 0 (zero) e atribuímos a “time_aux1” os valores relacionados ao relógio do computador local (Função Clock),sendo este o momento em que a ordenação se iniciou.
Linha 30: Atribuímos a variável “inc” o valor de (n/2) e com a função cast convertemos o numero para inteiro.
Linha 31: Repetir enquanto “inc” for maior que 0 (zero).
Linha 32:Repetir de “inc+1” até “n”.
Linha 33: A variável “aux” recebe o valor do vetor x(i2) para caso seja realizada a troca posteriormente.
Linha 34: Atribui a variável “j2” o valor de “i2” (como não podemos mudar o valor de “i2”, pois é um contador, passamos o valor para “j2” para podermos manipula-lo).
Linha 35 à 37: Enquanto as condições forem verdadeiras, sãoinvertidas as posições dos valores do vetor (Iniciado a troca).
Linha 38: Incrementa a variável “iterations_ss” em 1 (um).
Linha 39: Fechamento do bloco “while”.
Linha 40: Finalizando a troca das posições do vetor.
Linha 41: Incrementa a variável “iterations_ss” em 1 (um).
Linha 42: Fechamento do bloco “for”.
Linha 43: Atribuímos a variável “inc” o valor de (n/2) e com a função cast convertemos o numero para inteiro. A função “floor” arredonda para menos e a função “double” aumenta a precisão para evitar arredondamentos errôneos.
Linha 44: Fechamento do bloco “while”.
Linha 45: Atribuímos ao “time_aux2” os valores relacionados ao relógio do computador local (Função Clock), sendo este o momento em que a ordenação se finalizou.
Linha 46: Inicia-se a variável time_ss como “float” (Real) e atribui a estao valordo calculo do tempo de execução. (time_aux2 - time_aux1).
Linha 47: Mostra os valores do vetor “x” (Números ordenados).
Linha 48: Escreve no arquivo “ordenar.xlsx” o vetor “x” ordenado, de H1 à H2000.
Linha 49: Comentário para separação da parte onde fazemos as comparações.
Linha 50: Armazena no vetor “graph” o valor “iterations_bs” e “iterations_ss”. Vetor de 2 (duas) posições.
Linha 51: O vetor “graphtime” é iniciado como “float” (Real). Atribuindo a esta o valor de “time_bs” e “time_ss”. Vetor de 2 (duas) posições.
Linha 52 à 55: Mostra ao usuário os resultados da comparação (Quantidade de iterações e Tempo de execução de cada um).

IMAGENS DO PROGRAMA

Figura 1.0 A imagem acima representa a tela inicial do programa, onde é apresentado para o usuário os números na ordem atual (os números a serem ordenados).

Figura 1.1A imagem acima representa a ordenação feita pelo método Bubble sort.

Figura 1.2A imagem acima representa a ordenação feita pelo método Shell sort.

Figura 1.3A imagem acima apresenta a tela do programa que mostra ao usuário a quantidade de iterações e o tempo em milissegundo de cada um dos métodos utilizados em nosso programa (Bubble sort e Shell sort).

Figura 1.4 Ao lado podemos observar a “Workspace” do MATLAB, onde são mostradas as variáveis utilizadas em nosso programa.

Quatro dessas variáveis foram utilizadas para gerar um gráfico de comparação entre os 2 métodos que utilizamos em nosso programa. São elas:  iterations_bs, iterations_ss, time_bs e time_ss.

Os gráficos devem ser gerados a partir de vetores ou matrizes, então armazenamos no vetor graph as variáveis iterations_bs e iterations_ss e no vetor graphtime as variáveis time_bs e time_ss.

Através desses vetores geramos os dois gráficos de comparação através do botão contornado de vermelho (Select data to plot).

Figura 1.5 A imagem acima mostra o gráfico que compara a quantidade de iterações realizadas pelo Bubble sort (coluna esquerda) e a quantidade de iterações realizadas pelo Shell sort (coluna direita).

Figura 1.6 A imagem acima mostra o gráfico que compara o tempo em que foi feita a ordenação pelo Bubble sort (coluna esquerda) e o tempo em que foi feita a ordenação pelo Shell sort (coluna direita).

Figura 1.7 A imagem acima mostra o arquivo do Excel (ordenar.xlsx) onde geramos os números aleatórios utilizados em nosso programa. Tanto para o Bubble Sort quanto para o Shell Sort foram utilizados exatamente os mesmos números, que são os números que estão de B1 à B2000.

Figura 1.8:A imagem acima mostra o arquivo do Excel (ordenar.xlsx) com os números já ordenados, sendo a coluna E referente ao Bubble Sort e a coluna H referente ao Shell Sort. Podemos observar que o resultado é exatamente o mesmo, pois, como explicado anteriormente, as ordenações foram realizadas com os mesmos números para os dois métodos.

COMENTÁRIOS SOBRE A LINGUAGEM DE PROGRAMAÇÃO UTILIZADA

MATLAB é uma linguagem de programação muito poderosa. É claro que durante nossa pequena pesquisa não utilizamos todo seu poder, mas conseguimos observar bem isso através de sua biblioteca de funções. Existe uma quantidade enorme de comandos para os mais diversos usos.

Deparamo-nos com muito conteúdo para engenharia e matemática. Em nossas pesquisas observamos que engenheiros e matemáticos utilizam o MATLAB como ferramenta de pesquisa. Criam através dele modelos matemáticos ou simbólicos (gráficos) para auxiliar em seus projetos. E ainda é possível utiliza-lo para pesquisas cientificas, pois é de grande facilidade trabalhar com fórmulas no MATLAB e com grande velocidade. Além de tudo isso é possível utilizar os conceitos de orientação a objeto, criar funções, gráficos, trabalhar com som, etc.

Encontramos alguns vídeos bem explicados, entre eles, um dos que nos mais ajudou a entender a linguagem foram os próprios vídeos disponíveis no portal do MATLAB (http://www.mathworks.com/products/matlab/examples.html).

BIBLIOGRAFIA

CELES, Waldemar. CERQUEIRA, Renato. RANGEL, José Lucas. Introdução a Estruturas de Dados. 2004, Elsevier Editora.

http://das.ufsc.br/~nestor/cursos/matlab/matlab/matlab.html. Acesso em 19/10/2012 ás 15h22min.

http://www2.dcc.ufmg.br/disciplinas/aeds2_turmaA1/bubblesort.pdf. Acesso em 24/10/2012 ás 11h17min.

http://www.del.ufms.br/tutoriais/matlab/apresentacao.htm.Acesso em 24/10/2012 ás 11h40min.

http://www.ic.uff.br/~aconci/GuiaMatLab.pdf. Acesso em 24/10/2012 ás 09h32min.

http://www.mathworks.com/products/matlab/examples.html. Acesso em 25/10/2012 ás 12h09min.

http://www2.peq.coppe.ufrj.br/Pessoal/Professores/Arge/COQ897/Matlab/matlab.pdf. Acesso em 25/10/2012 ás 14h05min.

http://www.slideshare.net/ander-san/trabalho-shell-sort. Acesso em 19/10/2012 ás 11h16min.

http://www.youtube.com/playlist?list=PL4D57B6012FE85563. Acesso em 24/10/2012 ás 10h27min.

http://www.youtube.com/watch?v=CmPA7zE8mx0&feature=relmfu. Acesso em 19/10/2012 ás 10h03min.

http://www.youtube.com/watch?v=M3bS6w1R434. Acesso em 19/10/2012 ás 09h51min.