Bubble Sort

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Bubble Sort

N passate

N passate, sulle N-1 coppie, ordinano il vettore

procedure BUBBLESORT_0(Var V: Vettore; N: Integer);
Var
   i, j: Integer;
begin
   For i:=1 to N do
      For j:=1 to N-1 do
         if(V[j] > V[j+1]) then
            SCAMBIA(V[j], V[j+1]);
end;

BubbleSort

Sono sufficienti N-1 passate su N-i coppie

procedure BUBBLESORT_1(Var V: Vettore; N: Integer);
Var
   i, j: Integer;
begin
   For i:=1 to N-1 do
      For j:=1 to N-i do
         If(V[j] > V[j+1]) then
            SCAMBIA(V[j], V[j+1]);
end;

Esempio

V={4, 3, 2, 1}, i=1, j=1..3 --> V={3, 4, 2, 1}
                            --> V={3, 2, 4, 1}
                            --> V={3, 2, 1, 4}

V={3, 2, 1, 4}, i=2, j=1..2 --> V={2, 3, 1, 4}
                            --> V={2, 1, 3, 4}

V={2, 1, 3, 4}, i=3, j=1..1 --> V={1, 2, 3, 4}

N-1 passate al massimo

Nel caso in cui il vettore risulti ordinato dopo un certo numero di passate è possibile interrompere l'esecuzione del while() introducendo la variabile ANCORA

procedure BUBBLESORT_2(Var V: Vettore; N: Integer);
Var
   Ancora: Boolean;
   i, j: Integer;
begin
   i:=1;
   Ancora:=True;
   while(i < N) And (Ancora) do
      begin
         Ancora:=False;
         For j:=1 to N-i do
            If(V[j] > V[j+1]) then
               begin
                  SCAMBIA(V[j], V[j+1]);
                  Ancora:=True;
               end;
         Inc(i);
      end;
end;

Semplifico 1: il numero di passate dipende solo da ANCORA

procedure BUBBLESORT_3(Var V: Vettore; N: Integer);
Var
   Ancora: Boolean;
   i, j: Integer;
begin
   i:=1;
   Ancora:=True;
   while(Ancora) do
      begin
         Ancora:=False;
         For j:=1 to N-i do
            if(V[j] > V[j+1]) then
               begin
                  SCAMBIA(V[j], V[j+1]);
                  Ancora:=True;
               end;
         Inc(i);
      end;
end;

Se la variabile ANCORA non interviene si ha una passata in più

Semplifico 2: elimino la differenza N-i

procedure BUBBLESORT_4(Var V: Vettore; N: Integer);
Var
   Ancora: Boolean;
   UltimaCoppia, j: Integer;
begin
   Ancora:=True;
   UltimaCoppia:=N-1;
   while(Ancora) do
      begin
         Ancora:=False;
         For j:=1 to UltimaCoppia do
            if(V[j] > V[j+1]) then
               begin
                  SCAMBIA(V[j], V[j+1]);
                  Ancora:=True;
               end;
         Dec(UltimaCoppia);
      end;
end;

Semplifico 3: la lunghezza del vettore dipende da UltimoScambio piuttosto che da UltimaCoppia

Procedure BUBBLESORT_5(Var V: Vettore; N: Integer);
Var
   Ancora: Boolean;
   UltimaCoppia, UltimoScambio, i: Integer;
begin
   Ancora:=True;
   UltimaCoppia:=N-1;
   while(Ancora) do
      begin
         Ancora:=False;
         UltimoScambio:=1;
         for i:=1 to UltimaCoppia do
         if(V[i] > V[i+1]) then
            begin
               SCAMBIA(V[i], V[i+1]);
               Ancora:=True;
               UltimoScambio:=i;
            end;
         UltimaCoppia:=UltimoScambio-1;
      end;
end;

In questo modo le passate diventano più corte.

Semplifico 4: il while-do esterno diventa repeat-until

Procedure BUBBLESORT_6(Var V: Vettore; N: Integer);
Var
   UltimaCoppia, UltimoScambio, i: Integer;
   FINITO: Boolean;
begin
   UltimaCoppia:=N-1;
   repeat
      FINITO:=True;
      UltimoScambio:=1;
      for i:=1 to UltimaCoppia do
         if(V[i] > V[i+1]) then
            begin
               SCAMBIA(V[i], V[i+1]);
               FINITO:=False;
               UltimoScambio:=i;
            end;
      UltimaCoppia:=UltimoScambio-1;
   until(FINITO);
end;

BubbleSort finale

Elimino la variabile FINITO

Procedure BUBBLESORT_7(Var V: Vettore; N: Integer);
Var
   UltimaCoppia, UltimoScambio, i: Integer;
begin
   UltimaCoppia:=N-1;
   repeat
      UltimoScambio:=1;
      for i:=1 to UltimaCoppia do
         if(V[i] > V[i+1]) then
            begin
               SCAMBIA(V[i], V[i+1]);
               UltimoScambio:=i;
            end;
      UltimaCoppia:=UltimoScambio-1;
   until(UltimoScambio = 1);
end;

Bubble Sort - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito