--- title: 'Döngüsel Yerleştirme' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/donguscel-yerlestirme' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:29+00:00' license: 'CC BY-SA 4.0' --- # Döngüsel Yerleştirme Sınırlı değer aralığında karşılaştırmasız yerinde yerleştirme; tekrarlı değerde durmayan kalıp, aralık dışı değerde 40 yanlış yanıt ve korumanın neyi çözmediği. Ö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. ```python 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. ```python 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. ```python 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 **soru**dur. "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.