Kabarcık Sıralaması

#Nasıl çalışır?

Kabarcık sıralaması (bubble sort), diziyi baştan sona tekrar tekrar gezerek yan yana duran iki elemanı karşılaştırır. Soldaki sağdakinden büyükse ikisinin yerini değiştirir.

Her geçişin sonunda henüz sıralanmamış kısımdaki en büyük eleman, sudaki bir kabarcık gibi dizinin sonuna doğru yükselir ve kalıcı yerine oturur. Algoritma adını buradan alır.

Bir geçiş boyunca hiç yer değiştirme olmazsa dizi sıralanmış demektir ve algoritma erken durabilir.

#Canlı animasyon

for i = 0 to n - 2
  swapped = false
  for j = 0 to n - i - 2
    if a[j] > a[j + 1]
      swap(a[j], a[j + 1]); swapped = true
  if not swapped: break

#Adım adım

1. 01Dizinin başından başla ve ilk iki elemanı karşılaştır.
2. 02Soldaki eleman sağdakinden büyükse ikisinin yerini değiştir.
3. 03Bir sağa kay ve sıradaki komşu çifti karşılaştır; sona gelene kadar devam et.
4. 04Geçiş bittiğinde en büyük eleman en sağa yerleşmiştir. Bir sonraki geçişte bu elemana artık bakma.
5. 05Bir geçişte hiç yer değiştirme olmayana ya da sıralanacak eleman kalmayana kadar tekrarla.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def bubble_sort(a: list[int]) -> None:
    n = len(a)
    for i in range(n - 1):
        swapped = False
        # After pass i, the last i elements are already in place.
        for j in range(n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:  # no swaps: already sorted
            break


numbers = [5, 1, 4, 2, 8, 3]
bubble_sort(numbers)
print(*numbers)

#Karmaşıklık

En iyi durum O(n), dizi zaten sıralıyken ve erken durma (swapped bayrağı) kullanıldığında geçerlidir. Tek bir geçişte n-1 karşılaştırma yapılır. Ters sıralı bir dizide yaklaşık n²/2 karşılaştırma ve aynı sayıda yer değiştirme gerekir.

#Ne zaman kullanılır?

Bubble sort öğrenmek için mükemmeldir: karşılaştırma, yer değiştirme ve döngü değişmezi (loop invariant) kavramlarını çok net gösterir. Gerçek projelerde ise büyük veride yavaş kalır; bunun yerine merge sort, quick sort ya da dilin hazır sort fonksiyonu tercih edilir. Çok küçük veya neredeyse sıralı dizilerde hâlâ makul çalışabilir.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.