--- title: 'Aralık Birleştirme' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/aralik-birlestirme' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:30+00:00' license: 'CC BY-SA 4.0' --- # Aralık Birleştirme Örtüşen aralıkların tek geçişle indirgenmesi; yanlış sıralama anahtarınün 29 girdide bozduğu birleştirme ve eşitlik kuralının 8 girdide değiştirdiği yanıt. Önceki üç kalıp girdiyi olduğu gibi aldı: iki işaretçi sıralı gelmesini bekliyordu, kayan pencere işaretlere bakıyordu, hızlı ve yavaş işaretçi ardıl bağlantısını izliyordu. Bu dersin kalıbı girdiyi **önce yeniden düzenler**. Örtüşen aralıkları birleştirmek, aralıkları bir ölçüte göre sıralamakla başlar ve sıralama bittikten sonra tek bir geçiş yeter. Ön koşul artık verinin bir özelliği değildir; **seçilen ölçütün kendisidir**. Ölçüt yanlış seçildiğinde kalıp yine tek geçişte biter, yine bir aralık listesi döndürür ve yine hiçbir uyarı vermez. Bu ders üç yanlış ölçütü aynı kâhinle karşılaştırıp her birinin kaç girdide yanlış birleştirdiğini sayar. ## Problem, Kâhin ve Kalıp Problem şudur: verilen aralık kümesinde **örtüşen aralıkları birleştirip** en sade listeyi üretmek. Kâhin hiçbir sıralama yapmaz; örtüşen bir çift buldukça birleştirir ve hiçbir çift kalmayana kadar yineler. Bu, sonucu tanımı gereği doğru kılar ama her birleştirmede taramayı baştan başlatır. Kalıp bir kez sıralar, sonra listeyi soldan sağa tarar: her aralık ya son birleşik aralığın sağ ucunu uzatır ya da yeni bir birleşik aralık açar. **PK25.** Dağarcık 40 kümedir; her küme 12 aralık taşır. Başlangıç 0–60, uzunluk 1–9; tohum `20260218`. **PK26.** Aralıklar **kapalıdır**: `(4, 20)` aralığı 4 ile 20 arasındaki bütün noktaları içerir ve `(20, 25)` ile örtüşür. **PK27.** Kâhinin ve kalıbın yanıtı, karşılaştırmadan önce **sıralanır**; ayrılma bir sıra farkından değil, yalnız içerik farkından doğar. **PK28.** Sıralamanın adımı kalıbın hanesine yazılır. Karşılaştırmalı bir yordam kullanılır ve her karşılaştırma bir adım sayılır; sıralama yordamlarının kendisi Algoritmalar kursunda ölçüldü ve burada tekrarlanmaz. ```python TOHUM, ARALIK, 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 aralik_dagarcik(tohum=TOHUM, n=DAGARCIK, adet=ARALIK): r = uretec(tohum) kume = [] for i in range(n): liste = [] for _ in range(adet): bas = r(61) liste.append((bas, bas + 1 + r(9))) kume.append({"no": i + 1, "aralik": liste}) return kume class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def kahin_birlestir(araliklar, s): """Ortusen bir cift buldukca birlestirir, degisiklik bitene kadar yineler.""" kalan = [list(a) for a in araliklar] degisti = True while degisti: degisti = False for i in range(len(kalan)): for j in range(i + 1, len(kalan)): s.say() if kalan[i][0] <= kalan[j][1] and kalan[j][0] <= kalan[i][1]: kalan[i] = [min(kalan[i][0], kalan[j][0]), max(kalan[i][1], kalan[j][1])] kalan.pop(j) degisti = True break if degisti: break return sorted(tuple(a) for a in kalan) def sirala_sayarak(liste, anahtar, s): a = list(liste) for i in range(1, len(a)): j = i while j > 0: s.say() if anahtar(a[j - 1]) <= anahtar(a[j]): break a[j - 1], a[j] = a[j], a[j - 1] j -= 1 return a def kalip_birlestir(araliklar, anahtar, s): """ONKOSUL: siralama olcutu BASLANGIC olmali. Tek gecis yeter.""" sonuc = [] for bas, son in sirala_sayarak(araliklar, anahtar, s): s.say() if sonuc and bas <= sonuc[-1][1]: sonuc[-1] = (sonuc[-1][0], max(sonuc[-1][1], son)) else: sonuc.append((bas, son)) return sorted(sonuc) OLCUT = (("baslangica gore", lambda a: a[0]), ("bitise gore ", lambda a: a[1]), ("uzunluga gore ", lambda a: a[1] - a[0]), ("siralamasiz ", lambda a: 0)) K = aralik_dagarcik() print("dagarcik:", len(K), "kume x", ARALIK, "aralik") print("olcut ayrilan/40 kalip kahin oran ilk ayrilanlar") for ad, anahtar in OLCUT: ayrilan, ak, ah = [], 0, 0 for k in K: s1, s2 = Sayac(), Sayac() a = kalip_birlestir(k["aralik"], anahtar, s1) b = kahin_birlestir(k["aralik"], s2) ak, ah = ak + s1.adim, ah + s2.adim if a != b: ayrilan.append(k["no"]) print(f"{ad} {len(ayrilan):8d} {ak:5d} {ah:5d} {ah / ak:5.2f}" f" {ayrilan[:5]}") ``` ``` dagarcik: 40 kume x 12 aralik olcut ayrilan/40 kalip kahin oran ilk ayrilanlar baslangica gore 0 2154 2974 1.38 [] bitise gore 29 2145 2974 1.39 [2, 3, 4, 6, 7] uzunluga gore 40 2041 2974 1.46 [1, 2, 3, 4, 5] siralamasiz 40 920 2974 3.23 [1, 2, 3, 4, 5] ``` Dört satır dört ayrı ölçüt, aynı kâhin, aynı dağarcık. Yalnız birinci satır doğrudur: başlangıca göre sıralayan kalıp 40 girdinin 40'ında kâhinle aynı listeyi üretiyor. Son satır dersin en keskin sayısıdır. **Sıralamasız kalıp en hızlısıdır** — 920 adım, oran **3,23** — ve **40 girdinin 40'ında yanlıştır**. Sıralamayı atlamak kalıbı üç kat hızlandırıyor ve tümüyle bozuyor. Sıralamanın adımı doğrudan ölçülebilir: 2154 ile 920 arasındaki **1234 adım**, ön koşulu sağlamanın bedelidir ve kalıbın kazancının büyük bölümünü yiyor. Kâhinin 2974 adımı da açıklama ister. Kâhin her birleştirmeden sonra taramayı **baştan** başlatır, çünkü yeni oluşan geniş aralık daha önce bakılmış bir çiftle örtüşebilir. Bu, kâhini bilerek pahalı kılan bir seçimdir ve amacı hızlanmak değil, **hiçbir örtüşmeyi kaçırmamaktır**. Kalıbın tek geçişte aynı sonucu vermesi, sıralamanın bu geriye dönüşü gereksiz kılmasından gelir: başlangıca göre sıralı bir listede, kapanmış bir birleşik aralığa sonradan dokunacak bir aralık kalmaz. Ortadaki iki satır arasındaki fark da öğreticidir. Uzunluğa göre sıralamak **40 girdinin 40'ında** yanlış; bitişe göre sıralamak **29'unda**. İkisi de yanlış ölçüttür, ama biri girdilerin dörtte birinde doğru yanıt üretir — ve o dörtte bir, ölçütün doğru sanılmasına yeter. ## Bitişe Göre Sıralamak Neden Bozuyor Kalıbın tek karar kuralı `bas <= sonuc[-1][1]` karşılaştırmasıdır: yeni aralığın başlangıcı, açık duran birleşik aralığın sağ ucunu geçmiyorsa birleştir. Bu kural, sonraki her aralığın başlangıcının **öncekinden küçük olmadığını** varsayar. Başlangıca göre sıralamak tam olarak bunu güvenceye alır. Bitişe göre sıralandığında geç başlayan ama erken biten bir aralık öne geçebilir; onun arkasından gelen, **daha erken başlayan** bir aralık artık birleşme koşulunu sağlamaz ve yeni bir birleşik aralık açar. Sonuç listesinde birbirini kapsayan iki kayıt kalır. ```python def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def aralik_dagarcik(tohum, n=40, adet=12): r = uretec(tohum) kume = [] for i in range(n): liste = [] for _ in range(adet): bas = r(61) liste.append((bas, bas + 1 + r(9))) kume.append({"no": i + 1, "aralik": liste}) return kume def kahin_birlestir(araliklar): kalan = [list(a) for a in araliklar] degisti = True while degisti: degisti = False for i in range(len(kalan)): for j in range(i + 1, len(kalan)): if kalan[i][0] <= kalan[j][1] and kalan[j][0] <= kalan[i][1]: kalan[i] = [min(kalan[i][0], kalan[j][0]), max(kalan[i][1], kalan[j][1])] kalan.pop(j) degisti = True break if degisti: break return sorted(tuple(a) for a in kalan) def kalip_birlestir(araliklar, anahtar): sonuc = [] for bas, son in sorted(araliklar, key=anahtar): if sonuc and bas <= sonuc[-1][1]: sonuc[-1] = (sonuc[-1][0], max(sonuc[-1][1], son)) else: sonuc.append((bas, son)) return sorted(sonuc) kucuk = [(4, 20), (6, 8), (10, 12)] print("kucuk ornek :", kucuk) print(" kahin :", kahin_birlestir(kucuk)) print(" baslangica gore :", kalip_birlestir(kucuk, lambda a: a[0])) print(" bitise gore :", kalip_birlestir(kucuk, lambda a: a[1]), " <- bitise gore siralama:", sorted(kucuk, key=lambda a: a[1])) print() print("tohum olcut ayrilan/40 oran") for tohum in (20260218, 20260219): K = aralik_dagarcik(tohum) for ad, anahtar in (("baslangica gore", lambda a: a[0]), ("bitise gore ", lambda a: a[1]), ("uzunluga gore ", lambda a: a[1] - a[0]), ("siralamasiz ", lambda a: 0)): ayrilan = sum(1 for k in K if kalip_birlestir(k["aralik"], anahtar) != kahin_birlestir(k["aralik"])) print(f"{tohum} {ad} {ayrilan:8d} {ayrilan / 40:.4f}") ``` ``` kucuk ornek : [(4, 20), (6, 8), (10, 12)] kahin : [(4, 20)] baslangica gore : [(4, 20)] bitise gore : [(6, 8), (10, 20)] <- bitise gore siralama: [(6, 8), (10, 12), (4, 20)] tohum olcut ayrilan/40 oran 20260218 baslangica gore 0 0.0000 20260218 bitise gore 29 0.7250 20260218 uzunluga gore 40 1.0000 20260218 siralamasiz 40 1.0000 20260219 baslangica gore 0 0.0000 20260219 bitise gore 32 0.8000 20260219 uzunluga gore 40 1.0000 20260219 siralamasiz 40 1.0000 ``` Üç aralıklı küçük örnek mekanizmayı bütünüyle gösteriyor. Doğru yanıt tek aralıktır: `(6, 8)` ve `(10, 12)` tümüyle `(4, 20)` içindedir. Bitişe göre sıralanınca `(4, 20)` listenin **sonuna** düşüyor; kalıp önce `(6, 8)` ile başlıyor, `(10, 12)` birleşmiyor ve yeni bir kayıt açılıyor, sonra `(4, 20)` gelip onu `(10, 20)` yapıyor. Geriye `(6, 8)` kaydı **kapsanmış olduğu hâlde** ayrı duruyor. **PK29.** İkinci dağarcık `20260219` tohumundan gelir. Bitişe göre sıralamada ayrılan girdi **32/40**, birincide **29/40**; oran 0,7250 ile 0,8000, aynı büyüklük düzeninde. Sonuç dağarcığa bağlı değildir. Uzunluğa göre ve sıralamasız ölçütler iki dağarcıkta da **40/40**'tır. ## Ölçüt Yalnız Anahtar Değil, Eşitlik Kuralıdır Sıralama ölçütü seçildikten sonra bir soru daha kalır ve çoğu zaman sorulmaz: **aynı değere sahip iki kayıt hangi sırayla gelecek.** Aralıklarla çalışan ikinci bir problem bu soruyu ölçülebilir kılar: bir noktada **en çok kaç aralık aynı anda açık**. Kalıp aralıkları olaylara çevirir — her başlangıç bir açılış, her bitiş bir kapanış — ve olayları koordinata göre sıralayıp tek geçişte sayar. Bir aralığın bittiği koordinatta başka bir aralık başlıyorsa, kapanışın açılıştan **önce** işlenmesi gerekir; kapalı sayılan bir uç iki kez sayılırsa açık aralık sayısı şişer. **PK30.** Bu ölçümde aralıklar **yarı açıktır**: bir aralık başlangıcını içerir, bitişini içermez. Kâhin her başlangıç noktasında kaç aralığın açık olduğunu tek tek sayar. **PK31.** Dağarcığın **32 kümesinde** bir aralığın bitişi başka bir aralığın başlangıcıyla çakışır; eşitlik kuralının etkisi ancak bu kümelerde görülebilir. ```python def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def aralik_dagarcik(tohum=20260218, n=40, adet=12): r = uretec(tohum) kume = [] for i in range(n): liste = [] for _ in range(adet): bas = r(61) liste.append((bas, bas + 1 + r(9))) kume.append({"no": i + 1, "aralik": liste}) return kume class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def kahin_ortusme(araliklar, s): """Her baslangic noktasinda kac aralik acik. Butun ciftler denenir.""" en_cok = 0 for bas, _ in araliklar: acik = 0 for b, y in araliklar: s.say() if b <= bas < y: acik += 1 en_cok = max(en_cok, acik) return en_cok def kalip_ortusme(araliklar, once_bitis, s): """ONKOSUL: ayni koordinatta BITIS olayi baslangictan once islenmeli.""" olay = [] for bas, son in araliklar: olay.append((bas, 1 if once_bitis else 0, +1)) olay.append((son, 0 if once_bitis else 1, -1)) en_cok = acik = 0 for _, _, delta in sorted(olay): s.say() acik += delta en_cok = max(en_cok, acik) return en_cok K = aralik_dagarcik() carpisan = sum(1 for k in K if {b for b, _ in k["aralik"]} & {y for _, y in k["aralik"]}) print("dagarcik: 40 kume x 12 aralik | bir bitisi bir baslangicla cakisan kume:", carpisan) print("olay sirasi ayrilan/40 kalip kahin oran ilk ayrilanlar") for ad, once_bitis in (("bitis once ", True), ("baslangic once", False)): ayrilan, ak, ah = [], 0, 0 for k in K: s1, s2 = Sayac(), Sayac() a = kalip_ortusme(k["aralik"], once_bitis, s1) b = kahin_ortusme(k["aralik"], s2) ak, ah = ak + s1.adim, ah + s2.adim if a != b: ayrilan.append(k["no"]) print(f"{ad} {len(ayrilan):10d} {ak:5d} {ah:5d} {ah / ak:5.2f}" f" {ayrilan[:5]}") ``` ``` dagarcik: 40 kume x 12 aralik | bir bitisi bir baslangicla cakisan kume: 32 olay sirasi ayrilan/40 kalip kahin oran ilk ayrilanlar bitis once 0 960 5760 6.00 [] baslangic once 8 960 5760 6.00 [5, 7, 8, 15, 31] ``` İki satırın adım sütunları birebir aynı: kalıp **960**, kâhin **5760**, oran **6,00**. Değişen tek şey aynı koordinattaki iki olayın hangisinin önce işlendiğidir ve bu tek karar **8 girdide** yanıtı değiştiriyor. Sekiz sayısı 32'nin çeyreğinden azdır ve bu, ölçütün neden gözden kaçtığını açıklar. Çakışmanın olmadığı 8 kümede eşitlik kuralının hiçbir etkisi yoktur; çakışmanın olduğu 32 kümenin çoğunda da en çok örtüşme başka bir yerde oluştuğu için sonuç değişmez. Kural yalnız 8 girdide görünür — ama o 8 girdide **yanlıştır**, ve hangi 8 girdi olduğu ancak kâhinle bilinir. ## Üç Sayı | Ölçüt | Kâhin | Kalıp | Ayrılan girdi | |---|---|---|---| | Başlangıca göre sıralı | 2974 adım | 2154 adım | **0/40** | | Bitişe göre sıralı | 2974 adım | 2145 adım | **29/40** | | Sıralamasız | 2974 adım | 920 adım | **40/40** | | Örtüşme sayımı, bitiş önce | 5760 adım | 960 adım | **0/40** | | Örtüşme sayımı, başlangıç önce | 5760 adım | 960 adım | **8/40** | Beş satırın hiçbirinde adım sütunu doğruluk hakkında bilgi taşımıyor; üçüncü satırda en düşük adımla en yüksek yanlış sayısı bir arada duruyor. Kalıbın ön koşulu tek bir cümleyle söylenebilir: **sıralama anahtarı, kalıbın tek karar kuralının varsaydığı şeyi güvenceye almalıdır** — ne fazlası ne eksiği. Ölçütü "doğal görünen" bir alana bakarak seçmek, karar kuralına bakmadan seçmektir. ## Özet - Aralık birleştirme, girdiyi önce sıralayan ilk kalıptır; ön koşulu verinin değil **seçilen ölçütün** bir özelliğidir. - Başlangıca göre sıralamak 40 girdinin 40'ında doğru; bitişe göre sıralamak **29**, uzunluğa göre sıralamak ve sıralamamak **40** girdide kâhinden ayrılıyor. - Sıralamayı atlamak kalıbı 2154 adımdan 920 adıma indiriyor ve **bütün girdilerde** yanlış yapıyor; en hızlı satır en bozuk satırdır. - İkinci dağarcıkta bitişe göre ayrılan girdi 32; oran aynı büyüklük düzeninde kaldığı için sonuç dağarcığa bağlı değildir. - Örtüşme sayımında aynı koordinattaki olay sırası tek başına **8 girdide** yanıtı değiştiriyor; adım sayısı iki durumda da birebir aynı kalıyor. ## Sonraki Adım Bu kalıp sıralamanın bedelini ödeyip karşılığında tek geçiş aldı. Sonraki kalıp sıralamayı bütünüyle atlar: değerlerin **kendi konumlarını bildiği** bir aralıkta, her değer doğrudan gideceği yere yerleştirilir ve karşılaştırma hiç yapılmaz. Ön koşulu ağırdır — değerler 1 ile n arasında ve tekrarsız olmalıdır — ve bozulduğunda kalıp yalnız yanlış yanıt vermez, dönüp durur. Sonraki ders bu iki kusuru ayrı ayrı sayacak.