Bubble Sort

[Gurzi]

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

[garmg]

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.

[Betovsky]

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.

[garmg]

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

[Rui Carlos]

        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...

[garmg]

        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 :-)

[Rui Carlos]

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 😉

[garmg]

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!

[garmg]

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

[Rui Carlos]

Isso continua a dar problemas...

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

[Rui Carlos]

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 😉

[garmg]

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

[Rui Carlos]

tás num x86 ou x86_64?

Num PowerPC 😉

[garmg]

ppc32 ou ppc64?

[djthyrax]

32.

[garmg]

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.

[Rui Carlos]

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.

[garmg]

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

[mogers]

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...

[Rui Carlos]

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