Ordenação: Algoritmo Bubblesort

[nunopicado]

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...  🙂

[thoga31]

Ah isto tem nome? 😄

[nunopicado]

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... 😄

[thoga31]

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:

[nunopicado]

Olha um miudo a chamar-me filho!  🙂😄

[thoga31]

Olha um miudo a chamar-me filho! 😁😁

Hábitos do norte.