Burbulo rikiavimo algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Algoritmas
Tipas Rikiavimo algoritmai
Pavadinimas Burbulo (Bubble Sort)
Sudėtingumas Vidutinis - N2; blogiausias - N2
Greitos nuorodos

Burbulo rikiavimo metodas - vienas iš paprastų, bet nelabai efektyvių rikiavimo algoritmų. Algoritmo principas - nuosekliai iš eilės peržiūrėti gretimų elementų poras, prireikus elementus sukeisti, perkeliant mažesnį arčiau pradžios. Tokiu būdu per pirmą iteraciją mažiausias elementas perkeliamas į pirmą poziciją, vėliau tas pats principas taikomas posekiui be pirmo elemento ir t.t.

Algoritmo veikimo principas primena virimo procesą, kai oro burbulai kyla į paviršių, dėl to jis ir vadinamas burbulo metodu.

Burbulo algoritmas naudoja apie N²/2 lyginimų ir N²/2 keitimų vietomis, tiek laukiamu, tiek ir blogiausiu atveju. Algoritmas nenaudoja papildomos atminties.

[taisyti] Pavyzdžiai

procedure Burbulas(var a:array of integer; N:integer);
var i,j,t: integer;
begin
for i:=N downto 1 do
  for j:=2 to i do
    if a[j-1]>a[j] then
      begin
        t:=a[j-1];
        a[j-1]:=a[j];
        a[j]:=t;
      end
end;
  • Realizacija Java kalba
public class Pavyzdys {

...

    private int[] duomenys;
    private final int ilgis;
...

    private void rikiuotiBurbuliuku() {
        boolean testi = true;
        int pask = ilgis - 1;
        while (testi) {
            testi = false;
            for (int i=0;i<pask;++i) {
                if (duomenys[i] > duomenys[i+1]) {
                    int laikinas = duomenys[i];
                    duomenys [i] = duomenys [i+1];
                    duomenys[i+1] = laikinas;
                    testi = true;
                }
            }
            --pask;
        }
    }

...

}