Qabarcıqlı nizamlama

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 = ${\displaystyle O(n)}$
• orta vaxt = ${\displaystyle O(n^{2})}$

Redaktə rəng qabarcıq sıralama

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 ) ${\displaystyle \to }$ ( 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 ) ${\displaystyle \to }$ ( 1 4 5 2 8 ), 5 > 4 olduğu üçün
( 1 4 5 2 8 ) ${\displaystyle \to }$ ( 1 4 2 5 8 ), 5 > 2 olduğu
( 1 4 2 5 8 ) ${\displaystyle \to }$ ( 1 4 2 5 8 ), 5 < 8, heç bir dəyişiklik olmur.
İkinci keçid:
( 1 4 2 5 8 ) ${\displaystyle \to }$ ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ${\displaystyle \to }$ ( 1 2 4 5 8 ), 4 > 2 olduğu üçün
( 1 2 4 5 8 ) ${\displaystyle \to }$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ${\displaystyle \to }$ ( 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 ) ${\displaystyle \to }$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ${\displaystyle \to }$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ${\displaystyle \to }$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ${\displaystyle \to }$ ( 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]