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

Windows Unicode Strings

Uma das variáveis mais complicadas do desenvolvimento de aplicações em código nativo C/C++ é a quantidade de tipos diferentes para representar Strings.
Basicamente, uma string é uma cadeia de caracteres que pode inicialmente ser representada como

char myString[100] = “Minha string”;

Uma cadeia de “char”, caracteres de 8-bit ANSI

Para o alfabeto americano, 8-bit é suficiente para representar cada caracter, porém outros alfabetos como o Kanji precisam de mais informação para representar alguns caracteres e é aí que nasce o Unicode e os diversos UTFs.

Eis que temos então os caracteres ANSI representados por 1 byte e os conhecidos UTF-8, UTF-16 e UTF-32.

O UTF-8 codifica alguns caracteres utilizando 1 byte, alguns caracteres usando 2, 3 ou 4 bytes. (Loucura não?)
O UTF-16 codifica todos os caracteres utilizando 2 bytes.
O UTF-32 codifica os caracteres utilizando 4 bytes.

O UTF-8 é bastante interessante, porém ele é menos eficiente que o UTF-16 caso existam muitos caracteres que necessitam de 2 bytes ou mais.

As linguagens C/C++ suportam caracteres Unicode e as APIs do Windows também suportam. Existe o tipo wchar_t que é utilizando em C++ para representar caracteres Unicode e é aí que começa a bagunça.

Diversas aplicações mesclam funcões que manipulam caracteres ANSI e UNICODE, o que causa além de um trabalho maior para o desenvolvedor ficar convertendo entre diversos tipos, uma perda de performance e aumento no consumo de memória.

A partir do Windows Vista, a API do Windows utiliza Unicode para tudo, porém as funções da API sempre possuem duas versões, uma versão que ANSI e uma Unicode e dependendo da definição da macro UNICODE, que é definida automaticamente pelo Visual C++.

O tipo TCHAR é um bom exemplo, vejam a declaração simplificada

#ifdef UNICODE
typedef WCHAR TCHAR, *PTCHAR, PTSTR;
#else
typedef CHAR TCHAR, *PTCHAR, PTSTR;
#endif

Se no momento da compilação a macro UNICODE estiver definida o tipo TCHAR representará o WCHAR senão representará o tipo CHAR.
E isto serve para o consumo das funções do Windows que possuem duas versões, por exemplo a função CreateWindowEx:

Versão Unicode (WIDE)
HWND WINAPI CreateWindowExW(…)

Versão ANSI
HWND WINAPI CreateWindowExA(…)

O consumo de versão da função CreateWindowEx é resolvido no momento da compilação devido à esta declaração:

#ifdef UNICODE
#define CreateWindowEx CreateWindowExW
#else
#define CreateWindowEx CreateWindowExA
#endif

Use somente strings UNICODE! 

É importante ter consciência de todos estes detalhes para que ao construir uma aplicação minimize a utilização de caracteres não Unicode.
No Windows, as funções com o sufixo “A” que é a versão Ansi, simplesmente convertem a string passada para a função para uma string Unicode e executam a versão Unicode da função.
Ao término da execução da função Unicode, a função Ansi que a invocou, converte o resultado para uma string Ansi e retorna para a aplicação. Ou seja, ocorre uma sobrecarga de processamento apenas pelas conversões entre tipos.
Strings Ansi proporcionam uma falsa economia de memória, que se perde e pode ter efeito contrário ao passar pela camada de “tradução” da API do Windows.

Outro ponto importante que deve ser levado em consideração para migrar totalmente para strings Unicode é interoperabilidade com aplicações COM e .Net, que também são baseados em Unicode.

Não se preocupe .Net é Unicode!

O .Net framework que possui a classe System.String que simplifica muito a manipulação deste tipo de dado e é Unicode por padrão.
Para o programador .Net (C#/VB/F#/etc) a questão das string é transparente, pois não é necessário manipular ou se preocupar com isto.
Porém toda esta facilidade tem um pequeno porém, toda string no .Net é imutável, ou seja, as manipulações de string com o tipo string padrão do .Net sempre cria cópias das strings e elas são destruídas pelo Gargage Collector. Por isto é preciso ter cuidado e não exagerar nas strings para não desperdiçar a vantagem de trabalhar com o Unicode por padrão.

Para mais informações acesse:

The Unicode Consortium
www.unicode.org

Unicode and Character Sets
http://msdn.microsoft.com/en-us/library/dd374083(VS.85).aspx

Unicode in Visual C++ 2
http://msdn.microsoft.com/en-us/library/cc194799.aspx

How to: Convert between varios string types
http://msdn.microsoft.com/en-us/library/ms235631(VS.80).aspx

Divirtam-se!