• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Gurzi

Bubble Sort

26 mensagens neste tópico

Alguem me consegue dar uma explicação matemática para o Bubble Sort ??'

Já li vários tutoriais mas não consigo perceber a parte matemática da cena.

E porque lhe chamam Bubble Sort ? Que é que isso tem a ver com bolhas ??

Um abraço

ps: no algoritmo falam em elementos adjacentes, o que é isso ? =D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Elementos adjacentes será algo como índice 0 e índice 1. Para ordenar uma string de caracteres, o algoritmo funciona da seguinte forma:

1. Percorre a string,

2. valida se o elemento[ i ] é superior ao elemento.

3. Caso elemento[ i ] seja superior ao elemento, ele troca-os, passando o valor de elemento ficar na posição do valor elemento[ i ] e vice versa.

4. Voltar ao passo número 1.

É muito simples, talvez dos algoritmos de ordenação mais simples.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A lógica por traz do bubblesort é por cada ciclo por o MAIOR elemento no fim da lista.

Por esse motivo tens de se no máximo percorrer (n-1) vezes o ciclo, sendo n o número de elementos numa lista.

Também por optimização pode-se percorrer a lista cada vez menos até ao fim, porque já se sabe que a parte final da lista já irá estar ordenada.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nunca tinha implementado este algoritmo em C, uma vez que a libc já trás o bsort() por natureza e já não programava em C há prai 2-3 anos. Foi um desafio porreiro, deu para vibrar :-)

#include <stdio.h>

int *bsort(int sort[], int n)
{
        int *p;
        int cont = 1;
        int i;

        p = malloc(n*sizeof(int));
        if (!p) {
                fprintf(stderr, "Out of Memory!\n");
                return NULL;
        }

        memset(p, 0, n*sizeof(int));
        memcpy(p, sort, n*sizeof(int));

        for (i = 0; i < (n - 1); i++) {
                if (p[i] >  p[i + 1])
                        p[i] ^= p[i + 1] ^= p[i] ^= p[i + 1];
        }

        return p;
}

int main(int argc, char **argv)
{
        int num[] = { 1, 3, 33, 5, 7, 9, 3300, 44 };
        int *p, i;

        p = bsort(num, sizeof(num)/sizeof(int));

        if (p) {
                for (i = 0; i < sizeof(num)/sizeof(int); i++)
                        printf("%d\n", p[i]);
                free(p);
        }
        return 0;
}

# ./a.out

1

3

5

7

9

33

44

3300

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

        do {
                for (i = 0; i < (n - 1); i++) {
                        if (p[i] >  p[i + 1])
                                p[i] ^= p[i + 1] ^= p[i] ^= p[i + 1];
                }
                cont = 0;

        } while (cont);

Para que é o do/while se tens o count=0 imediatamente antes de testar a condição?

O algoritmo não está a funcionar...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

        do {
                for (i = 0; i < (n - 1); i++) {
                        if (p[i] >  p[i + 1])
                                p[i] ^= p[i + 1] ^= p[i] ^= p[i + 1];
                }
                cont = 0;

        } while (cont);

Para que é o do/while se tens o count=0 imediatamente antes de testar a condição?

O algoritmo não está a funcionar...

A versão que colei, foi a 1ª que comecei a fazer e que estava no clipboard. Daí ter editado e retirado o while. :-)

Já agora, não está a funcionar? É que a tua critica foi tudo menos construtiva, o que se esperava de um moderador :-)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mesmo a nova versão também não funciona. Até porque só tens um ciclo e parece-me que precisavas de dois aninhados para implementar o algoritmo...

Não olhei para o algoritmo com grande atenção, apenas o testei, pois achei estranho que funcionasse sem dois ciclos. Daí o comentário pouco construtivo ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens razão, está ali um erro de implementação!

Vou corrigir.. devia ter testado melhor (a 1ª  e única vez que implementei foi em 98 em pascal)

Obrigado!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Corrigido! Afinal quando pus o do...while estava a ir no caminho certo, mas como testei e funcionou sem ele, assumi logo que nem era necessário, enfim... :-)

#include <stdio.h>

int *bsort(int sort[], int n)
{
        int *p;
        int i;
        int v = n;
        int cont;

        p = malloc(n*sizeof(int));
        if (!p) {
                fprintf(stderr, "Out of Memory!\n");
                return NULL;
        }

        memset(p, 0, n*sizeof(int));
        memcpy(p, sort, n*sizeof(int));

        do {
                cont = 0;
                v--;

                for (i = 0; i < v; i++)
                        if (p[i] >  p[i + 1]) {
                                p[i] ^= p[i + 1] ^= p[i] ^= p[i + 1];
                                cont = 1;
                        }


        } while(cont);

        return p;
}

int main(int argc, char **argv)
{
        int num[] = { 554, 0xff, 1, 3, 33, 5, 7, 9, 3300, 44 };
        int *p, i;

        p = bsort(num, sizeof(num)/sizeof(int));

        if (p) {
                for (i = 0; i < sizeof(num)/sizeof(int); i++)
                        printf("%d\n", p[i]);
                free(p);
        }
        return 0;
}

# ./a.out

1

3

5

7

9

33

44

255

554

3300

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso continua a dar problemas...

Acho que o problema está na forma como fazes o swap.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso continua a dar problemas...

Acho que o problema está na forma como fazes o swap.

Isto está um bocado estranho... Começo a achar que descobri um bug no compilador ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

tás num x86 ou x86_64?

P.S fiz esta alteração e acho que a última versão que postei acima está 100% correcta.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int *bsort(int sort[], int n)
{
        int *p;
        int i;
        int v = n;
        int cont;

        p = malloc(n*sizeof(int));
        if (!p) {
                fprintf(stderr, "Out of Memory!\n");
                return NULL;
        }

        memset(p, 0, n*sizeof(int));
        memcpy(p, sort, n*sizeof(int));

        do {
                cont = 0;
                v--;

                for (i = 0; i < v; i++)
                        if (p[i] >  p[i + 1]) {
                                p[i] ^= p[i + 1] ^= p[i] ^= p[i + 1];
                                cont = 1;
                        }


        } while(cont);

        return p;
}

int main(int argc, char **argv)
{
        int num[10];
        int *p, i;

        srand(time(NULL));

        for (i = 0; i < 10; i++)
                printf("%d, ", num[i] = rand()%100);
        printf("\n");

        p = bsort(num, sizeof(num)/sizeof(int));

        if (p) {
                for (i = 0; i < sizeof(num)/sizeof(int); i++)
                        printf("%d\n", p[i]);
                free(p);
        }
        return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso continua a dar problemas...

Acho que o problema está na forma como fazes o swap.

Isto está um bocado estranho... Começo a achar que descobri um bug no compilador ;)

Duvido que seja problema do programa; vide:

# valgrind --tool=memcheck --leak-check=yes ./sort

==20940== Memcheck, a memory error detector for x86-linux.

==20940== Copyright © 2002-2004, and GNU GPL'd, by Julian Seward et al.

==20940== Using valgrind-2.2.0, a program supervision framework for x86-linux.

==20940== Copyright © 2000-2004, and GNU GPL'd, by Julian Seward et al.

==20940== For more details, rerun with: -v

==20940==

12, 70, 24, 48, 44, 49, 32, 33, 75, 41,

12

24

32

33

41

44

48

49

70

75

==20940==

==20940== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 12 from 1)

==20940== malloc/free: in use at exit: 0 bytes in 0 blocks.

==20940== malloc/free: 1 allocs, 1 frees, 40 bytes allocated.

==20940== For counts of detected errors, rerun with: -v

==20940== No malloc'd blocks -- no leaks are possible.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Deve ser alguma optimização do compilador. Quando executa aquela parte do swap, o primeiro elemento passa a 0. Isto se estiver tudo numa linha, se separar em várias já funciona.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

De certeza que tem haver com os data types definidos (casting fsckups) ou as operações bitwise geradas a baixo nível

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Depois quando quiseres um algoritmo de ordenação mais rápido -> O( N log N ) , podes fazer simplesmente:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp( const void * a , const void * b ) {    return *(int * ) a - *(int *) b;       }

int * ordena_quicksort(int sort[], int n)
{
        int *p = malloc(n*sizeof(int));

        if (!p) {
                fprintf(stderr, "Out of Memory!\n");
                return NULL;
        }
        memcpy(p, sort, n*sizeof(int));

        qsort( p , n , sizeof(int) , cmp );

        return p;
}

ou em C++

#include <algorithm>
#include <string.h>
int * ordena_quicksort(int sort[], int n)
{
        int *p = new int[n];

        if (!p) {
                fprintf(stderr, "Out of Memory!\n");
                return NULL;
        }
        memcpy(p, sort, n*sizeof(int));

        std::sort( p , p + n );  // senao usarmos  "using namespace std"

        return p;
}

Não sei se conheciam...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já existe a função qsort (assim como a mergesort e heapsort) na stdlib.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Depois quando quiseres um algoritmo de ordenação mais rápido -> O( N log N ) , podes fazer simplesmente:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp( const void * a , const void * b ) {    return *(int * ) a - *(int *) b;       }

int * ordena_quicksort(int sort[], int n)
{
        int *p = malloc(n*sizeof(int));

        if (!p) {
                fprintf(stderr, "Out of Memory!\n");
                return NULL;
        }
        memcpy(p, sort, n*sizeof(int));

        qsort( p , n , sizeof(int) , cmp );

        return p;
}

ou em C++

#include <algorithm>
#include <string.h>
int * ordena_quicksort(int sort[], int n)
{
        int *p = new int[n];

        if (!p) {
                fprintf(stderr, "Out of Memory!\n");
                return NULL;
        }
        memcpy(p, sort, n*sizeof(int));

        std::sort( p , p + n );  // senao usarmos  "using namespace std"

        return p;
}

Não sei se conheciam...

Terias sido mais "on topic", se tivesses dissecado a implementação do quicksort como alternativa ao bubble. 

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já existe a função qsort (assim como a mergesort e heapsort) na stdlib.

e bsort() :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens razão. Na pratica como uso estas funções, já não sei de cor a implementação do quicksort.. mas posso por uns links

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já existe a função qsort (assim como a mergesort e heapsort) na stdlib.

e bsort() :P

Nem sempre, penso que a bsort não é muito frequente encontrar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

À partida, o sort() da STL pode até ser mais rápido que o qsort(), já que usa quicksort e heapsort conjuntamente, num algoritmo com o nome de introsort. A ordenação é iniciada com quicksort, mas chegado a um determinado nível de profunidade na recursão, passa-se a usar o heapsort, evitando por isso os problemas que por vezes podem surgir de uma má escolha do pivot. No pior caso, o introsort tem uma ordem de complexidade O(n log n), significativamente melhor que O(n^2) no pior caso do quicksort.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora