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 N elementų masyvo rikiavimui naudoja apie N²/2 lyginimų ir N²/2 keitimų vietomis, tiek laukiamu, tiek ir blogiausiu atveju. Algoritmas nenaudoja papildomos atminties.
[taisyti] Pavyzdžiai
- Realizacija Pascal kalba:
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; } } ... }