Bu derste oyunun haritası 🗺️

Oyun YZ dersinde neden sıralama?

Algoritmalar = oyun YZ’sinin kas sistemi. Önce temel hareketleri öğreneceğiz. 💪

Çoğumuz şöyle yapar: soldan başlarız, her yeni kartı soldaki zaten sıralı kartların arasında doğru yere sokarız.

Tebrikler — az önce insertion sort yaptınız. 🎉

“Algoritma” kelimesi nereden geliyor?

Yıl ~820, Bağdat. Matematikçi el-Harezmî iki ünlü kitap yazar:

Avrupalılar 1. kitabı Latinceye çevirirken yazarın adını “Algoritmi” diye yazar. Zamanla “Harezmî’nin yöntemi” = adım adım hesap yapma yolu anlamına gelir:

Algoritma ve veri yapısı

İkisi birbirinden ayrılmaz: dolap dağınıksa en iyi tarif bile yavaş kalır. Bugünkü veri yapımız en temel olanı: dizi array.

Programlar = Algoritmalar + Veri Yapıları

— Niklaus Wirth’in 1976 tarihli ünlü kitabının adı (Algorithms + Data Structures = Programs).

Mini sözlük (1/2)

Mini sözlük (2/2)

Sıralama problemi

🎒 Ön bilgi: sınıf ve nesne class & object

🎒 Ön bilgi: fonksiyonu değer olarak vermek ve lambda lambda · arrow function

“Neye göre?” — karşılaştırıcı comparator / callback

Hazır sıralama fonksiyonlarına nasıl karşılaştıracağını biz söyleriz. Başka bir fonksiyona verdiğimiz bu küçük fonksiyona geri çağırma callback denir; burada görevi karşılaştırıcı comparator olmak.

enemies.sort(key=lambda e: e.hp)              # canı az olan önce
enemies.sort(key=lambda e: e.hp, reverse=True) # canı çok olan önce
leaderboard.sort(key=lambda p: (-p.score, p.time))  # önce puan, eşitse süre

enemies.Sort((x, y) => x.hp.CompareTo(y.hp));     // canı az olan önce
enemies.Sort((x, y) => y.hp.CompareTo(x.hp));     // canı çok olan önce
// CompareTo: negatif → x önce, 0 → eşit, pozitif → y önce

enemies.sort((x, y) => x.hp - y.hp);   // canı az olan önce
enemies.sort((x, y) => y.hp - x.hp);   // canı çok olan önce

Sıralama algoritması, anahtarın ne olduğunu bilmez; sadece “şu ikisinden hangisi önce?” diye sorar. Bu yüzden aynı algoritma her şeyi sıralayabilir.

🔗 Başka gözle: etkileşimli anlatımlar ve yazılar

Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.

Dizi bellekte nasıl durur? ⚙️

Dizi = bellekte yan yana duran, aynı boyutta kutular. Bu yüzden a[i]’nin adresi tek bir hesapla bulunur:

Maliyet modeli: sadece iki işlem cost model

Kural: sıralama algoritmalarımız diziye sadece iki yardımcı fonksiyonla dokunur:

Neden?

1. Sayabilmek için: Hız = kaç karşılaştırma + kaç yer değiştirme. Saniye bilgisayara göre değişir, bu sayılar değişmez.
2. Genellik için: less’i değiştirirsek aynı kod sayı, metin, düşman, sprite… her şeyi sıralar.

less ve exch kodu

def less(v, w):
    return v < w

def exch(a, i, j):
    a[i], a[j] = a[j], a[i]     # Python'un "demet" (tuple) takası

🎒 C# sekmesindeki <T>: generic — “her tür için” yazılmış fonksiyon; where T : IComparable<T> = “T karşılaştırılabilir bir tür olmalı”. Şimdilik T yerine int düşünebilirsiniz.
Not: Canlı editörlerde görselleştirme için less(a, i, j) biçimini (değer yerine indeks) kullanacağız.

Takas neden üç adım? 🥤 swap

a bardağında kola, b bardağında ayran var. Yerlerini değiştirmek (takas swap) istiyoruz. Üçüncü boş bardak = geçici değişken temporary variable, temp.

Fikir: en küçüğü seç selection sort

İz tablosu trace — S U P E R M A R I O

Selection sort — animasyon

Selection sort — kod

def selection_sort(a):
    n = len(a)
    for i in range(n):                   # i: doldurulacak yer
        min_i = i                        # şimdilik en küçük a[i]
        for j in range(i + 1, n):        # sağ tarafı tara
            if a[j] < a[min_i]:
                min_i = j                # daha küçüğünü bulduk
        a[i], a[min_i] = a[min_i], a[i]  # takas (exch)

Değişmez invariant: neden doğru çalışıyor?

Her turun başında şu iki cümle hep doğrudur:

1. i’nin solundaki elemanlar sıralı ve son yerlerinde.
2. i’nin sağında soldakilerden küçük eleman yok.

Döngü bitince i = N → tüm dizi “solda” → sıralı. ✔ (Buna “doğruluk kanıtı” denir proof of correctness.)

Kaç karşılaştırma? 📐 number of compares

Küçük Gauss ve 1’den 100’e 📜

Selection sort’un karakteri

Peki az takas ne zaman önemli? → Takaslanan şey büyük ya da yazmak pahalıysa. (Birazdan: “perde arkası”)

🧪 Kod laboratuvarı: selection sort

🐍 Aynı laboratuvar — Python

⚙️ Takas ettiğimiz şey ne kadar büyük?

🎮 İç döngü = en yakın düşmanı bulmak

Haritaya tıklayarak büyücüyü taşıyın. Selection sort’un tek bir turu = “en yakın düşman”. K tur = “en yakın K düşman”.

🔗 Ayrıntısı: G2 · Uzaysal Bölümleme (çok düşmanda “en yakın kim?” sorusunu hızlandırmak) sunumunda.

🎮 Hepsini sıralamaya gerek var mı?

🎒 Önceki koddaki yeni ifadeler

🎬 Ara: Selection sort dansı

Select-sort with Gypsy folk dance
AlgoRythmics (Sapientia Üniversitesi, Romanya)

Dansçıların sırtındaki numaralar dizi elemanları. Şapkalı dansçı = min işaretçisi.

🤔 İzlerken sayKaç kez takas oldu? Önerme A ile uyuşuyor mu?

Fikir: kart dizer gibi insertion sort

İz tablosu — S U P E R M A R I O

Insertion sort — animasyon

Insertion sort — kod

def insertion_sort(a):
    for i in range(1, len(a)):            # a[i]'yi solundakilere ekle
        j = i
        while j > 0 and a[j] < a[j - 1]:  # solundaki daha büyükse…
            a[j], a[j - 1] = a[j - 1], a[j]  # …takasla, bir sola geç
            j -= 1

Dikkat: iç döngü, solundaki eleman küçük çıktığı anda durur. Bütün sihir bu erken durmada. ✨

Değişmez invariant

• i’nin solundaki elemanlar kendi aralarında sıralı.
• i’nin sağındaki elemanlara hiç bakılmadı.

Kaç karşılaştırma? Girdiye bağlı!

Ortalama neden N²/4? Rastgele dizide yeni eleman, sıralı kısmın ortalama yarısı kadar sola yürür: en kötünün (N²/2) yarısı.

Ters çift inversion 🔁

Ters çift: dizide yanlış sırada duran her (soldaki, sağdaki) çift. Örn. E A bir ters çifttir.

Insertion sort’un gizli gücü

Kısmen sıralı partially sorted dizi: ters çift sayısı N ile orantılı (az) olan dizi. Örnekler:

• Her eleman, son yerine yakın (kareden kareye biraz kayan sprite’lar 👀)
• Büyük sıralı diziye birkaç yeni eleman eklenmiş (yeni skorlar)
• Sadece birkaç eleman yanlış yerde

Kısmen sıralı dizide insertion sort ≈ doğrusal (N) zamanda çalışır!

🧪 Kod laboratuvarı: insertion sort

İyileştirme: takas yerine kaydır half exchanges

N² bir algoritma… dünyanın en hızlı kütüphanelerinde? 🤯

Neden? Küçük N’de N² ile N log N arasındaki fark önemsiz; insertion sort’un ek yükü yok, kodu minicik ve belleğe komşu komşu erişiyor → CPU önbelleği çok sever.

Ders: “Büyük-O” her şey değildir. Sabitler ve donanım da önemli. → Sonraki slayt.

⚙️ Bellek hiyerarşisi: her “okuma” eşit değil memory hierarchy

Klasik “her programcının bilmesi gereken gecikmeler” (Jeff Dean / Peter Norvig). İnsan ölçeği: 1 ns = 1 saniye olsaydı…

CPU, RAM’den tek bayt istemez: 64 baytlık bir bloğu (önbellek satırı cache line) birden getirir. Komşu elemanlar “bedavaya” gelir.

⚙️ Önbellek cache simülasyonu: dizi vs bağlı liste linked list

Her hücre bir bellek adresi, her satır (8 hücre) bir önbellek satırı. Önbellek sadece 3 satır tutabiliyor. Dizi elemanları yan yana; bağlı liste düğümleri belleğe dağılmış (her düğüm bir sonrakinin adresini tutar).

📜 Stack Overflow’un en ünlü sorusu

🎬 Ara: Insertion sort dansı

Insert-sort with Romanian folk dance
AlgoRythmics

Bir dansçı öne çıkar ve kendinden büyük olanları geçerek sola doğru “dans eder” → iç döngü.

🤔 KarşılaştırSelection dansıyla karşılaştırın: Hangisinde dansçılar daha çok yer değiştiriyor? Hangisinde daha çok “bakışma” (karşılaştırma) var?

Ressam algoritması painter’s algorithm

🎮 Canlı demo: y-sıralama

Zamansal tutarlılık temporal coherence

Oyun dünyası kareden kareye çok az değişir. Önceki karenin cevabı, bu karenin cevabına çok yakındır.

Kodda y-sıralama: Unity · pygame · p5.js

Not: Gerçek projede Unity bunu sizin için yapabilir (2D: Transparency Sort Axis = (0, 1, 0); Godot: Y Sort). Ama arkasındaki fikir tam olarak bu.

🎒 Önceki koddaki yeni ifadeler

⚙️ Çöp toplayıcı garbage collector ve takılan oyunlar

Insertion sort’un zayıf noktası 🐌

En küçük eleman dizinin en sonundaysa, ona yer açmak için herkes teker teker kayar: N−1 takas, hep birer adım.

Fikir: Elemanlar uzak mesafelere tek hamlede atlayabilseydi? 🦘

h-sıralı dizi h-sorted array

Aralarında h adım olan elemanlar (her renk bir grup) kendi aralarında sıralıysa dizi h-sıralıdır.

Shellsort fikri

1. Büyük bir h seç; diziyi h-sırala (her grup için insertion sort, h adımlı atlayarak).
2. h’yi küçült, tekrarla.
3. Son olarak h = 1: normal insertion sort.

🎬 Ara: 15 sıralama algoritması, sesli

İz: S T R E E T F I G H T E R T W O

h dizisi: 13 → 4 → 1 (Knuth’un “3x+1” dizisi: 1, 4, 13, 40, 121, 364, …)

Shellsort — animasyon

Alttaki renkli şerit: aynı renk = aynı h-grubu. h dizisini değiştirip karşılaştırma sayısını izleyin.

Shellsort — kod

def shell_sort(a):
    n = len(a)
    h = 1
    while h < n // 3:
        h = 3 * h + 1               # 1, 4, 13, 40, 121, ...
    while h >= 1:
        for i in range(h, n):       # h adımlı insertion sort
            j = i
            while j >= h and a[j] < a[j - h]:
                a[j], a[j - h] = a[j - h], a[j]
                j -= h
        h //= 3                     # bir sonraki (daha küçük) h
    # h = 1 turu bittiğinde dizi sıralı

Insertion sort’tan farkı: 1 yerine h yazmak + dışarıda bir döngü. Sadece birkaç satır! 😮

Shellsort ne kadar hızlı? 📐

Gerçek hayatta: kodu çok kısa ve ek bellek istemediği için gömülü sistemlerde (ör. uClibc’nin qsort’u) ve bzip2 sıkıştırma programında kullanıldı.

🧪 Kod laboratuvarı: shellsort

🎬 Ara: Shellsort dansı

Shell-sort with Hungarian (Székely) folk dance
AlgoRythmics

Dansçılar önce uzaktaki partnerleriyle eşleşir (büyük h), sonra giderek yakındakilerle (h küçülür).

🤔 İzlerkenVideoda hangi h değerleri kullanılıyor? Son turda kaç takas oluyor — neden bu kadar az?

🏁 Yarış! Önce tahmin edin

N büyüdükçe ne olur? 📈 order of growth

Fareyi grafiğin üzerinde gezdirin. Süreler, saniyede 1 milyar karşılaştırma yapan hayali bir bilgisayar için.

Küçük terimleri neden atıyoruz? tilde notation

\( \dfrac{N(N-1)}{2} = \dfrac{N^2}{2} - \dfrac{N}{2} \)   →   büyük N için \( \sim \dfrac{N^2}{2} \) yazarız. “~” = “yaklaşık, baskın terim”.

🧪 Bilimsel yöntem: iki katına çıkarma deneyi doubling test

Özet tablo 📋

Değerler karşılaştırma sayısıdır (~ anlamında). “Kararlı” sütununu birazdan açıklayacağız.

📜 Peki ya Bubble Sort?

Kabarcık sıralaması bubble sort: komşuları karşılaştır, yanlışsa takasla; büyükler “kabarcık gibi” sona yükselir. En çok bilinen sıralama… ama en kötülerinden biri.

🎤 2007, Google CEO Eric Schmidt, başkan adayı Barack Obama’ya şaka yollu sorar: “Bir milyon 32-bitlik tamsayıyı sıralamanın en verimli yolu nedir?”
Obama: “I think the bubble sort would be the wrong way to go.” 😄

Donald Knuth: “Bubble sort’un, akılda kalıcı bir adı olması dışında önerilecek hiçbir yanı yok gibi görünüyor.”

Barack Obama — Computer Science Question Bubble-sort with Hungarian folk dance — AlgoRythmics

Kararlı sıralama stable sort

Bir sıralama, anahtarı eşit equal keys olan elemanların önceki göreli sırasını koruyorsa kararlıdır.

Kararsız bir algoritma Zeynep’i Mert’in önüne koyabilir — oyuncular forumda isyan eder. 😤

🎮 Envanter: “İsme göre”, sonra “Nadirliğe göre”

Selection sort neden kararsız?

Anahtar = harf. Alt indis sadece “kimin önce geldiğini” takip etmek için: B₁ B₂ A

Uzak mesafeli takas, B₁’i B₂’nin üzerinden atlattı. Insertion sort sadece komşu takası yapar ve eşitleri asla takaslamaz (< kullanır, ≤ değil) → kararlı.

Kullandığınız dil kararlı mı sıralıyor? ⚠️

Knuth karıştırması Fisher–Yates / Knuth shuffle

import random

def shuffle(a):
    for i in range(len(a)):
        r = random.randint(0, i)    # 0..i (i dahil!)
        a[i], a[r] = a[r], a[i]

🎒 Rastgele sayılar: Python random.randint(0, i) → 0…i (i dahil) · C# rng.Next(i + 1) → 0…i (üst sınır hariç) · JS Math.random() → 0 ≤ x < 1 ondalıklı sayı, bu yüzden Math.floor(Math.random() * (i + 1)) → 0…i.

🎲 Deney: hangi karıştırma adil?

Her çubuk bir permütasyonun kaç kez çıktığını gösterir. Adil karıştırmada hepsi kesikli “beklenen” çizgisine yakın olmalı. Çubukların üzerine gelince sayıyı görürsünüz.

📜 Karıştırma hatalarının gerçek bedeli

Kaynaklar: “How We Learned to Cheat at Online Poker” (Arkin ve ark., 1999); Rob Weir, “Doing the Microsoft Shuffle” (2010).

🎮 Tetris’in “7-torba” sistemi 7-bag randomizer

Her parça zar atar gibi rastgele seçilirse uzun çubuk (“I”) onlarca parça boyunca gelmeyebilir 😩. Modern Tetris oyunları 7 parçayı bir torbaya koyar, torbayı karıştırır ve sırayla dağıtır; torba bitince yenisini karıştırır. Böylece iki “I” arasında en fazla 12 parça olur.

A* yol bulmaya bir bakış 🧭

Derin hikâye: Hollerith’in delikli kartları ve 1890 nüfus sayımı

Kaynak: Wikipedia: Herman Hollerith · Wikipedia: Radix sort

🧰 Kütüphaneler ve araçlar

🧩 Oyunlarda sıralama

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

🚀 Proje ve araştırma önerileri

1. [kolay] Sıralama görselleştirici — p5.js’te dört temel sıralamayı aynı veriyle yarıştırın; karşılaştırma ve takas sayısını gösterin.
2. [kolay] Liderlik tablosu — Çok anahtarlı, kararlı sıralama + ikili aramayla ekleme.
3. [orta] Neredeyse sıralı veri — Her kare biraz karışan 1.000 düşman listesinde ekleme sıralaması ile Array.Sort’u ölçün.
4. [araştırma] Yanlı karıştırma — Rastgele karşılaştırıcıyla 1 milyon karıştırma yapıp her elemanın konum dağılımını çizin; Fisher–Yates ile karşılaştırın.

📄 Akademik okumalar ve kaynaklar

Neler öğrendik? 🎒

Alıştırmalar 🏋️

1. Bubble sort’u son slayttaki laboratuvarda yazın, erken çıkış (swapped) ekleyin. Sıralı / ters / rastgele girdide insertion sort ile karşılaştırın.
2. p5.js’te y-sıralama yapan küçük bir sahne yazın (ağaçlar + hareket eden karakter). Her karede kaç karşılaştırma yaptığınızı ekrana yazdırın.
3. Unity’de 10 oyunculu bir skor tablosu: puan eşitse önce bitiren önde. Hem List.Sort + ikinci anahtar, hem kararlı insertion sort ile yapın.
4. Kağıt-kalem: E A S Y Q U E S T I O N dizisi için selection ve insertion sort’un iz tablosunu çıkarın. Kaç ters çift var?
5. 🤖 Bir YZ asistanından “C#’ta insertion sort” isteyin. Kodun değişmezini bulun ve doğru olduğunu kendi cümlelerinizle açıklayın.

🧪 Serbest laboratuvar

🐍 Serbest laboratuvar — Python

🎮 Bu sunumdaki oyunlar

Adı geçen oyunu tanımıyorsanız: oyuncuların kullandığı wiki sayfası ve oyunu kısaca gösteren bir video. ▶ video slaydın üstünde açılır (Esc ile kapanır); 🎯 işaretli bağlantılar doğrudan bu sunumdaki konuya gider.

Kaynaklar: videolar 🎬

15 Sorting Algorithms in 6 Minutes
Timo Bingmann — sesli görselleştirme Getting Sorted & Big O Notation
Computerphile Selection Sort
CS50 Shorts (Harvard) Insertion Sort
CS50 (Harvard) Selection sort in 3 minutes
Michael Sambol Insertion sort in 2 minutes
Michael Sambol Insertion sort algorithm
mycodeschool AlgoRythmics dans serisi
(insertion, selection, shell, bubble…)

Kaynaklar: okuma ve görselleştirme 📚