Jump to content

Ordenação: Algoritmo Bubblesort


nunopicado
 Share

Recommended Posts

O BubbleSort é um algoritmo de ordenação simples, mas eficaz.

Não é o mais rápido, mas para "poucos" registos, serve perfeitamente.

Consiste apenas em percorrer uma lista e testar cada valor contra todos os que lhe seguem nessa lista. Se o valor testado for maior que algum dos seguintes, trocam-se um pelo outro na posição dessa lista.

Complicado? Não!

Aliás, nada mais fácil.

Vamos a um exemplo:

var
   Lista:Array [0..99] of Real;

procedure BubbleSort:
var
   i,j:integer; // Precisamos de dois indexes
   Tmp:Real; // Precisamos também de uma variável do mesmo tipo de dados que estamos a ordenar
begin
   for i:=0 to 98 do  // Ciclo exterior: Percorre do primeiro ao penúltimo da lista
      for j:=i+1 to 99 do  // Ciclo interior: Percorre do registo seguinte ao actual do ciclo exterior até ao último da lista
         if Lista[i]>Lista[j]   // Se o da lista exterior for maior que o interior, troca-os
            then begin
                     Tmp:=Lista[i];
                     Lista[i]:=Lista[j];
                     Lista[j]:=Lita[i];
                   end;
end;
procedure MostraValores;
var
   i:integer;
begin
   clrscr;
   for i:=0 to 99 do
      writeln(i+1,'º valor: ',Lista[i]);
end;
.
.
.
begin
   .
   .  // Código para preencher a lista com valores, por exemplo, pedindo-os ao utilizador
   .
   BubbleSort;  // Chama o nosso algoritmo de ordenação
   MostraValores;  // Mostra a lista
end.

No final deste código, os dados do array estarão ordenados.

Outro exemplo, desta vez mais complexo, mas que do ponto de vista do Pascal, é a mesma coisa:

Imaginando que a lista é um array de records, com vários campos, e queremos ordenar por nome (alfabeticamente)

const
     MaxItems=100;

type
    TLista=Record
      Nome:String;
      Idade:integer;
    End;

var
   Lista:Array [0..MaxItems-1] of TLista;

O nosso BubbleSort ficaria assim:

procedure BubbleSort(var ListaOrdenada:Array of TLista);
var
   i,j:integer;
   Tmp:TLista;
begin
     for i := 0 to MaxItems-2 do
         for j:= i+1 to MaxItems-1 do
             if UpperCase(ListaOrdenada[i].Nome)>UpperCase(ListaOrdenada[j].Nome)  
                 then begin
                           Tmp:=ListaOrdenada[i];
                           ListaOrdenada[i]:=ListaOrdenada[j];
                           ListaOrdenada[j]:=Tmp;
                        end;
end;

Nada mais simples...  🙂

  • Vote 1

"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Link to comment
Share on other sites

lol

Tem. É o chamado algoritmo Bubblesort, ou ordenação por bolha, porque os valores menores vão subindo na lista até à sua posição ideal como se fossem bolhas de sabão a subir na atmosfera (uii, foi bonito  🙂 ).

No entanto, tens lá um pormenor a ajustar para ficar exactamente o Bubblesort, e ao mesmo tempo, para optimizar o código.

O FOR exterior deve ir do primeiro item da lista até ao penúltimo.

O FOR interior deve ir do item seguinte ao actual do FOR exterior até ao último.

Com isto evita-se algumas iteracções dos FOR's que são desnecessárias para levar a tarefa a cabo... 😄

"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Link to comment
Share on other sites

os valores menores vão subindo na lista até à sua posição ideal como se fossem bolhas de sabão a subir na atmosfera (uii, foi bonito  🙂 ).

Senhoras e senhores, sejam bem-vindos ao Portugal-a-Declamar 😄

O FOR exterior deve ir do primeiro item da lista até ao penúltimo.

O FOR interior deve ir do item seguinte ao actual do FOR exterior até ao último.

Com isto evita-se algumas iteracções dos FOR's que são desnecessárias para levar a tarefa a cabo... 🙂

Meu filho, aquele código foi dos primeiros de ordenação que fiz, e na época mal sabia o que era optimização. Aka inícios de 2010. 😄

Confesso que me esqueci de optimizar isso quando fiz o copy-paste para o tutorial dos meus antigos snippets :bag:

Knowledge is free!

Link to comment
Share on other sites

Olha um miudo a chamar-me filho!  🙂😄

"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.