Estrutura De Dados

2.2 BubbleSort

o mØtodo mais simples em termos de implementa ªo, porØm Ø o menos e ciente. A idØia principal do algoritmo Ø percorrer o vetor n − 1 vezes, a cada passagem fazendo utuar para o inicio o menor elemento da sequŒncia. Essa movimenta ªo, ilustrada na Figura 2.2, lembra a forma como as bolhas procuram seu pr prio n vel, por isso o nome do algoritmo. Seu uso nªo Ø recomendado para vetores com muitos elementos [7].

Figura 2.2: Ilustra ªo do funcionamento do algoritmo BubbleSort.

A seguir na Figura 2.3 Ø mostrado o uxograma do algoritmo.

Figura 2.3: Fluxograma do algoritmo BubbleSort.

2.2.1 Implementa ªo

Programa 2.5: MØtodo BubbleSort.

void SortMethods : : BubbleSort (TItem ∗Array , long n){

long i , j ; TItem aux ;

CTimer ∗Timer = new CTimer() ; this−>ClearAll () ; Timer−>start () ;

for ( i = 0 ; i < n−1 ; i++ ){

for ( j = 1 ; j < n−i ; j++ ){ this−>mComparations++;

if ( Array [ j ] . Key < Array [ j −1].Key){

aux = Array [ j ] ;

this−>mMoviments++; Array [ j ] = Array [ j −1]; this−>mMoviments++; Array [ j −1] = aux ; this−>mMoviments++;

}

}

}

Timer−>stop () ; this−>mTime = Timer−>getElapsedTime () ;

}

O Programa 2.5 mostra a implementa ªo do algoritmo para um conjunto de n itens, implementado como um vetor do tipo TItem. O algoritmo procede da seguinte forma:

1. Zera os valores das vÆriÆveis de medi ªo atravØs do mØtodo ClearAll();

2. Inicia a contagem de tempo com a fun ªo start();

3. Percorre o vetor, trazendo para o in cio o menor elemento encontrado;

4. A cada compara ªo incrementa a variÆvel mComparations e a cada movimenta ªo incrementa a variÆvel mMoviments;

5. Pausa a contagem de tempo e calcula o tempo gasto armazenando o valor na variÆvel mTime;

Uma maneira mais e ciente de implementa ªo do BubbleSort consiste em parar o processo logo que se detecte que, ao longo de uma passagem nªo foram efetuadas trocas de chaves [16].

2.2.2 Estudo da Complexidade

A Equa ªo 2.1 demonstra o calculo da fun ªo de complexidade em rela ªo ao nœmero de compara ıes. Ela Ø a mesma para o melhor, pior e caso mØdio.

(2.1)

Ordem de Complexidade: O(n2)

Para a fun ªo de complexidade em rela ªo ao nœmero de movimentos (Equa ªo 2.2 basta multiplicar a fun ªo C(n) por 3 que Ø o nœmero de movimenta ıes a