Scientific Research and Essay Vol. 4 (8), pp. 740-744, Agosto de 2009

Disponível online em http://www.academicjournals.org/SRE

ISSN 1922-2248© 2009 Academic Journals

Artigo Completo de Pesquisa.

Melhorando o desempenho do bubble sort usando um

método de Shell modificado

Oyelami Olufemi Moses

Departamento de Ciências da Informação e Computação, Covenant University, P. M. B. 1023, Ota, Ogun State, Nigeria. Email: olufemioyelami@yahoo.com ou olufemioyelami@gmail.com. Tel.: +234-8055344658.

A Ordenação implica na reorganização das informações tanto em ordem crescente como decrescente.

Existem muitos algoritmos de ordenação, entre eles está o Bubble Sort (“Ordenação em Bolha”). O Bubble Sort é

conhecido por não ser um bom algoritmo de ordenação por estar envolvido com comparações redundantes. No

entanto, esforços têm sido feitos a fim de melhorar o desempenho do algoritmo. Com o Bidirectional Bubble Sort

(“Ordenação bidirecional em bolha”) a média de comparações é levemente reduzida. O Batcher‟s Sort (“Algoritmo

de Batcher” – Autor do Algoritmo), similar ao Shellsort (“Ordenação de Shell” – Autor do Algoritmo), também

funciona significativamente melhor que o Bidirectional Bubble Sort por realizar comparações de uma forma

diferente de modo que não sejam necessárias propagações de trocas. O Bitonic„s Sort (A.k.a Parallel Sort –

“Ordenação Paralela”) também foi mostrado por Batcher e o ponto forte deste procedimento de organização é que

se adéqua muito bem em implementações de redes com fios ordenadas. Esse artigo apresenta um algoritmo

descritivo chamado “Oyelami‟s Sort”(Ordenação de Oyelami” – Autor do Artigo e do Algoritmo) que combina a

técnica do Bidirectional Bubble Sort com o método de Shell. Os resultados obtidos da implementação do algoritmo

comparado com o Batcher‟s Odd-Even Sort(“Ordenação Ímpar-Par de Batcher”) e o Batcher‟s Bitonic Sort

mostraram que o algoritmo desempenhou-se melhor do que estes dois, no pior cenário possível. A conclusão é

que o algoritmo é mais rápido.

Palavras-Chave: Algoritmo, ordenação, Bubble Sort, Bidirectional Bubble Sort, Batcher‟s Sort, Oyelami‟s Sort, pior cenário,

trocas, comparações.

INTRODUÇÃO

Utilizar computadores para solucionar diferentes situações

implica em mostrá-los quais etapas eles devem seguir

para solucionar estas situações. As etapas que devem ser

seguidas são chamadas de algoritmo. Um algoritmo é

uma sequência limitada de instruções com uma

quantidade limitada de soluções em uma quantia limitada

de tempo. (William, 2005; Alfred et al., 2002).

Algoritmos são extremamente importantes na

programação de computadores, contudo, um algoritmo

pode ser inútil mesmo que esteja correto e resulte nas

saídas (Outputs) desejadas. Isso acontece quando o

algoritmo exige recursos e tempo intoleráveis para o

domínio em que se encontra.

Instruções podem ser executadas quantas vezes

necessárias, desde que estas instruções indiquem a elas

mesmas a repetição. No entanto, não importam quais

valores de entradas serão assumidos, um algoritmo

sempre acaba depois de executar um número limitado de

instruções. Um programa é, portanto, um algoritmo, na

medida em que este não execute Loops (Ciclos) infinitos

em qualquer valor de entrada (Sara e Allen, 2000).

As cinco importantes características de um algoritmo

são (Donald, 1997):

I.) Finitude (Limitabilidade): Um algoritmo sempre deve

terminar após um número limitado de etapas.

II.) Entrada (Input): Um algoritmo tem zero ou mais

entradas – valores que são definidos antes do

algoritmo iniciar ou dinamicamente, conforme o

algoritmo é executado.

III.) Definibilidade: Cada passo de um algoritmo deve ser

precisamente definido; As ações a serem realizadas

devem ser rigorosamente especificadas para cada

situação.

IV.) Saída (Output): Um algoritmo possui uma ou mais

saídas – valores que tem conexão específica com as

Entradas (Inputs).

V.) Eficácia: Geralmente supõe-se que um algoritmo

será eficaz, no sentido de que suas operações

devem ser suficientemente básicas de modo que

possam ser solucionadas por completo em um

espaço limitado de tempo por alguém usando papel

e caneta.

A ordenação é um processo que reorganiza os

registros de uma fila de valores em uma sequência que é

separada em várias chaves (posições de um vetor).

Ordenações organizam um conjunto de dados tanto em

ordem crescente como decrescente (Yedidjah and Aaron,

2003; Frank, 2004).

As ordenações podem ser categorizadas de duas

formas: Ordenações Internas e Externas.

As ordenações internas exigem que todo o conjunto

de dados caiba na memória principal do computador,

enquanto nas ordenações externas, os dados,

coletivamente, não caberão na memória principal de uma

só vez, mas deverão residir em armazenamentos

auxiliares, como o disco rígido (Yedidjah and Aaron, 2003;

Frank, 2004; Shola, 2003).

Algoritmos de ordenação para computadores seriais

(random access machines ou RAMs) permitem a

execução de apenas uma operação por vez. Nos

algoritmos de ordenação baseados no modelo

computacional de comparações em rede, diversas

comparações podem ser executadas simultaneamente.

Comparações em rede se diferem das RAMs em dois

importantes aspectos. Primeiro, os modelos RAMs só

podem realizar comparações. Segundo, diferente do

modelo RAM, cujas operações ocorrem em série, ou seja,

uma após a outra, operações em redes de comparações

podem ocorrer ao mesmo tempo ou “em paralelo”.

Uma rede de ordenações é uma rede de

comparações no qual a sequência de saída aumenta

monotonicamente (Ou seja, ) para

cada sequência de entrada (Thomas et al., 2003).

O método de Shell, como usado no Shellsort,

oferece um simples e eficiente algoritmo de ordenação.

Este algoritmo aprimora-se na Insertion Sort (“Ordenação

de Inserções”) por reduzir o numero de inversões e

comparações feitas nos elementos a serem ordenados.

Ele ordena um array (vetor) „A‟ com „n‟ elementos

dividindo-o em subseqüências e ordena as

subseqüências. Isso é chamado de ordenação

„decrescente‟ (Procurar definição correta) de incrementos

(Diminishing increment sorting ou “método de Shell” – vide

título do Artigo) porque os incrementos continuam a

diminuir de um passo para o outro até que o último

incremento seja „1‟.

O Bubble Sort é um tipo de ordenação interna que

compara elementos adjacentes e os permuta se estes

estão fora de ordem e continua até que a sequência de

valores estejam ordenados (Frank, 2004; Robert, 1998).

De qualquer forma, o Bubble Sort não é um algoritmo

eficiente, pois é um algoritmo de ordenação com consumo

de tempo quadrático (Exponencial). No entanto, esforços

têm sido feitos a fim de melhorar o desempenho do

algoritmo. Com o Bidirectional Bubble Sort a média de

comparações é levemente reduzida. O Batcher’s Sort,

similar ao Shellsort, também funciona significativamente

melhor que o Bidirectional Bubble Sort por realizar

comparações de uma forma diferente de modo que não

sejam necessárias propagações de trocas. O Bitonic‘s

Sort também foi mostrado por Batcher e o ponto forte

deste procedimento de organização é que se adéqua

muito bem em implementações de redes com fios

ordenadas.

Este Artigo apresenta um algoritmo que combina as

técnicas do Bidirectional Bubble Sort com um modificado

método de Shell para melhorar o Bubble Sort. Os

resultados obtidos da implementação do algoritmo

comparada com o Batcher’s Odd-Even Sort e o Bitonic

Sort mostrou que o algoritmo é o mais rápido dos três.

MÉTODOS E MATERIAIS

O Oyelami’s Sort foi desenvolvido através de um

modificado método de Shell como usado no Shellsort e,

em seguida, aplicado nos elementos a serem ordenados

antes de aplicar o Bidirectional Bubble Sort. Devemos

levar em conta que o tipo de método de Shell usado é

diferente do usado no Shellsort, mas é como o usado por

Oyelami (2008) e Oyelami et al. (2007).

Bubble Sort

Para entender como o Bubble Sort funciona, considere

um array contendo elementos à serem ordenados. Nós

passamos pelo array e pegamos o menor elemento e o

colocamos na posição „1‟. Esse é o primeiro passo. Nós

olhamos os elementos restantes desde a posição „2‟ até a

última posição e pegamos o menor elemento colocando-o

na posição „2‟ e assim sucessivamente, até que todos os

elementos estejam ordenados. Por exemplo, considere os

números abaixo:

8 4 3 2

A Figura 1 mostra uma representação ilustrativa de como

a ordenação será realizada.

Refinamentos no Bubble Sort

Houve algumas melhorias no Bubble Sort como

discutidas abaixo:

Bidirectional Bubble Sort

O Bidirectional Bubble Sort também conhecido como

Cocktail Sort ou Shaker Sort é uma variação do Bubble

Sort que é tanto um algoritmo estável de ordenação como

de comparação. O algoritmo se diferencia do Bubble Sort

nessas ordenações em ambos os sentidos que percorre o

array (O vetor é percorrido em idas e voltas até que os

valores estejam ordenados). A média de comparações

diminui levemente em razão desta abordagem (Donald,

1998). Este algoritmo de ordenação é apenas um pouco

mais difícil que o Bubble Sort na implementação e resolve

o problema com as chamadas Turtles (“Tartarugas” –

Lentidões quadráticas) no Bubble Sort. Considere para

esta situação de ordenação o mesmo conjunto de

números usado para o Bubble Sort:

8 4 3 2

O algoritmo faz a mesma ordenação como vista na Figura

2. Ocorrem „7‟ comparações e „6‟ trocas no total.

Figura 1. Demonstração do Bubble Sort.

Figura 2. Demonstração do Bidirectional

Bubble Sort.

Figura 3. Demonstração do Batcher’s

Odd and Even Merge Sort.

Batcher‟s Odd and Even Merge Sort

(“Ordenação de mistura Ímpar-Par de Batcher”)

Se você possui uma lista de chaves (ou Keys – posições

do vetor) dispostas da esquerda para a direita, e você

ordena a metade esquerda e a metade direita da lista,

separadamente, e logo após ordena as chaves de

posições pares da lista e depois as chaves de posições

ímpares da lista, então tudo o que você precisa fazer é

comparar e trocar cada posição par (da esquerda para a

direita) com a chave de posição ímpar logo à sua direta, e

você terá ordenado completamente a lista.

O algoritmo pode ser resumido da seguinte forma: Ordene

o algoritmo em „2m‟ chaves (m = metade do número de

chaves) onde deverá ordenar a metade esquerda e

ordenar a metade direita; Então misture as duas metades,

podendo descrever o passo de mistura como Mistura de

2m chaves, onde misturamos „m‟ chaves ímpares com „m‟

chaves pares. Em seguida, comparáramos e trocamos

cada chave par com a chave ímpar à direita.

Para uma explicação de como Batcher’s Sort

funciona, suponha os números „8‟,‟4‟,‟3‟ e „2‟ mostrados

acima. Os números são ordenados como mostrado na

Figura 3.

Ao todo, ocorrem „5‟ comparações e „4‟ trocas,

mostrando a superioridade do Batcher’s Sort sobre o

Bidirectional Bubble Sort.

Bitonic Sort9

Uma sequência “Bitônica” (Tradução Livre) é uma

que monotonicamente aumenta e monotonicamente

diminui. Um ordenador Bitônico é composto de diversos

estágios, cada um deles é chamado de Half-Cleaner (Sem

tradução direta – São as metades bitônicas da metade

anterior). Cada Half-Cleaner é uma rede de comparação

de profundidade „1‟ em que a linha de Entrada „i‟ é

comparada com a linha i + n/2 para l = 1, 2, ... n/2

(assume-se que „n‟ é par – „n‟ número de elementos no

array). Por combinar os Half-Cleaners recursivamente

(Divisões sucessivas do vetor) , um ordenador Bitônico

pode ser construído, que é uma rede que ordena

sequências Bitônicas (Thomas et AL., 2003). Para

demonstrar como o Bitonic Sort funciona, considere a

situação habitual de ordenação dos números „8‟, „4‟, „3‟ e

„2‟. Os números são ordenados da seguinte forma:

Os Half-Cleaners são usados nos passos „1‟ e „2‟, e as

Bitonic Mergers (misturas “bitônicas”) são usadas nos

passos 3 e 4.

Ao todo, ocorrem „6‟ comparações e „4‟ trocas.

O Algoritmo Proposto (Oyelami‟s Sort)

Este algoritmo de ordenação proposto divide os

elementos a serem ordenados em subseqüências assim

como o Shellsort faz, mas, primeiro de tudo, compara o

primeiro elemento com o último. Se o último é menor que

o primeiro, os dois trocam de posição, senão,

permanecem em suas posições. Depois, o segundo

elemento é comparado com o penúltimo e, se o penúltimo

elemento é menor do que o segundo, eles são trocados.

Caso contrário, eles mantém suas posições. Esse

processo continua até que os últimos dois elementos

centrais são comparados ou até que sobre apenas um

elemento no centro. Depois, o Bidirectional Bubble Sort é

aplicado para ordenar os elementos adjacentes. Essa

abordagem reduz o número de comparações e inversões

realizadas significativamente.

Considere o pior cenário de ordenação dos

elementos a seguir usados para o Batcher’s Sort e o

Bitonic Sort em ordem crescente:

8 4 3 2

O algoritmo funciona assim:

Figura 4. Demonstração do Oyelami’s

Sort.

O Bidirectional Bubble Sort é aplicado a partir do (*) para

ordenar os elementos que são adjacentes, como

mostrados na Figura 4.

Uma vez que nenhuma troca ocorra, o algoritmo

para, eliminando a necessidade de percorrer o array

novamente na ida ou na volta. Ao todo, „5‟ comparações

foram realizadas e apenas „2‟ trocas. Isso mostra que o

algoritmo se sobressai melhor que o de Batcher que

possui „5‟ comparações e „4‟ trocas. Quando comparado

com o Bitonic’s Sort („6‟ comparações e „4‟ trocas) ele

também se sobressai melhor. Apresentamos o algoritmo a

seguir:

Oyelami‟s Sort (array, size)

Begin

1. i = 1

2. j = size

3. while (i < j) do

begin

4. if array[i] > array[j] swap (array, i, j)

5. i = i + 1

6. j = j – 1

end

[Chama o Bidirectional Bubble Sort para ordenar os

elementos adjacentes]

7. Bidirectional Bubble Sort (A, size:int)

End

Análise de Desempenho dos Algoritmos

O atributo mais importante de um programa/algoritmo é a

sua validação/consistência (Correctness – Sem tradução

direta). Algoritmos que não geram saídas (Outputs)

corretas são inúteis. No entanto, algoritmos corretos

também podem ser de pouca utilidade. Isso acontece

muitas vezes quando o algoritmo/programa leva mais

tempo do que o esperado pelo usuário para executar ou

quando ele usa muito mais memória do que a disponível

no computador. (Sartaj, 2000). O desempenho de um

programa ou de um algoritmo é a quantidade de tempo e

a quantidade de memória necessária para executar o

programa/algoritmo. Existem dois métodos que são

normalmente utilizados na análise de um algoritmo:

I.) Método analítico.

II.) Método experimental.

No método analítico, os fatores de tempo e requisitos de

espaço de que um programa depende são identificados e

seus contributos/contribuições/requisitos (Contributions -

Sem tradução direta) são determinados. Mas uma vez

que esses fatores não são conhecidos no momento em

que o programa é escrito, uma analise precisa de tempo e

requisitos de espaço não podem ser feitas.

O método experimental lida justamente com a

execução do experimento e a medição do espaço e tempo

usados pelo programa. Duas abordagens generalizadas

para estimativa de tempo de execução são (Sartaj, 200):

I.) Identificar uma ou mais operações principais e

determinar o número de vezes que elas são

executadas.

II.) Determinar o número total de etapas executadas pelo

programa

Análise dos algoritmos de ordenação no pior, melhor

e médio casos.

O pior cenário ocorre em um algoritmo de ordenação

quando os elementos a serem ordenados estão na ordem

contrária ( ). O melhor caso acontece

quando os elementos já estão ordenados (

). O caso mediano pode ocorrer quando parte dos

elementos já estão ordenados ( , Exemplo:

1, 2, 4, 3). O caso mediano tem seus dados distribuídos

aleatoriamente na lista de valores (William e William,

2002). O caso mediano pode não ser fácil para determinar

pelo fato de que nem sempre é possível determinar o

quanto disperso ficaram as Inputs (Valores que entraram).

O foco está sempre em buscar os piores casos de tempo

de execução para quaisquer Inputs de tamanho „n‟ devido

aos seguintes motivos (Thomas et al., 2003):

I.) O pior caso de tempo de execução de um algoritmo é

o maior limite de tempo de execução que pode ser

atingido pelo algoritmo para quaisquer Inputs.

Conhecendo este fato nos dá a garantia de que o

algoritmo nunca levará mais tempo que o limite

máximo que pode atingir. Nós não precisamos dar

palpites sobre o tempo de execução e torcer para que

o tempo de execução nunca fique pior.

II.) Para alguns algoritmos, os piores casos ocorrem com

bastante freqüência. Por exemplo, pesquisando o

banco de dados por uma parte específica de uma

informação, os piores casos do algoritmo de busca

ocorrerão quando a informação não se encontra no

banco de dados. Em muitas aplicações de busca,

pesquisas por informações inexistentes podem ser

frequentes.

III.) Muitas vezes, os casos medianos tão piores quanto os

piores casos.

Análise do algoritmo proposto

Geralmente, o tempo de execução de um algoritmo de

ordenação é proporcional ao número de comparações

que o algoritmo efetua, ao número de vezes que os

elementos são movidos ou trocados. A abordagem usada

neste Artigo é a medição do número de comparações e

trocas realizadas por cada algoritmo (Batcher’s Sort,

Bitonic Sort, e Oyealmi’s Sort) no pior cenário possível.

Tabela 1. Comparações de desempenho do Batcher’s Odd-Even Sort, Bitonic Sort e Oyelami’s Sort:

RESULTADOS E DISCUSSÕES

A Tabela 1 mostra os resultados obtidos. De acordo

com os resultados, o algoritmo proposto tem menos

comparações e trocas quando comparado com ambos

os algoritmos. Os resultados também mostram que

conforme o tamanho de entradas (“Tamanho do Array”)

aumenta, o algoritmo proposto tende a ser mais

eficiente e, tanto o Batcher’s Odd-Even Sort como o

Bitonic Sort não são bons para muitos valores de

entrada. A conclusão disso é que o algoritmo proposto é

mais rápido e, sendo assim, mais eficiente. O algoritmo

também é recomendado para ordenar grandes

quantidades de Inputs.

Conclusão

O Bubble Sort é conhecido por não ser um bom

algoritmo de ordenação por estar envolvido com

comparações redundantes. No entanto, esforços têm

sido feitos a fim de melhorar o desempenho do

algoritmo. Com o Bidirectional Bubble Sort a média de

comparações é levemente reduzida. O Batcher’s Sort,

similar ao Shellsort, também funciona significativamente

melhor que o Bidirectional Bubble Sort por realizar

comparações de uma forma diferente de modo que não

sejam necessárias propagações de trocas. Este Artigo

foi bem aprimorado em relação ao Batcher’s Sort

usando as técnicas do Bidirectional Bubble Sort e do

método de Shell. Os testes com o algoritmo proposto e

o Batcher’s Sort mostraram que o algoritmo proposto é

mais eficiente. O algoritmo é recomendado para todos

os tamanhos de elementos a serem ordenados, mas é

muito mais eficiente conforme o número elementos a

serem sorteados aument

REFERÊNCIAS

Alfred V, Aho J, Horroroft, Jeffrey DU (2002). Data Structures and Algorithms (India: Pearson Education Asia).

Donald EK (1997). The Art of Computer Programming, Volume I,Fundamental Algorithms; Third Edition. US: Addison-

Wesley.

Donald EK (1998). The Art of Computer Programming, Volume 3,Sorting and Searching, Second Edition. Addison-Wesley.

Frank MC (2004). Data Abstraction and Problem Solving with C++. US: Pearson Education, Inc.

Oyelami MO (2008). A Modified Diminishing Increment Sort for Overcoming the Search for Best Sequence of Increment for

Shellsort”. J. Appl. Sci. Res., 4 (6): 760- 766.

Oyelami MO, Azeta AA, Ayo CK (2007). Improved Shellsort for the Worst-Case, the Best-Case and a Subset of the

Average-Case Scenarios. J. Comput. Sci Appl. 14 (2): 73- 84.

Robert S (1998). Algorithms in C. Addison-Wesley Publishing Company, Inc.

Sara B, Allen G (2000). Computer Algorithms. US: Addison Wesley Longman.

Sartaj S (2000). Data Structures, Algorithms and Applications in Java. McGrawHill.

Shola PB (2003). Data Structures With Implementation in C and Pascal. Nigeria: Reflect Publishers.

Thomas HC, Charles EL, Ronald LR, Clifford S (2003). Introduction to Algorithms. The Massachusetts Institute of

Technology.

William F, William T (2002). Data Structures With C++ Using STL. Prentice Hall.

William JC (2005). Data Structures and the Java Collections Framework (US: The McGrawHill Companies, Inc).

Yedidjah L, Moshe A, Aaron MT (2003). Data Structures Using Java. US: Pearson Education, Inc.