Döngüsel Yerleştirme

Önceki kalıp sıralamanın bedelini ödeyip karşılığında tek geçiş aldı. Bu dersin kalıbı sıralamayı bütünüyle atlar. Fikri tek cümledir: değer, gideceği yeri kendisi söylüyorsa karşılaştırmaya gerek yoktur. Değerler 1 ile n arasındaysa, v değerinin yeri v-1 konumudur; her değer doğrudan evine gönderilir ve evden çıkan değer sıradaki gönderiyi belirler.

Karşılığında ödenen şey ağır bir ön koşuldur ve aslında iki ayrı ön koşuldur: değerler 1 ile n arasında olmalı, ve değerler tekrarsız olmalı. Bu ders ikisini ayrı ayrı bozar, çünkü bozulmalarının sonucu da ayrıdır: biri yanlış yanıt üretir, öbürü hiç yanıt üretmez.

Kalıbın Fikri ve İki Ön koşulu

Kalıp bir konumda durur ve oradaki değere bakar. Değer evinde değilse, değeri evine gönderir; evden çıkan yeni değer aynı konuma düşer ve aynı işlem yinelenir. Değer evindeyse bir sonraki konuma geçilir. Her takas en az bir değeri kalıcı olarak evine koyduğu için toplam takas sayısı n’i aşamaz.

Bu sayının güvencesi doğrudan ön koşuldan gelir. Bir değer evine gönderildiğinde orada başka bir değer varsa, o değer farklı olmalıdır; aksi hâlde takas hiçbir şeyi ilerletmez ve aynı iki değer sonsuza kadar yer değiştirir.

PK32. Dizi 12 değerlidir ve hedef aralık 1..12’dir; tohum 20260218. PK33. Üç öbek vardır ve üçü de aynı üreteçten gelir: 1..n yerleşimi (tekrarsız ve aralık içi), tekrarlı değerler, ve iki değeri aralık dışına taşınmış diziler. PK34. Kâhin, Algoritmalar kursunda ölçülen karşılaştırmalı yordamlardan birini kullanır ve her karşılaştırmayı bir adım sayar. Yordamın kendisi burada tekrarlanmaz. PK35. Kalıba bir adım sınırı konur (400 adım). Sınıra dayanan koşum durmadi döndürür ve kâhinden ayrılmış sayılır.

TOHUM, UZUNLUK, DAGARCIK = 20260218, 12, 40


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def deger_dagarcik(tohum=TOHUM, n=DAGARCIK, uzunluk=UZUNLUK):
    """Uc obek: 1..n yerlesimi; tekrarli degerler; aralik disi deger tasiyanlar."""
    r = uretec(tohum)
    kume = []
    for i in range(n):
        yerlesim = list(range(1, uzunluk + 1))
        for j in range(uzunluk, 1, -1):
            k = r(j)
            yerlesim[j - 1], yerlesim[k] = yerlesim[k], yerlesim[j - 1]
        tekrarli = [r(uzunluk) + 1 for _ in range(uzunluk)]
        disarili = list(yerlesim)
        for _ in range(2):
            disarili[r(uzunluk)] = uzunluk + 2 + r(uzunluk)
        kume.append({"no": i + 1, "yerlesim": yerlesim,
                     "tekrarli": tekrarli, "disarili": disarili})
    return kume


class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def kahin_yerlesim(dizi, s):
    """Karsilastirmali secmeli yerlestirme. Her zaman dogru, her zaman pahali."""
    a = list(dizi)
    for i in range(len(a)):
        en = i
        for j in range(i + 1, len(a)):
            s.say()
            if a[j] < a[en]:
                en = j
        a[i], a[en] = a[en], a[i]
    return a


def kalip_yalin(dizi, s, sinir=400):
    """ONKOSUL: degerler 1..n araliginda ve TEKRARSIZ olmali."""
    a, n = list(dizi), len(dizi)
    i = 0
    while i < n:
        s.say()
        if s.adim > sinir:
            return "durmadi"
        h = a[i] - 1
        if 0 <= h < n and h != i:
            a[i], a[h] = a[h], a[i]
        else:
            i += 1
    return a


def kalip_korumali(dizi, s, sinir=400):
    """Tekrar korumasi eklendi: evdeki deger ayniysa takas edilmez."""
    a, n = list(dizi), len(dizi)
    i = 0
    while i < n:
        s.say()
        if s.adim > sinir:
            return "durmadi"
        h = a[i] - 1
        if 0 <= h < n and a[i] != a[h]:
            a[i], a[h] = a[h], a[i]
        else:
            i += 1
    return a


OBEK = (("1..n yerlesimi     ", "yerlesim"),
        ("tekrarli deger     ", "tekrarli"),
        ("aralik disi deger  ", "disarili"))

K = deger_dagarcik()
print("dagarcik:", len(K), "dizi x", UZUNLUK, "deger | ornekler:")
print("  yerlesim:", K[0]["yerlesim"])
print("  tekrarli:", K[0]["tekrarli"])
print("  disarili:", K[0]["disarili"])
print()
print("kalip      obek                 ayrilan/40  kalip  kahin   oran")
for kad, kalip in (("yalin    ", kalip_yalin), ("korumali ", kalip_korumali)):
    for ad, anahtar in OBEK:
        ayrilan, ak, ah = 0, 0, 0
        for k in K:
            s1, s2 = Sayac(), Sayac()
            a = kalip(k[anahtar], s1)
            b = kahin_yerlesim(k[anahtar], s2)
            ak, ah = ak + s1.adim, ah + s2.adim
            ayrilan += (a != b)
        print(f"{kad}  {ad}  {ayrilan:8d}  {ak:5d}  {ah:5d}  {ah / ak:5.2f}")

dagarcik: 40 dizi x 12 deger | ornekler:
  yerlesim: [5, 9, 3, 4, 7, 10, 1, 12, 11, 2, 6, 8]
  tekrarli: [3, 4, 1, 2, 3, 4, 5, 6, 7, 12, 9, 2]
  disarili: [5, 9, 3, 4, 7, 18, 1, 12, 11, 2, 6, 16]

kalip      obek                 ayrilan/40  kalip  kahin   oran
yalin      1..n yerlesimi              0    826   2640   3.20
yalin      tekrarli deger             40  16040   2640   0.16
yalin      aralik disi deger          40    801   2640   3.30
korumali   1..n yerlesimi              0    826   2640   3.20
korumali   tekrarli deger             39    750   2640   3.52
korumali   aralik disi deger          40    801   2640   3.30

Birinci satır kalıbın vaadidir: 40 girdinin 40’ında kâhinle aynı yerleşim, 826 adıma karşı 2640, oran 3,20. Karşılaştırma hiç yapılmadığı hâlde sonuç doğrudur.

İkinci satır, bu konudaki en uç sonucu taşıyor. Tekrarlı değerlerde yalın kalıp 16.040 adım harcıyor ve oran 0,16’ya düşüyor — kâhinden altı kat pahalı. Bu sayı bir yavaşlama değil, bir durmama ölçüsüdür: 40 girdinin 40’ı da 400 adımlık sınıra dayanıyor. Sınır konmasaydı ilk girdide ölçüm biterdi ve hiç sonuç alınamazdı.

Üçüncü satır bambaşka bir kusuru gösteriyor. Aralık dışı değerlerde kalıp 801 adımda biriyor, oran 3,30 — birinci satırdan bile hızlı — ve 40 girdinin 40’ında yanlış. Aralık dışı bir değerin evi yoktur; kalıp onu olduğu yerde bırakıp ilerler ve geriye kalan yerleşim kâhinin ürettiğinden farklı olur. Hiçbir uyarı, hiçbir gecikme, hiçbir belirti yoktur.

Koruma Durmamayı Çözer, Yanlışı Çözmez

Sonsuz takası durduran değişiklik tek bir karşılaştırmadır: değeri evine göndermeden önce evde aynı değerin olup olmadığına bakmak. Aynıysa gönderim anlamsızdır ve konum ilerletilir.

def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def deger_dagarcik(tohum, n=40, uzunluk=12):
    r = uretec(tohum)
    kume = []
    for i in range(n):
        yerlesim = list(range(1, uzunluk + 1))
        for j in range(uzunluk, 1, -1):
            k = r(j)
            yerlesim[j - 1], yerlesim[k] = yerlesim[k], yerlesim[j - 1]
        tekrarli = [r(uzunluk) + 1 for _ in range(uzunluk)]
        disarili = list(yerlesim)
        for _ in range(2):
            disarili[r(uzunluk)] = uzunluk + 2 + r(uzunluk)
        kume.append({"yerlesim": yerlesim, "tekrarli": tekrarli,
                     "disarili": disarili})
    return kume


def kahin_yerlesim(dizi):
    a = list(dizi)
    for i in range(len(a)):
        en = i
        for j in range(i + 1, len(a)):
            if a[j] < a[en]:
                en = j
        a[i], a[en] = a[en], a[i]
    return a


def kalip(dizi, koruma, sinir=400):
    a, n, i, adim = list(dizi), len(dizi), 0, 0
    while i < n:
        adim += 1
        if adim > sinir:
            return "durmadi"
        h = a[i] - 1
        if 0 <= h < n and ((a[i] != a[h]) if koruma else (h != i)):
            a[i], a[h] = a[h], a[i]
        else:
            i += 1
    return a


ornek = deger_dagarcik(20260218)[0]
print("tekrarli girdi:", ornek["tekrarli"])
print("  yalin kalip   :", kalip(ornek["tekrarli"], False))
print("  korumali kalip:", kalip(ornek["tekrarli"], True))
print("  kahin         :", kahin_yerlesim(ornek["tekrarli"]))
print()
print("tohum      kalip     obek       ayrilan/40   oran")
for tohum in (20260218, 20260219):
    K = deger_dagarcik(tohum)
    for kad, koruma in (("yalin   ", False), ("korumali", True)):
        for anahtar in ("yerlesim", "tekrarli", "disarili"):
            ayrilan = sum(1 for k in K
                          if kalip(k[anahtar], koruma) != kahin_yerlesim(k[anahtar]))
            print(f"{tohum}  {kad}  {anahtar:9s}  {ayrilan:8d}   {ayrilan / 40:.4f}")

tekrarli girdi: [3, 4, 1, 2, 3, 4, 5, 6, 7, 12, 9, 2]
  yalin kalip   : durmadi
  korumali kalip: [1, 2, 3, 4, 5, 6, 7, 4, 9, 2, 3, 12]
  kahin         : [1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 9, 12]

tohum      kalip     obek       ayrilan/40   oran
20260218  yalin     yerlesim          0   0.0000
20260218  yalin     tekrarli         40   1.0000
20260218  yalin     disarili         40   1.0000
20260218  korumali  yerlesim          0   0.0000
20260218  korumali  tekrarli         39   0.9750
20260218  korumali  disarili         40   1.0000
20260219  yalin     yerlesim          0   0.0000
20260219  yalin     tekrarli         40   1.0000
20260219  yalin     disarili         39   0.9750
20260219  korumali  yerlesim          0   0.0000
20260219  korumali  tekrarli         40   1.0000
20260219  korumali  disarili         39   0.9750

Örnek girdi mekanizmayı açıkça gösteriyor. Yalın kalıp durmadi döndürüyor. Korumalı kalıp duruyor ve [1, 2, 3, 4, 5, 6, 7, 4, 9, 2, 3, 12] üretiyor; kâhinin yanıtı [1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 9, 12]. İkisi aynı değil — koruma durmamayı çözdü, yanlışı çözmedi. Ayrılan girdi 40’tan 39’a indi; bu, çözünürlük kuralına göre ölçülmemiş sayılacak bir fark bile değildir, çünkü aynı büyüklükte kalmıştır.

PK36. İkinci dağarcık 20260219 tohumundan gelir. On iki satırın on ikisinde ayrılan girdi ya 0 ya 39–40’tır; sonuç dağarcığa bağlı değildir. PK37. 40 girdide 39 ile 40 arasındaki fark ölçülmemiş sayılır; iki dağarcık arasındaki yer değiştirmeler (tekrarlıda 39/40, aralık dışında 40/39) bu nedenle bir eğilim değildir.

Ön koşul Kalıba Değil, Kalıp–Soru Çiftine Aittir

Buraya kadar tek bir soru soruldu: yerleşimin kendisi ne olacak. Aynı kalıp, aynı bozuk girdilerle, başka bir soruya yanıt vermek için de kullanılır: 1..n aralığından hangi değerler eksik. Bu soruda kalıp yerleşimi bir amaç olarak değil, bir ara ürün olarak kullanır; evinde olmayan konumlar doğrudan eksik değerleri verir.

PK38. Bu ölçümde kalıp korumalı biçimdir ve yanıt, evinde olmayan konumların listesidir. Kâhin her değeri diziyi tarayarak arar. PK39. Soru değişti; kalıp, kâhin, dağarcık ve tohum değişmedi.

def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def deger_dagarcik(tohum, n=40, uzunluk=12):
    r = uretec(tohum)
    kume = []
    for i in range(n):
        yerlesim = list(range(1, uzunluk + 1))
        for j in range(uzunluk, 1, -1):
            k = r(j)
            yerlesim[j - 1], yerlesim[k] = yerlesim[k], yerlesim[j - 1]
        tekrarli = [r(uzunluk) + 1 for _ in range(uzunluk)]
        disarili = list(yerlesim)
        for _ in range(2):
            disarili[r(uzunluk)] = uzunluk + 2 + r(uzunluk)
        kume.append({"yerlesim": yerlesim, "tekrarli": tekrarli,
                     "disarili": disarili})
    return kume


class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def kahin_eksik(dizi, s):
    """1..n arasindaki her degeri diziyi tarayarak arar."""
    eksik = []
    for v in range(1, len(dizi) + 1):
        bulundu = False
        for x in dizi:
            s.say()
            if x == v:
                bulundu = True
                break
        if not bulundu:
            eksik.append(v)
    return eksik


def kalip_eksik(dizi, s, sinir=400):
    """Once yerlestirir, sonra evinde olmayan konumlari toplar."""
    a, n = list(dizi), len(dizi)
    i = 0
    while i < n:
        s.say()
        if s.adim > sinir:
            return "durmadi"
        h = a[i] - 1
        if 0 <= h < n and a[i] != a[h]:
            a[i], a[h] = a[h], a[i]
        else:
            i += 1
    eksik = []
    for j in range(n):
        s.say()
        if a[j] != j + 1:
            eksik.append(j + 1)
    return eksik


print("tohum      obek       ayrilan/40  kalip  kahin   oran")
for tohum in (20260218, 20260219):
    K = deger_dagarcik(tohum)
    for anahtar in ("yerlesim", "tekrarli", "disarili"):
        ayrilan, ak, ah = 0, 0, 0
        for k in K:
            s1, s2 = Sayac(), Sayac()
            a = kalip_eksik(k[anahtar], s1)
            b = kahin_eksik(k[anahtar], s2)
            ak, ah = ak + s1.adim, ah + s2.adim
            ayrilan += (a != b)
        print(f"{tohum}  {anahtar:9s}  {ayrilan:8d}  {ak:5d}  {ah:5d}"
              f"  {ah / ak:5.2f}")
print()
K = deger_dagarcik(20260218)
print("ornek aralik disi dizi:", K[0]["disarili"])
print("  kalip eksik:", kalip_eksik(K[0]["disarili"], Sayac()))
print("  kahin eksik:", kahin_eksik(K[0]["disarili"], Sayac()))

tohum      obek       ayrilan/40  kalip  kahin   oran
20260218  yerlesim          0   1306   3120   2.39
20260218  tekrarli          0   1230   3531   2.87
20260218  disarili          0   1281   3536   2.76
20260219  yerlesim          0   1313   3120   2.38
20260219  tekrarli          0   1233   3525   2.86
20260219  disarili          0   1294   3548   2.74

ornek aralik disi dizi: [5, 9, 3, 4, 7, 18, 1, 12, 11, 2, 6, 16]
  kalip eksik: [8, 10]
  kahin eksik: [8, 10]

Altı satırın altısında ayrılan girdi sıfır. Aynı kalıp, aynı tekrarlı ve aralık dışı girdiler, iki dağarcık — ve hiçbir ayrılma yok. Bir önceki tabloda 39 ve 40 yazan satırlar burada 0 yazıyor.

Değişen tek şey sorudur. “Yerleşim ne olacak” sorusu, dizinin bütün değerlerinin bir eve sahip olmasını gerektirir; “hangi değerler eksik” sorusu bunu gerektirmez, çünkü evsiz bir değerin nerede durduğu yanıtı etkilemez. Kalıbın ön koşulu, kalıbın kendi kodunda değil, kalıbın hangi soruya yanıt verdiğinde yatar.

Buradan çıkan kural, konunun tamamı için geçerlidir: bir kalıbın ön koşulu, kalıbın adı sorulduğunda değil, sorulan soru sabitlendiğinde tanımlanır. “Döngüsel yerleştirme tekrarlı değerle çalışmaz” cümlesi bu tabloda yanlıştır; doğru cümle, “döngüsel yerleştirme tekrarlı değerle yerleşim sorusuna doğru yanıt vermez” cümlesidir.

Üç Sayı

Ölçüt	Kâhin	Kalıp	Ayrılan girdi
Yerleşim, 1..n değerleri	2640 adım	826 adım	0/40
Yerleşim, tekrarlı, yalın kalıp	2640 adım	16.040 adım	40/40
Yerleşim, tekrarlı, korumalı kalıp	2640 adım	750 adım	39/40
Yerleşim, aralık dışı	2640 adım	801 adım	40/40
Eksik değer, aralık dışı	3536 adım	1281 adım	0/40

İkinci satır durmamanın, üçüncü satır sessiz yanlışın, beşinci satır ise sorunun değişmesinin ölçüsüdür. Beş satırın hiçbirinde adım sütununa bakarak doğru satırlar seçilemez.

Özet

• Döngüsel yerleştirme hiç karşılaştırma yapmaz; her değeri doğrudan v-1 konumuna gönderir ve toplam takas sayısı n’i aşmaz.
• Kalıbın iki ayrı ön koşulu vardır ve bozulmalarının sonucu ayrıdır: tekrarlı değer durmamaya, aralık dışı değer sessiz yanlışa yol açar.
• Yalın kalıp tekrarlı girdide 40 girdinin 40’ında adım sınırına dayanıyor ve oran 0,16’ya düşüyor; aralık dışı girdide 801 adımda biriyor ve 40 girdinin 40’ında yanlış.
• Tekrar koruması durmamayı ortadan kaldırıyor ama yerleşim sorusunda ayrılan girdiyi 40’tan yalnız 39’a indiriyor.
• Aynı kalıp “hangi değerler eksik” sorusuna yanıt verdiğinde altı ölçümün altısında ayrılan girdi sıfırdır; ön koşul kalıba değil, kalıp–soru çiftine aittir.

Sonraki Adım

Buraya kadarki beş kalıp girdinin tamamını elinde tuttu: diziyi baştan sona görebiliyor, istediği konuma dönebiliyordu. Sonraki kalıp bu olanağı kaybeder. Veriler tek tek akar ve her yeni değerden sonra bir soru yanıtlanmalıdır: o ana kadar görülenlerin ortancası nedir. Kalıp iki yığın tutar ve ön koşulu bu iki yığının dengede kalmasıdır. Sonraki ders dengeyi bozunca kaç adımda kaç yanlış ortanca çıktığını sayacak.