Qabarcıqlı nizamlama və ya qabarcıqlı sıralama (ing. Bubble sort) — iki qonşu elementi müqayisə etməklə və əgər onlar səhv nizamda isə onların yerini dəyişməklə verilən siyahını təkrarla yoxlayaraq, sıralayan alqoritmdir. Alqoritmin performansı aşağıdakı kimidir:
- ən yaxşı vaxt =
- orta vaxt =
Addım-addım nümunə
"5 1 4 2 8" şəklində bir massiv götürək, və massivi artma sırasına görə sıralayaq. Hər bir addımda müqayisə olunan elementlər tünd qara ilə göstərilib. Sona qədər sıralama üçün 3 keçid lazımdır.
Birinci keçid:
( 5 1 4 2 8 )
( 1 5 4 2 8 ), Burada alqoritm ilk iki elementi müqayisə edir və 5>1 olduğu üçün 5 ilə 1-in yerini dəyişir.
( 1 5 4 2 8 )
( 1 4 5 2 8 ), 5 > 4 olduğu üçün
( 1 4 5 2 8 )
( 1 4 2 5 8 ), 5 > 2 olduğu
( 1 4 2 5 8 )
( 1 4 2 5 8 ), 5 < 8, heç bir dəyişiklik olmur.
İkinci keçid:
( 1 4 2 5 8 )
( 1 4 2 5 8 )
( 1 4 2 5 8 )
( 1 2 4 5 8 ), 4 > 2 olduğu üçün
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
Hal - hazırda massiv artma sırasına görə sıralanıb (nizamlanıb). Amma alqoritm bunun belə olduğunu bilmədiyi üçün elementlərin yerini dəyişmədən birdaha elementləri müqayisə edəcək.
Üçüncü keçid:
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
İmplementasiyası
Python dilində implementasiya aşağıdakı kimi olar.
def bubblesort(A):
while True:
swapped = False
for i in range(1,len(A)-1):
if A[i-1]>A[i]:
tmp=A[i-1]
A[i-1]=A[i]
A[i]=tmp
swapped=True
if swapped==False:
break
return A
#Yuxarıdakı nümunə ilə test etsək
siyahi = [5,1,4,2,8]
print bubblesort(siyahi)
Cavab:
$python bubble.py [1, 2, 4, 5, 8]