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
- 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;
}
}
...
}

