Bubble Sort

5.1 Bubble Sort haqqında tərif

Bubble Sort — bu çox sadə bir çeşidləmə alqoritmidir. Siyahının üzərindən dəfələrlə keçir, qonşu elementləri müqayisə edir və əgər düzgün ardıcıllıqda deyilsə, yerlərini dəyişir. Bu proses siyahı tam şəkildə çeşidlənənə qədər davam edir.

İş prinsipi:

1. Alqoritm siyahı üzərindən keçir və hər bir cüt qonşu elementi müqayisə edir.
2. Əgər elementlər düzgün ardıcıllıqda deyilsə (artan sıralama üçün birincisi ikincidən böyükdür) — yerləri dəyişdirilir.
3. Bu proses siyahıdakı bütün element cütləri üçün təkrarlanır.
4. Hər tam keçid zamanı ən böyük element öz yerinə «üzür» (su səthinə çıxan köpük kimi), buna görə də növbəti keçidlərə daxil olmur.
5. Proses siyahı tam çeşidlənənə qədər təkrarlanır.

Bubble Sort-un vaxt və yaddaş mürəkkəbliyi

Vaxt mürəkkəbliyi:

• Ən pis halda: O(n^2) — əgər elementlər əks ardıcıllıqda düzülmüşdürsə.
• Orta halda: O(n^2) — elementlər təsadüfi şəkildə yerləşdirildikdə baş verir.
• Ən yaxşı halda: O(n) — elementlər artıq çeşidlənmiş olduqda baş verir (alqoritm bu halda optimallaşdırıla bilər, əgər keçid zamanı elementlərin yeri dəyişibsə yoxlama əlavə edilərsə).

Yaddaş mürəkkəbliyi:

O(1) — çünki alqoritm sabit miqdarda əlavə yaddaş istifadə edir (yalnız müvəqqəti dəyərləri saxlamaq üçün bir neçə dəyişən).

5.2 Alqoritmin həyata keçirilməsi

"Bubble Sort" alqoritmi — siyahı/massiv elementlərini sıralamaq üçün ən sadə və primitiv alqoritmdir. Sadəcə olaraq elementləri qoşa-qarşılaşdırır və ehtiyac varsa, yerlərini dəyişir.

Versiya 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Elementlərin dəyişdirilməsi

print("Sıralanmış massiv:", array)
# Çıxış: Sıralanmış massiv: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Daxili dövr (yaşıl rənglə vurğulanıb) elementi sağ qonşusu ilə müqayisə edir. Və əgər lazımdırsa — elementlərin yerlərini dəyişir.

Versiya 2:

Alqoritmimizə dərhal optimizasiya əlavə etmək olar: birinci keçiddən sonra ən böyük element sağda olacaq, ona görə də onu növbəti dövrdə nəzərə almağa ehtiyac yoxdur.

İkinci iterasiyadan sonra sağ tərəfdə artıq 2 ən böyük element olacaq, ona görə də daxili dövr n - 1 deyil, n - 1 - i qədər işləyə bilər. Burada i — xarici dövrün keçdiyi iterasiyaların sayıdır.

Yeni variant belə olacaq:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Elementlərin dəyişdirilməsi

print("Sıralanmış massiv:", array)
# Çıxış: Sıralanmış massiv: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Versiya 3:

Həmçinin massiv artıq demək olar ki, sıralanmış ola bilər. Buna görə də belə bir optimizasiya əlavə etmək olar: əgər daxili dövr bütün elementlərdən keçibsə, lakin heç bir dəyişiklik etməyibsə, sıralama başa çatıb.

Bu versiyada swapped dəyişəni istifadə olunur ki, bu da sonuncu keçid zamanı elementlərin dəyişdirilib-dəyişdirilmədiyini izləyir. Əgər massivdən keçiddən sonra heç bir dəyişiklik olmayıbsa, bu o deməkdir ki, massiv artıq sıralanıb və daha çox iterasiya aparmağa ehtiyac yoxdur — onlar sıralamanı yaxşılaşdırmaz. Beləliklə, swapped dəyişəni, demək olar ki, sıralanmış massivlərdə alqoritmin işini xeyli tezləşdirərək, onun icrasını vaxtından əvvəl başa çatdırmağa imkan verir.

Python-da Bubble Sort alqoritminin həyata keçirilməsi:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False # Optimizasiya: dəyişiklik olub-olmadığını yoxlamaq
        for j in range(0, n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Elementlərin dəyişdirilməsi
                swapped = True
        if not swapped:
            break  # Əgər dəyişiklik olmayıbsa, massiv artıq sıralanıb
    return array

# İstifadə nümunəsi:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("Sıralanmış massiv:", sorted_array)
# Çıxış: Sıralanmış massiv: [11, 12, 22, 25, 34, 64, 90]