Pesquisar no blog:

Mostrando postagens com marcador Vetor. Mostrar todas as postagens
Mostrando postagens com marcador Vetor. Mostrar todas as postagens

segunda-feira, 22 de junho de 2015

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.

domingo, 21 de junho de 2015

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



sábado, 20 de junho de 2015

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

sexta-feira, 19 de junho de 2015

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.

quinta-feira, 27 de junho de 2013

Linguagem C: Manipulação de Strings

A linguagem C nos permite manipular um vetor de caracteres que, em outras linguagens, são chamados de Strings. Então, podemos afirmar que a linguagem C também existe esse tipo de dado. Sendo assim, há na linguagem C diversas funções que nos auxiliam a manipular as Strings, evitando a necessidade do uso de grande quantidade de linhas de códigos.
Sendo assim, há na linguagem C diversas funções que nos auxiliam a manipular as Strings, evitando a necessidade do uso de grande quantidade de linhas de códigos.

FUNÇÃO STRLEN

A função strlen é acrônimo de String Length, e como o próprio nome sugere usamos essa função para encontrar o tamanho de uma string, ou seja, a quantidade de caracteres.
A função strlen retorna um valor inteiro referente à quantidade de caracteres da função. Essa contagem é feita passando caractere por caractere da string até chegarmos ao caractere ‘\0’ que, na linguagem C, é o nulo (NULL). É importante sabermos que todas as strings são terminadas com nulo, ou seja, enquanto o caractere nulo (‘\0’) não for encontrado é incrementado 1 (um) ao contador e é passado para o próximo caractere.
A função strlen tem várias aplicações, podemos usar como exemplo a necessidade de contar a quantidade de caracteres para verificar se o usuário informou corretamente um documento como o CPF que tem sempre 11 (onze) caracteres. Chamada da função: strlen(vetor); que o usuárioeja contar. Para melhor entendimento veja a aplicação da função strlen:
main()
{
    char *teste = "Manipulaçao de Strings";
    int tam = strlen(teste);
    printf("%d\n",tam);
    getch();
}

Esse programa conta a quantidade de caracteres de teste e imprime na tela 22.
Abaixo vemos uma função com o mesmo funcionamento da função strlen:
int tamstr(char *str)
{
    int i = 0;
    while(*(str+i) != '\0') i++; 
    return i; 
}

FUNÇÃO STRCAT

main()
{
    char teste[] = "Manipulacao de Strings", teste2[] = " - strcat";
    printf("%x\n", teste);
    strcat(teste,teste2);
    puts(teste);
    getch();
}

No programa acima concatenamos a string “teste” com a string teste2 informando a função “strcat(teste,teste2);”. A concatenação é feita no primeiro vetor (teste = “Manipulacao de Strings - strcat”) e o segundo vetor permanece com o mesmo conteúdo (teste2 = “- strcat”).

FUNÇÃO STRCMP

A função strcmp é acrônimo de String Comparison, e como o próprio nome sugere usamos essa função para comparar duas strings. A função STRCMP compara as strings, e devolve apenas 2 valores, 0 caso forem iguais (verdadeiro), um valor maior que zero que as strings não são iguais e que o primeiro caractere que não é igual entre elas é maior na primeira string, já um valor abaixo de zero o caractere diferente é maior na segunda string. A comparação termina após a função encontrar o NULO na string ou ao encontrar algum caractere diferente.
Exemplo 1:
main()
{
    char teste[] = "Manipulacao de Strings", teste2[] = "Manipulacao de Strings";
    strc== 0 ? puts("iguais") : puts("Sao diferentes");
 getch();
}
No exemplo acima o retorno é 0, ou seja, as strings são iguais.

Exemplo 2:
main()
{
    char teste[] = "Manipulacao de Strings", teste2[] = "Manipulacao de strings";
    printf("\n\n%d \n\n", strcmp(teste,teste2));
    strcmp(teste,teste2) == 0 ? puts("Sao iguais") : puts("Sao diferentes");
    getch();
}
Observe que a letra 's' de uma das string está em maiúsculo e da outra em minusculo. Sendo assim, nesse segundo exemplo o retorno é -1, por que S < s, que equivalem a a 83 e 115 na tabela ASCII respectivamente.

FUNÇÃO STRCPY

A função strcpy é acrônimo de String Copy, e como o próprio nome sugere usamos essa função para copiar o conteúdo de uma string para outra. A função pode vir a ser muito útil podendo copiar todo o conteúdo de uma string para a outra, ou podemos também copiar strings a partir de posições específicas, mas deve-se estar atento em seu tring é copiadra outro lugar, esta pode se sobrepor em outra, ou pode não ter espaço suficiente para esta, o que pode acabar ocorrendo um comportamento não definido. Em seguida veja um exemplo de seu uso:
main()
{
    char teste[] = "Manipulacao de Strings", teste2[] = "strcpy - ";
    strcpy(&teste2[9],&teste[15]);
    puts(teste2);
    getch();
}

Neste programa a string teste está sendo copiada para a string teste2, no entanto está sendo indicado de qual posição isso deve ser feito, então, observe que está sendo copiado de teste2 todo o conteúdo a partir da posição 15 para a string teste a partir da posição 9, logo o resultado deste programa é “strcpy – Strings”.

FUNÇÃO TOLOWER

A função tolower pa uma string uum para minúsculo desde que este pertença as letras de A-Z.
A função retorna o caractere convertido para minúsculo. Essa função pode ser usada para padronizar os dados de um programa tornando qualquer caractere maiúsculo digitado pelo usuário em um caractere minúsculo. Exemplo:
main()
{
    char teste[] = "MANIPULACAO DE STRINGS";
    int i;
    puts(teseste[i] != '\0+)
        putchar(tolower(teste[i])); 
    getch();
}

A saída desse programa será: manipulação de strings.
A implementação dessa função é simples e se faz com o auxílio da tabela ASCII:
char Mtom(char st){
    if((st >= 65)&&(st <= 90)){
        return(st + 32);
    return(st);
    }
}

FUNÇÃO STRLWR

Além da função tolower, existe outra função com o objetivo semelhante. A função strring inteira nvés de fazer caractere por caractere.
Exemplo:
main()
{
    char str[] = "MANIPULACAO DE STRINGS!";
    strlwr(str);
    puts(str);
    getch();
    return 0;
}

A saída será "manipulacao de strings!".

FUNÇÃO TOUPPER

A função toupper passa caracteres de uma string um a um para maiúsculo desde que este pertença as letras de a-z.
A função retorna o caractere convertido para maiúsculo. Essa função pode ser usada para padronizar os dados de um programa tornando qualquer caractere minúsculo digitado pelo usuário em um caractere maiúsculo. Exemplo:
main()
{
    char teste[] = "manipulacao de strings";
    int i;
    puts(teste);
    for(i=0;teste[i] != '\0';i++)
        putchar(tolower(teste[i])); 
    getch();
}

FUNÇÃO STRUPR

Além da função toupper, existe outra função com o objetivo semelhante. A função strupr converte a string inteira para maiúsculo ao invés de fazer caractere por caractere.
Exemplo:
main()
{
    char str[] = "manipulacao de strings!";
    strupr(str);
    puts(str);
    getch();
    return 0;
}

A saída será "MANIPULACAO DE STRINGS!".

FUNÇÃO STRSTR

strstr(string1, string2);
A função strstr deve ser chamada com 2 parâmetros do tipo string, e procura a primeira ocorrência de string1 em string2. Se não for encontrado é retornado NULL e se encontrado é retornado um ponteiro apontando para a primeira ocorrência de string2 em string1.
Exemplo:
#include 
main()
{
    char str1[] = "strings", str2[] = "Manipulacao de strings!";
    if(strstr(str2, str1) == NULL)
        printf("Nao ha ocorrencia.\n");
    else
        printf("Endereco HEX: %x\n",strstr(str2, str1));
    getch();
    return 0;
}

segunda-feira, 7 de janeiro de 2013

Ponteiros - Linguagem C

Ponteiros são variáveis que permitem que você acesse outras variáveis sem referência-las diretamente.
Como o nome sugere, seu objetivo é apontar para uma variável. Mais especificamente para o endereço onde a variável apontada se encontra.
Os ponteiros dão a linguagem C grandes possibilidades para manipular endereços de memória e é representado por um asterisco (*) antes do nome da variável. Exemplo: *var

Como funcionam os ponteiros?
Exemplo: temos a variável x = 5 e a variável ponteiro *y = &x.
A variável x é uma variável comum com o valor 5 armazenado. Já a variável *y esta apontando para o endereço da variável x (&x).
O operador "&" na frente de uma variável sempre retornará seu endereço de memória, por isso que ao ler uma variável com a função "scanf" utilizamos as variáveis com este sinal na frente.
Neste caso, então, *y tem o endereço de x. Isso significa que se eu fizer a seguinte operação:
*y = 10
Estarei mudando o valor de x que era 5 para 10.

Exemplo:
main()
{
      int a = 3, b = 7, *pa = &a, *pb = &b, aux;
      printf("a = %d\nb =%d\n",a,b);
      printf("Invertendo...\n");
      system("pause");
      aux = a;
      *pa = b;
      *pb = aux;
      printf("a = %d\nb =%d\n",a,b);
      system("pause");
      return 0;
}

A tabela a seguir representa o conteúdo das variáveis usadas nesse simples programa.
Endereço
Variável
Conteúdo
0x0100
a
3
0x0101
b
7
0x0102
pa
0x0100
0x0103
pb
0x0101
0x0102
*pa
3
0x0103
*pb
7

Observe que o conteúdo dos ponteiros sem o asterisco (*) são endereços.
Mais quando colocamos o asterisco (*) estou indicando que ela deve apontar para o endereço. Então quando informo que *pa = b é a mesma coisa que dizer que o endereço de memória 0x0100 = b ou que a variável a = b.

Como ou quando usar os ponteiros?
Ponteiros são utilizado principalmente em funções, quando há a necessidade de retornar mais valores para o programa principal.
Se você não conhece funções na linguagem C acesse este link.
Sabemos que funções retornam apenas um valor por função. Sabemos também que as variáveis de uma função são destruídas depois que a função é executada. Então a solução para isso é mandar para uma função o endereço da variável que você deseja alterar, assim você estará alterando a variável do programa principal.

Exemplo: função para inverter valores de variáveis.
void troca(int *px, int *py)
{
     int aux;
     aux = *px;
     *px = *py;
     *py = aux;
}

main()
{
      int x = 3, y = 7;
      printf("x = %d\ny =%d\n",x,y);
      printf("Invetendo...\n");
      system("pause");
      troca(&x,&y);
      printf("x = %d\ny =%d\n",x,y);
      system("pause");
      return 0;
}

Na função "troca" foi criado dois ponteiros apontando para os endereços das variáveis do programa principal (x e y) e usando esses ponteiros invertemos os valores das variáveis do programa principal.
Essa inversão é muito utilizada em muitos algoritmos e essa seria uma solução para não precisar repetir essas linhas sempre que precisar inverter variáveis.
As matrizes são ponteiros representados de uma maneira diferente.
Se você não sabe o que são matrizes acesse esse link.
As matrizes são armazenadas em sequencia nas células de memórias. Sabemos que cada célula possui 1 Byte (8 bits), então se tivermos um valor do tipo inteiro armazenado em um ponteiro e somarmos 1 a esse endereço ele irá pular 4 células, ou seja, 4 Bytes onde está armazenado o valor da variável.
Aqui temos um programa que comprova isso:
main()
{
      int i, a[5] = {2000,2001,2002,2003,2004}, *pa = &a;
      for(i = 0; i < 5; i++)
           printf("Endereço atual: %d\nValor: %d\n",&a[i],*pa+i);
      system("pause");
      return 0;
}

Criamos um vetor (a) simples com 5 posições e percorremos ele com um ponteiro (*pa) sendo incrementado por i.
A cada vez que o ponteiro é incrementado é mostrado o endereço do vetor e seu valor, oque comprova que ao incrementar o ponteiro ele pula as 4 células (4 Bytes).
Veja o resultado na imagem abaixo:

quarta-feira, 19 de dezembro de 2012

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.

segunda-feira, 17 de dezembro de 2012

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.

domingo, 16 de dezembro de 2012

Métodos de ordenação de vetores


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.