Kabarcık, Seçmeli ve Eklemeli Sıralama

İkili arama sıralılık varsayıyordu; öyleyse sıralamanın kendisi incelenmelidir. Sıralama, algoritma öğretiminin merkezinde durur: aynı problem, farklı fikirlerle onlarca kez çözülmüş ve çözümler tam olarak bu kursun araçlarıyla karşılaştırılmıştır.

Bu ders karesel maliyetli üç temel algoritmayı ele alır. Amaç yalnızca onları öğrenmek değil, sonraki derslerin daha iyi algoritmalarını karşılaştıracak bir taban kurmaktır.

Problem ve Ölçütler

Sıralama problemi: Girdi, karşılaştırılabilir elemanlardan oluşan bir dizidir. Çıktı, aynı elemanların bir permütasyonu olan ve azalmayan sırada dizilmiş bir dizidir.

İki koşul da gereklidir. Yalnızca sıralılık istenirse, girdiyi silip boş dizi döndürmek “çözüm” sayılırdı; permütasyon koşulu bunu engeller.

Sıralama algoritmaları üç ölçütle ayrılır:

Kararlılık (stability). Eşit anahtarlı elemanların göreli sırası korunuyorsa algoritma kararlıdır. Çok anahtarlı sıralamalarda belirleyicidir: önce şehre, sonra kararlı bir algoritmayla tarihe göre sıralanan kayıtlarda şehir sırası bozulmaz.

Yerinde çalışma. Ek alan sabitse algoritma yerindedir.

Uyarlanabilirlik. Girdi kısmen sıralıysa maliyeti düşüyorsa algoritma uyarlanabilirdir.

Ayrıca iki ayrı maliyet sayılır: karşılaştırma sayısı ve taşıma (yer değiştirme veya kaydırma) sayısı. Elemanlar büyük nesnelerse taşıma pahalıdır; karşılaştırma karmaşık bir işlevse karşılaştırma pahalıdır.

Kabarcık Sıralama

Komşu elemanlar karşılaştırılır ve sıra bozuksa yer değiştirilir. Her geçişte en büyük eleman sona “kabarır”.

def kabarcik_siralama(dizi: list[int]) -> list[int]:
    """Değişmez: her dış turdan sonra son `n - son` eleman kesin yerindedir."""
    d = list(dizi)
    for son in range(len(d) - 1, 0, -1):
        degisim = False
        for i in range(son):
            if d[i] > d[i + 1]:
                d[i], d[i + 1] = d[i + 1], d[i]
                degisim = True
        if not degisim:                 # hiç değişim yoksa dizi sıralıdır
            break
    return d


print(kabarcik_siralama([5, 2, 9, 1, 5, 6]))    # [1, 2, 5, 5, 6, 9]

Erken çıkış bayrağı olmadan algoritma her durumda $n(n-1)/2$ karşılaştırma yapar. Bayrakla birlikte sıralı girdide tek geçişte durur: en iyi durum $O(n)$ olur.

En kötü ve ortalama durum $O(n^2)$’dir. Taşıma sayısı da karesel olabilir — ters sıralı girdide her karşılaştırma bir yer değiştirmeye yol açar. Algoritma kararlıdır (yalnızca kesin büyüklükte yer değiştirilir) ve yerindedir.

Seçmeli Sıralama

Kalan bölümün en küçüğü bulunur ve bulunduğu yerle sınırın başı yer değiştirir.

def secmeli_siralama(dizi: list[int]) -> list[int]:
    """Değişmez: her turdan sonra ilk i eleman kesin sıralıdır."""
    d = list(dizi)
    for i in range(len(d) - 1):
        en_kucuk = i
        for j in range(i + 1, len(d)):
            if d[j] < d[en_kucuk]:
                en_kucuk = j
        d[i], d[en_kucuk] = d[en_kucuk], d[i]
    return d


print(secmeli_siralama([5, 2, 9, 1, 5, 6]))     # [1, 2, 5, 5, 6, 9]

Karşılaştırma sayısı girdiden bağımsızdır: her zaman $n(n-1)/2$. Uyarlanabilir değildir — sıralı girdide de tam maliyeti öder.

Buna karşılık taşıma sayısı en çok $n-1$’dir ve bu, algoritmanın tek üstünlüğüdür: elemanlar çok büyükse veya yazma işlemi pahalıysa (bazı kalıcı bellek türlerinde okuma ile yazma maliyeti eşit değildir), az yazma yapan bir algoritma tercih edilebilir.

Bu biçimiyle kararlı değildir: uzak bir elemanla yer değiştirme, eşit anahtarlıların sırasını bozabilir.

def secmeli_siralama_kayit(kayitlar: list[tuple[int, str]]) -> list[tuple[int, str]]:
    """Yalnızca ilk alana (anahtara) göre sıralar; ikinci alan kimliktir."""
    d = list(kayitlar)
    for i in range(len(d) - 1):
        en_kucuk = i
        for j in range(i + 1, len(d)):
            if d[j][0] < d[en_kucuk][0]:
                en_kucuk = j
        d[i], d[en_kucuk] = d[en_kucuk], d[i]
    return d


print(secmeli_siralama_kayit([(2, "a"), (2, "b"), (1, "c")]))
# [(1, 'c'), (2, 'b'), (2, 'a')]

Çıktıda b, a’nın önüne geçmiştir; girdide sıra tersineydi. Yer değiştirme yerine kaydırma yapan bir değişke kararlı olur, ama o zaman taşıma üstünlüğü kaybolur.

Eklemeli Sıralama

Her eleman, kendisinden önceki sıralı bölüme doğru yerine kaydırılarak eklenir. İskambil kâğıtlarını elde sıralama biçimi budur.

def eklemeli_siralama(dizi: list[int]) -> list[int]:
    """Değişmez: her turun başında ilk i eleman kendi arasında sıralıdır."""
    d = list(dizi)
    for i in range(1, len(d)):
        anahtar = d[i]
        j = i - 1
        while j >= 0 and d[j] > anahtar:
            d[j + 1] = d[j]             # kaydır
            j -= 1
        d[j + 1] = anahtar
    return d


def eklemeli_siralama_kayit(kayitlar: list[tuple[int, str]]) -> list[tuple[int, str]]:
    d = list(kayitlar)
    for i in range(1, len(d)):
        anahtar = d[i]
        j = i - 1
        while j >= 0 and d[j][0] > anahtar[0]:
            d[j + 1] = d[j]
            j -= 1
        d[j + 1] = anahtar
    return d


print(eklemeli_siralama([5, 2, 9, 1, 5, 6]))    # [1, 2, 5, 5, 6, 9]
print(eklemeli_siralama_kayit([(2, "a"), (2, "b"), (1, "c")]))
# [(1, 'c'), (2, 'a'), (2, 'b')]   — girdideki a, b sırası korundu

Döngü koşulundaki > işareti kararlılığın kaynağıdır: eşitlikte kaydırma durur, yeni eleman eşitinin arkasına yerleşir. >= yazılsaydı algoritma kararlılığını yitirirdi.

En iyi durum sıralı girdidir: iç döngü hiç çalışmaz, maliyet $O(n)$. En kötü durum ters sıralı girdidir: $n(n-1)/2$ kaydırma, $O(n^2)$. Ortalama durumda her eleman sıralı bölümün yarısı kadar kayar; yine karesel ama sabiti küçüktür.

Ters Çift Sayısı

Eklemeli sıralamanın maliyeti, girdinin “ne kadar bozuk” olduğuyla tam olarak ölçülebilir.

Ters çift (inversion), $i < j$ iken $d_i > d_j$ olan çiftlerdir. Sıralı dizide sıfır, ters sıralı dizide $n(n-1)/2$ tanedir.

Eklemeli sıralamanın yaptığı her kaydırma tam olarak bir ters çifti giderir; dolayısıyla toplam kaydırma sayısı ters çift sayısına eşittir ve maliyet $O(n + \text{ters çift})$ olur.

def ters_cift_sayisi(dizi: list[int]) -> int:
    return sum(1 for i in range(len(dizi))
                 for j in range(i + 1, len(dizi)) if dizi[i] > dizi[j])


def eklemeli_kaydirma_sayisi(dizi: list[int]) -> int:
    d, sayac = list(dizi), 0
    for i in range(1, len(d)):
        anahtar, j = d[i], i - 1
        while j >= 0 and d[j] > anahtar:
            d[j + 1] = d[j]
            j -= 1
            sayac += 1
        d[j + 1] = anahtar
    return sayac


for ornek in ([1, 2, 3, 4, 5], [5, 2, 9, 1, 5, 6], [5, 4, 3, 2, 1]):
    print(ornek, ters_cift_sayisi(ornek), eklemeli_kaydirma_sayisi(ornek))

# [1, 2, 3, 4, 5] 0 0
# [5, 2, 9, 1, 5, 6] 6 6
# [5, 4, 3, 2, 1] 10 10

İki sütunun her satırda eşit olması rastlantı değildir; algoritmanın ne yaptığının tam tanımıdır. Sonuç pratikte önemlidir: neredeyse sıralı veride eklemeli sıralama doğrusala yakın çalışır. Sıralı bir kütüğe birkaç yeni kayıt eklenmiş bir dizi bu tanıma girer.

Karşılaştırma

Ölçüt	Kabarcık	Seçmeli	Eklemeli
En iyi durum	$O(n)$ (bayrakla)	$O(n^2)$	$O(n)$
Ortalama / en kötü	$O(n^2)$	$O(n^2)$	$O(n^2)$
Taşıma sayısı	$O(n^2)$	$O(n)$	$O(n^2)$
Kararlı	Evet	Hayır	Evet
Yerinde	Evet	Evet	Evet
Uyarlanabilir	Evet	Hayır	Evet

Üçü de karesel sınıftadır; aralarındaki fark sabitlerde ve ikincil ölçütlerdedir. Pratikte eklemeli sıralama, küçük dizilerde ve neredeyse sıralı veride öne çıkar — bu nedenle gelişmiş sıralama gerçekleştirimleri, küçük parçalarda ona geçer.

Kabarcık sıralamanın belirgin bir üstünlüğü yoktur; öğretici değeri, komşu takas fikrinin en yalın hâli olmasıdır.

Özet

• Sıralama problemi iki koşul ister: çıktı sıralı olmalı ve girdinin bir permütasyonu olmalıdır.
• Algoritmalar kararlılık, yerinde çalışma ve uyarlanabilirlik ölçütleriyle ayrılır; karşılaştırma ve taşıma sayıları ayrı sayılır.
• Kabarcık sıralama komşu takasla çalışır; erken çıkış bayrağı en iyi durumu doğrusala indirir.
• Seçmeli sıralama her zaman karesel karşılaştırma yapar ama doğrusal sayıda taşıma yapar; bu biçimiyle kararlı değildir.
• Eklemeli sıralama kararlı, yerinde ve uyarlanabilirdir; kaydırma sayısı ters çift sayısına eşittir.
• Üçü de karesel sınıftadır; fark sabitlerde ve ikincil ölçütlerdedir.

Sonraki Adım

Karesel sınıf, ölçek büyütme tablosunun gösterdiği gibi milyonluk verilerde kullanılamazdı. Sonraki ders, karmaşıklık hesabı dersinde bağıntısı çözülen böl ve yönet fikrini sıralamaya uygular: birleştirmeli sıralama, $O(n \log n)$ güvencesini kararlılıkla birlikte verir.