Qabarcıq sıralama

Qabarcıq sıralama (ing. Bubble sort) — İki 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 = $O(n)$
• orta vaxt = $O(n^2)$

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