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

Semana de Webcasts do Internet Explorer 9

A terceira semana de março de 2011 está sendo a semana de lançamento do Internet Explorer 9! Para chegar com tudo, o MSDN preparou uma semana de Webcasts especial sobre desenvolvimento web com IE9.

Dos 5 webcasts, fiquei responsável por 3 deles:

image

O que há de novo no Internet Explorer 9

Uma visão geral de tudo que temos de novo no IE9 tanto para usuários finais quanto para desenvolvedores. Como ele funciona, como e porquê ele está mais rápido e com o foco nos sites e não no browser.

A gravação do webcast pode ser acessada no seguinte endereço:
https://msevents.microsoft.com/CUI/EventDetail.aspx?EventID=1032481196&Culture=pt-BR

A apresentação em Power Point pode ser acessada no seguinte endereço:
http://cid-de5afe5b638592f4.office.live.com/view.aspx/Palestras/2011-03%20Semana%20Webcasts%20IE9/O%20que%20h%c3%a1%20de%20novo%20no%20IE9.pptx

image

O poder do HTML5

Entendendo de verdade o que é o HTML5, pra que serve e como usá-lo! Tudo bem prático, com exemplos de marcação e de utilização das APIs novas.

A gravação do webcast pode ser acessada no seguinte endereço:
https://msevents.microsoft.com/CUI/EventDetail.aspx?EventID=1032481198&Culture=pt-BR

A apresentação em Power Point pode ser acessada no seguinte endereço:
http://cid-de5afe5b638592f4.office.live.com/view.aspx/Palestras/2011-03%20Semana%20Webcasts%20IE9/O%20Poder%20do%20HTML5.pptx

Adiciono ainda hoje mais informações sobre o terceiro webcast: Aumentando o engajamento com sua audiência através de Sites Fixados do IE9
https://msevents.microsoft.com/CUI/EventDetail.aspx?EventID=1032481200&Culture=pt-BR

Boa web pra vocês!


Integrando Web Games com o Windows 7 via Internet Explorer 9

image

Nesta apresentação mostrei detalhes da nova experiência possibilitada pelo Windows 7 e a nova relação que o usuário tem com o Desktop que centraliza a comunicação com os programas na nova Taskbar.

O ponto principal é mostrar como o Internet Explorer 9 permite a integração de aplicações web, neste caso, web games, com o Windows 7, permitindo assim uma nova maneira de interação e comunicação com o jogo em questão.

Tudo isso com o novo recurso de Pinned Sites, notificações e thumbnail buttons.

Para demonstrar a codificação utilizei o novo editor Microsoft Webmatrix e a nova syntaxe Razor.

O Blend 4 para mostrar integração de jogos feitos em Silverlight com o Windows 7 via Ie9.

O Flash CS5 foi utilizado para demonstrar como integrar um Webgame feito em Flash com o Windows 7 via IE9.

Downloads

Apresentação

http://cid-de5afe5b638592f4.office.live.com/view.aspx/Palestras/2011-02-19%20Gamefest%20Brasil/Integrando%20Web%20Games%20Windows%207%20IE9.pptx

Código fonte das Demos
http://cid-de5afe5b638592f4.office.live.com/self.aspx/Palestras/2011-02-19%20Gamefest%20Brasil/WebGames%20Windows%207%20IE9.zip 

Download do IE9
http://www.beautyoftheweb.com

Mais informações e download do Webmatrix
http://www.microsoft.com/web/webmatrix/
http://www.asp.net/webmatrix

Aprendendo mais

Documentação do IE9 Pinned Sites
http://msdn.microsoft.com/en-us/library/gg491731(VS.85).aspx

Apresentações
Apresentação realizada no dia 19/02/2011 no Gamefest Brasil http://www.gamefestbrasil.com.br/ organizado pelo http://www.sharpgames.net

Até a próxima!


Introdução ao Windows Azure

image

Esta apresentação tem como objetivo apresentar uma visão geral de computação em nuvem e a proposta da plataforma Windows Azure para suprir os diversos cenários  para este tipo de ambiente. Também como dar os primeiros passos e publicar aplicações no Windows Azure.

A agenda apresentada é a seguinte:

•O que é o Windows Azure?
•Como desenvolver para Windows Azure?
•Cenários de aplicações para a nuvem

Downloads
Power Point da apresentação
http://cid-de5afe5b638592f4.office.live.com/view.aspx/Palestras/2011-02-11%20IO%20enCloud.io/Introdu%c3%a7%c3%a3o%20ao%20Windows%20Azure.pptx

Aprendendo mais

Para saber mais sobre o Windows Azure acesse o MSDN Brasil
http://www.msdnbrasil.com.br

Blog do Gerente de Azure no Brasil – Condé
http://blogs.msdn.com/conde

Apresentações
Apresentação realizada no dia 10/2/2011 no evento IO enCloud http://encloud.io realizado pelo portal http://www.ceviu.com.br

Até a próxima!


Introdução ao Visual Basic 2010

 

image

Esta apresentação tem como objetivo dar uma visão geral dos recursos disponíveis para desenvolvedores na linguagem Visual Basic 2010, características de seu funcionamento e benefícios para a construção de soluções.

A agenda apresentada é a seguinte:

•O que é a Plataforma .Net?
•O que é o .Net Framework?
•Multi Linguagem/Plataforma
•Ferramenta de Desenvolvimento
•Tipos de Aplicações
•Aprendendo mais sobre o .Net

Downloads
Power Point da apresentação
http://cid-de5afe5b638592f4.office.live.com/view.aspx/Palestras/2011-02-11%20IO%20enCloud.io/Introducao%20ao%20Visual%20Basic.pptx

Código fonte de demonstração
http://cid-de5afe5b638592f4.office.live.com/self.aspx/Palestras/2011-02-11%20IO%20enCloud.io/VBDemo.zip

Aprendendo mais

Para saber mais sobre o Visual Basic 2010 acesse o MSDN Brasil
http://www.msdnbrasil.com.br

What’s new in Visual Basic 2010
http://msdn.microsoft.com/en-us/library/ee336123.aspx

Apresentações
Apresentação realizada no dia 10/2/2011 no evento IO enCloud http://encloud.io realizado pelo portal http://www.ceviu.com.br

Até a próxima!


Introdução à Plataforma .Net

image

Esta apresentação tem como objetivo dar uma visão geral do que é a Plataforma .Net, características de seu funcionamento e benefícios para a construção de soluções.

A agenda apresentada é a seguinte:

•O que é a Plataforma .Net?
•O que é o .Net Framework?
•Multi Linguagem/Plataforma
•Ferramenta de Desenvolvimento
•Tipos de Aplicações
•Aprendendo mais sobre o .Net

Downloads
Power Point da apresentação
http://cid-de5afe5b638592f4.office.live.com/view.aspx/Palestras/2011-02-10%20IO%20enCloud/Introducao%20%c3%a0%20Plataforma%20DotNet.pptx 

Código fonte de demonstração
http://cid-de5afe5b638592f4.office.live.com/self.aspx/Palestras/2011-02-10%20IO%20enCloud/NetFrameworkDemo.zip

Esta solução possui projetos em C#, Vb.Net + WPF, C++, F#, Asp.Net e Windows Phone 7. Todos compartilham uma biblioteca baixa uma página HTML e extrai o seu título.

Aprendendo mais

Para saber mais sobre a Plataforma .Net acesse o MSDN Brasil
http://www.msdnbrasil.com.br

Centro para Iniciantes
http://msdn.microsoft.com/pt-br/beginner/default.aspx

Apresentações
Apresentação realizada no dia 10/2/2011 no evento IO enCloud http://encloud.io  realizado pelo portal http://www.ceviu.com.br

Até a próxima!


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!