Bubble Sort

Hoje resolvi brincar um pouco com este algortimo de ordenação tão famoso, o Bubble Sort.

A idéia deste algoritmo é fazer ir trocando os caracteres de modo que eles “flutuem” como bolhas. Os valores maiores, vão subindo à cada passagem do loop. De maneira metafórica, é como se fossem bolhas, dái o nome Bubble.

O algoritmo é bem simples e existem diversas implementações no wikipedia, para diversas linguagens http://pt.wikipedia.org/wiki/Bubble_sort

Eu resolvi brincar um pouco com C/C++ para ele. Vejam o caso mais simples, ordenação de inteiros:

#include <iostream>

using namespace std;

void print( int numbers[], int size )
{
    int i = 0;

    for( int i = 0; i < size; i++ )
    {
        cout << numbers[ i ] << " ";
    }

    cout << endl;
}

O algoritmo tradicionado do Bubble sort para uma lista de números:

void bubble()
{
    int numbers[] = { 0, 1, 4, 7, 2, 9, 3 };

    int size = sizeof( numbers ) / sizeof( int );
    int temp;
    int steps = 0;

    cout << "Unordered list: ";
    print( numbers, size );

    for( int i = 0; i < size; i++ )
    {
        for( int x = size - 1; x > i ; x-- )
        {
            steps++;

            if( numbers[ x ] < numbers[ x - 1 ])
            {
                temp = numbers[ x ];
                numbers[ x ] = numbers[ x – 1 ];
                numbers[ x - 1 ] = temp;
            }
        }
    }

    cout << "Ordered list: ";
    print( numbers, size );
    cout << "Steps: " << steps << endl;
}

O que temos aqui são dois loops que vão ao encontro um do outro para evitar passagens desnecessárias pelo array já que os menores valores já ficam posicionados ordenamente nas primeiras passagens.

O resultado é:

Unordered list: 0 1 4 7 2 9 3
Ordered list: 0 1 2 3 4 7 9
Steps: 21
Press any key to continue . . .

Agora vem um outro caso onde resolvi usar este algoritmo para ordenação: nomes.
Para deixar a brincadeira mais interessante, resolvi utilizar a minha própria implementação da strlen.

int strlen_x( char* word )
{
    int size = 0;

    if( word )
    {
        while( word[ size++ ] );
    }

    return size;
}
Uma maneira bem simples de obter o tamanho de uma string do C.
Agora uma função simples para imprimir a lista de nomes:
 
void printNames( char* names[], int size )
{
    for( int i = 0; i < size; i++ )
    {
        cout << names[ i ] << " ";
    }

    cout << endl;
}
A função de troca para reaproveitamento de código:
 
void swap( char* names[], int indexA, int indexB )
{
    char* temp = names[ indexA ];
    names[ indexA ] = names[ indexB ];
    names[ indexB ] = temp;
}
 
E a função do bubble adequado para palavras e não apenas inteiros ou caracteres:
 
void sortNames()
{
    char* names[] = { "bill", "steve", "paul", "aaron", "beth", 
"abner", "phil", "john", "mary", "felix", "carl", "tom",
"malcomn", "isabel" };

int steps = 0; int wordSize1, wordSize2; int size = 14; //número mágico cout << "Unodered names: "; printNames( names, size ); for( int i = 0; i < size; i++ ) { for( int x = size - 1; x > i ; x-- ) { if(names[ x ][ 0 ] != names[ x – 1 ][ 0 ] ) { steps++; if(names[ x ][ 0 ] < names[ x – 1 ][ 0 ] ) { steps++; swap( names, x, x - 1 ); } continue; } wordSize1 = strlen_x( names[ x - 1] ); wordSize2 = strlen_x( names[ x ] ); if( wordSize2 < wordSize1 ) { wordSize1 = wordSize2; } for( int w = 1; w < wordSize1 ; w++ ) { steps++; if(names[ x ][ w-1 ] == names[ x - 1][ w-1 ] ) { if(names[ x ][ w ] < names[ x – 1 ][ w ] ) { steps++; swap(names, x, x - 1 ); break; } } else { break; } } } } cout << "Ordered names: "; printNames( names, size ); cout << "Steps: " << steps << endl; }
O resultado é:

Unodered names: bill steve paul aaron beth abner phil john mary felix carl tom malcomn isabel
Ordered names: aaron abner beth bill carl felix isabel john malcomn mary paul phil steve tom
Steps: 146
Press any key to continue . . .

Qual é a diferença?
Ao invés de ter que se preocupar em ordenar N valores, é necessário se preocupar em ordenar N conjuntos de valores sequenciais. Essa sequência é importante para a ordenação final.

Neste caso consideramos a sequência de caracteres quando os nomes iniciam com a mesma letra, neste caso é necessária uma verificação caracter por caracter levando em consideração um caso especial de nomes que podem ter as duas primeiras letras iguais como Aaron.

Se as iniciais são diferentes, o processo é o bubble sort tradicional.

É isso aí pessoal! Divirtam-se Open-mouthed smile

Anúncios


Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s