Temel sıralama tasarımı

Sıralama, veriyi belirli bir ölçüte göre düzenleme işlemidir. Sayıları küçükten büyüğe, öğrencileri nota göre, ürünleri fiyata göre sıralayabiliriz. Python bu işi çok güçlü yerleşik araçlarla yapar; ancak bu hafta önce bir sıralama algoritmasının nasıl düşündüğünü görünür hâle getireceğiz.

Çekirdek uygulamamız insertion sort olacaktır. Selection sort ve bubble sort ise kod izleme ve karşılaştırma düzeyinde ele alınacaktır.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

sıralama probleminin girdisini ve ölçütünü açıklayabilmeli,
insertion sort algoritmasını uygulayabilmeli,
ara durumları izleyerek algoritmanın nasıl ilerlediğini gösterebilmeli,
insertion sort’un sıralı, ters sıralı ve yaklaşık sıralı veride farklı miktarda iş yapabildiğini açıklayabilmeli,
selection ve bubble sort yaklaşımlarını temel fikir düzeyinde karşılaştırabilmeli,
karşılaştırma ve yer değiştirme kavramlarını ayırt edebilmeli,
yerinde sıralama (in-place), kararlılık (stability) ve adaptive davranış kavramlarını tanıma düzeyinde açıklayabilmeli,
temel karesel sıralamaların en kötü durumda neden O(n²) sezgisi taşıdığını açıklayabilmelisiniz.

2 Sıralama neyi değiştirir?

#| edit: false
#| completion: false
values = [7, 3, 9, 1, 5]
print("Başlangıç:", values)

Bir sıralama algoritması sonunda şu düzeni üretmek isteyebilir:

[1, 3, 5, 7, 9]

Ancak asıl öğrenme hedefimiz son liste değildir. Soru şudur:

Algoritma bu düzene hangi ara adımlarla ulaşıyor?

3 Insertion sort sezgisi

Insertion sort’u elde tuttuğunuz iskambil kâğıtlarını sıraya sokmaya benzetebilirsiniz:

soldaki bölümün sıralı olduğunu kabul et,
sıradaki elemanı al,
soldaki sıralı bölümde doğru konuma yerleştir,
tüm elemanlar bitene kadar devam et.

flowchart LR
    A["[3] | 7 4 2"] --> B["[3 7] | 4 2"]
    B --> C["[3 4 7] | 2"]
    C --> D["[2 3 4 7]"]

Dikey çizginin solu her adımda sıralı bölgeyi temsil eder.

4 Insertion sort kodu

#| edit: false
#| completion: false
def insertion_sort(values):
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1

        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]
            j -= 1

        values[j + 1] = current

    return values

numbers = [7, 3, 9, 1, 5]
print(insertion_sort(numbers))

Bu fonksiyon verilen listeyi yerinde değiştirir. Ayrıca okunabilirlik için aynı listeyi döndürüyoruz.

5 Ara durumları izleyelim

#| edit: false
#| completion: false
def insertion_sort_trace(values):
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1

        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]
            j -= 1

        values[j + 1] = current
        print(f"Tur {i}:", values)

values = [8, 4, 6, 2, 5]
insertion_sort_trace(values)

Çalıştırmadan önce her turun sonunda listenin nasıl görüneceğini tahmin etmeye çalışın.

6 Neden `current` değişkeni gerekli?

Şu anda yerleştirmek istediğimiz değeri geçici olarak saklamazsak, elemanları sağa kaydırırken onu ezebiliriz. current, yerleştirilecek değeri güvenli biçimde tutar.

7 Alıştırma — insertion sort’u tamamla

#| exercise: hafta09-insertion
#| completion: false
#| persist: true
def insertion_sort(values):
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1

        while j >= 0 and values[j] > current:
            # soldaki büyük elemanı sağa kaydırın
            pass

        # current değerini doğru konuma yazın

    return values

print(insertion_sort([5, 2, 4, 1, 3]))

#| exercise: hafta09-insertion
#| check: true
scope = {}
try:
    exec(user_code, scope)
    fn = scope.get("insertion_sort")
    correct = (
        callable(fn)
        and fn([5, 2, 4, 1, 3]) == [1, 2, 3, 4, 5]
        and fn([]) == []
        and fn([1]) == [1]
        and fn([3, 3, 1]) == [1, 3, 3]
        and fn([1, 2, 3]) == [1, 2, 3]
    )
except Exception:
    correct = False

feedback = (
    {"correct": True, "message": "Insertion sort farklı sınır durumlarında doğru çalışıyor."}
    if correct
    else {"correct": False, "message": "Döngü içinde values[j + 1] = values[j] ve j -= 1 kullanın; döngüden sonra current değerini values[j + 1] konumuna yerleştirin."}
)
feedback

Kaydırma yaptıktan sonra j değerini azaltmayı unutmayın. while bittikten sonra current için doğru konum j + 1 olacaktır.

Solution.

def insertion_sort(values):
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1

        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]
            j -= 1

        values[j + 1] = current

    return values

8 Aynı algoritma her girdide aynı işi yapmaz

Insertion sort’un önemli bir özelliği, verinin başlangıç düzenine duyarlı olmasıdır.

8.1 Zaten sıralı veri

[1, 2, 3, 4, 5, 6]

Her current değeri zaten doğru taraftadır. while koşulu çoğu turda hemen başarısız olur; neredeyse hiç kaydırma yapılmaz. Bu durumda yapılan iş yaklaşık doğrusal büyür ve en iyi durum O(n) olarak düşünülebilir.

8.2 Ters sıralı veri

[6, 5, 4, 3, 2, 1]

Her yeni eleman soldaki sıralı bölümün neredeyse tamamından geçirilir. Çok sayıda karşılaştırma ve kaydırma gerekir. Bu, en kötü durum O(n²) davranışına örnektir.

8.3 Yaklaşık sıralı veri

[1, 2, 4, 3, 5, 6]

Yalnızca birkaç eleman yanlış yerdeyse insertion sort az sayıda kaydırmayla işi bitirebilir. Bu nedenle insertion sort için adaptive terimi kullanılır: girdi zaten kısmen düzenliyse bundan yararlanabilir.

Important

“Insertion sort O(n²)’dir” cümlesi tek başına eksik kalır. Bu derste daha doğru ifade şudur: en kötü durumda O(n²), zaten sıralı en iyi durumda O(n); yapılan gerçek iş verinin başlangıç düzeninden etkilenebilir.

9 İşlem sayısını veri düzenine göre karşılaştıralım

#| edit: false
#| completion: false
def insertion_counts(values):
    values = values.copy()
    comparisons = 0
    shifts = 0

    for i in range(1, len(values)):
        current = values[i]
        j = i - 1

        while j >= 0:
            comparisons += 1
            if values[j] <= current:
                break
            values[j + 1] = values[j]
            shifts += 1
            j -= 1

        values[j + 1] = current

    return comparisons, shifts

samples = {
    "sıralı": [1, 2, 3, 4, 5, 6, 7, 8],
    "yaklaşık sıralı": [1, 2, 3, 5, 4, 6, 7, 8],
    "ters": [8, 7, 6, 5, 4, 3, 2, 1],
}

for name, data in samples.items():
    print(name, "->", insertion_counts(data))

Çıktıda özellikle kaydırma sayısına dikkat edin. Aynı n değeri için bile girdi düzeni yapılan işi ciddi biçimde değiştirebilir.

10 Selection sort fikri

Selection sort’un temel yaklaşımı farklıdır:

sıralanmamış bölümde en küçük elemanı bul,
onu sıradaki doğru konumla değiştir,
kalan bölüm için tekrarla.

#| edit: false
#| completion: false
def selection_sort_trace(values):
    for i in range(len(values) - 1):
        min_index = i

        for j in range(i + 1, len(values)):
            if values[j] < values[min_index]:
                min_index = j

        values[i], values[min_index] = values[min_index], values[i]
        print(f"Tur {i + 1}:", values)

values = [8, 4, 6, 2, 5]
selection_sort_trace(values)

Insertion sort kaydırarak doğru konuma yerleştirirken selection sort önce minimumu seçer.

11 Bubble sort fikri

Bubble sort komşu elemanları karşılaştırır ve yanlış sıradaysa yer değiştirir. Büyük değerler her turda sağ tarafa doğru ilerler:

#| edit: false
#| completion: false
def bubble_sort_trace(values):
    n = len(values)

    for pass_no in range(n - 1):
        for i in range(n - 1 - pass_no):
            if values[i] > values[i + 1]:
                values[i], values[i + 1] = values[i + 1], values[i]

        print(f"Tur {pass_no + 1}:", values)

values = [8, 4, 6, 2, 5]
bubble_sort_trace(values)

Bu derste bubble sort’u ezberlemeniz beklenmez. Verilen kodda ara durumları okuyup algoritmanın “komşu karşılaştırma ve swap” fikrini açıklayabilmeniz yeterlidir.

12 Karşılaştırma ve yer değiştirme aynı şey değildir

Selection sort bir turda çok sayıda karşılaştırma yapabilir fakat sonunda yalnızca bir temel swap yapar. Bubble sort ise aynı turda birden çok swap yapabilir. Bu nedenle yalnızca “kaç döngü var?” değil, hangi işlemlerin kaç kez gerçekleştiği de önemlidir.

13 İşlem sayısını gözlemlemek

#| edit: false
#| completion: false
def selection_counts(values):
    values = values.copy()
    comparisons = 0
    swaps = 0

    for i in range(len(values) - 1):
        min_index = i
        for j in range(i + 1, len(values)):
            comparisons += 1
            if values[j] < values[min_index]:
                min_index = j

        if min_index != i:
            values[i], values[min_index] = values[min_index], values[i]
            swaps += 1

    return comparisons, swaps

for n in [5, 10, 20]:
    data = list(range(n, 0, -1))
    print(n, selection_counts(data))

Veri boyutu iki katına çıktığında karşılaştırma sayısının yaklaşık dört kat büyüme eğilimini gözlemleyebilirsiniz. Bu, O(n²) sezgisidir.

14 Neden O(n²)?

Selection sort gibi bazı temel sıralamalarda kabaca şöyle bir yapı vardır:

n eleman için yaklaşık n tur
her turda yaklaşık n karşılaştırma
→ yaklaşık n × n = n²

Insertion sort’un en kötü durumu da benzer karesel büyümeye ulaşabilir; ancak az önce gördüğümüz gibi başlangıç düzeni burada daha belirgin rol oynar.

15 Yerinde sıralama (in-place)

Bir algoritma, ana veriyi aynı liste üzerinde düzenliyor ve boyutla birlikte büyüyen ayrı bir sonuç listesi oluşturmuyorsa genellikle in-place olarak anılır.

Insertion sort örneğimiz:

numbers = [4, 2, 3]
insertion_sort(numbers)

sonrasında numbers listesinin kendisini değiştirmiştir.

Bu davranışın yan etkisini unutmayın:

#| edit: false
#| completion: false
numbers = [4, 2, 3]
backup = numbers
insertion_sort(numbers)

print(numbers)
print(backup)

backup aynı listeyi gösteriyorsa o da sıralanmış görünür. Bağımsız orijinal veri gerekiyorsa önce kopya alın.

16 Kararlılık (stability) sezgisi

Aynı sıralama anahtarına sahip kayıtların önceki göreli sırasının korunmasına kararlı sıralama denir.

Örneğin:

(Ayşe, 80)   önce
(Bora, 90)
(Cem, 80)    sonra

Notlara göre artan sıralamada Ayşe ile Cem’in ikisi de 80’dir. Kararlı sıralama, Ayşe’nin Cem’den önceki konumunu korur.

Bizim insertion sort koşulumuz:

while j >= 0 and values[j] > current:

şeklindedir. Eşit değerlerde > koşulu yanlış olur ve soldaki eşit eleman gereksiz yere sağa taşınmaz. Bu, kararlılığı korumaya yardımcı olur.

Eğer karşılaştırmayı düşünmeden >= yaparsak eşit anahtarlı öğeleri de kaydırmaya başlayabilir ve önceki göreli sıralarını bozabiliriz.

16.1 Kararlılığı görünür kılalım

Aşağıdaki küçük sürüm yalnızca grade alanına göre sıralıyor:

#| edit: false
#| completion: false
def stable_insertion_by_grade(records):
    records = records.copy()

    for i in range(1, len(records)):
        current = records[i]
        j = i - 1

        while j >= 0 and records[j]["grade"] > current["grade"]:
            records[j + 1] = records[j]
            j -= 1

        records[j + 1] = current

    return records

records = [
    {"name": "Ayşe", "grade": 80},
    {"name": "Bora", "grade": 90},
    {"name": "Cem", "grade": 80},
]

for record in stable_insertion_by_grade(records):
    print(record)

Ayşe ve Cem’in notları eşit olduğu hâlde başlangıçtaki göreli sıraları korunur.

17 Tahmin et — hangi girdi daha az iş yaptırır?

Aşağıdaki üç listeyi insertion sort ile sıraladığınızı düşünün. Çalıştırmadan önce en az kaydırmadan en çok kaydırmaya doğru sıralayın:

A = [1, 2, 3, 4, 5]
B = [1, 2, 4, 3, 5]
C = [5, 4, 3, 2, 1]

Beklenen sezgi:

A → en az iş
B → arada
C → en çok iş

Bu soru, karmaşıklığın yalnızca n değerinden değil, bazı algoritmalarda girdinin düzeninden de etkilendiğini hatırlatır.

18 Algoritmaların temel karakteri

Algoritma	Ana fikir	Veri düzenine duyarlılık	Bu dersteki düzey
insertion sort	sıradaki öğeyi sıralı bölgeye yerleştir	belirgin; yaklaşık sıralı veriden yararlanır	uygulama
selection sort	kalanların en küçüğünü seç	karşılaştırma sayısı başlangıç düzeninden az etkilenir	kod izleme
bubble sort	komşuları karşılaştır ve değiştir	sürüme göre erken durma eklenebilir	kod izleme

19 Bölüm özeti

Sıralama, veriyi belirli bir ölçüte göre düzenler.
Insertion sort solda büyüyen sıralı bölge oluşturur.
Insertion sort zaten sıralı veride yaklaşık O(n), en kötü durumda O(n²) davranışı gösterebilir.
Yaklaşık sıralı veriden yararlanabildiği için insertion sort adaptive bir algoritma örneğidir.
Selection sort her turda kalan bölümün minimumunu seçer.
Bubble sort komşu elemanları karşılaştırır.
Basit sıralama algoritmalarını yalnızca tek bir Big-O etiketiyle değil, girdi düzeni ve yapılan işlem türleriyle birlikte düşünmek gerekir.
In-place sıralama mevcut listeyi değiştirir.
Kararlılık, eşit anahtarlı kayıtların göreli sırasının korunmasıdır; insertion sort’taki > karşılaştırması bu davranışı korumaya yardımcı olur.

20 Kendinizi kontrol edin

Insertion sort’ta “sıralı bölüm” hangi tarafta büyür?
Zaten sıralı veri insertion sort için neden daha kolaydır?
Ters sıralı veri neden çok sayıda kaydırma oluşturur?
adaptive sözcüğü insertion sort bağlamında ne anlatır?
Selection sort’un ana seçimi nedir?
Bubble sort hangi elemanları karşılaştırır?
In-place sıralamanın aliasing açısından oluşturabileceği yan etki nedir?
Kararlı sıralama neyi korur ve > ile >= arasındaki fark neden önemli olabilir?

1 Bu hafta neleri yapabilmelisiniz?

2 Sıralama neyi değiştirir?

3 Insertion sort sezgisi

4 Insertion sort kodu

5 Ara durumları izleyelim

6 Neden current değişkeni gerekli?

7 Alıştırma — insertion sort’u tamamla

8 Aynı algoritma her girdide aynı işi yapmaz

8.1 Zaten sıralı veri

8.2 Ters sıralı veri

8.3 Yaklaşık sıralı veri

9 İşlem sayısını veri düzenine göre karşılaştıralım

10 Selection sort fikri

11 Bubble sort fikri

12 Karşılaştırma ve yer değiştirme aynı şey değildir

13 İşlem sayısını gözlemlemek

14 Neden O(n²)?

15 Yerinde sıralama (in-place)

16 Kararlılık (stability) sezgisi

16.1 Kararlılığı görünür kılalım

17 Tahmin et — hangi girdi daha az iş yaptırır?

18 Algoritmaların temel karakteri

19 Bölüm özeti

20 Kendinizi kontrol edin

6 Neden `current` değişkeni gerekli?