Burbulo rikiavimo algortimas Spausdinti
( 2 Votes )

Parašė Aurimas Šimkus   


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.


Pavyzdys C++ kalba:

1. Būdas

void Burbulas(int *mas, int n) {  
    int tmp;
    for(int i=0; i<n-1; i++){
        for(int j=0; j<n-i-1; j++){
            if(mas[j] > mas[j+1]){
                tmp = mas[j];
                mas[j] = mas[j+1];
                mas[j+1] = tmp;
            }
        }
    }
}