K'ıncı Eleman

Önceki kalıp ortancayı, yani sıralı düzende ortadaki değeri veriyordu. Ortanca genel bir sorunun özel bir durumudur: sıralı düzende k’ıncı değer nedir. K ortadaysa ortanca, k bir ise en küçük, k n ise en büyük değer sorulmuş olur.

Bu ders soruyu iki ayrı kalıpla yanıtlar. Birincisi k boyutlu bir yığın tutar; ikincisi diziyi bölümleyip yalnız ilgili yarıda arar. İkisi de aynı kâhinle sınanır ve iki farklı türde ön koşul ortaya çıkar: biri sorunun tanımına, öbürü girdinin düzenine dokunur.

İki Kalıp, Bir Kâhin

Kâhin diziyi karşılaştırarak baştan sona yerleştirir ve k’ıncı konumu okur; her karşılaştırma bir adım sayılır. Yığın kalıbı yalnız k eleman tutar: her yeni değer en büyük yığına konur, yığın k’yı aşarsa tepesi atılır. Sonunda tepede duran değer, görülen bütün değerler arasında k’ıncı en küçük olandır. Yığın koşulu ve süzme işlemleri Veri Yapıları kursunun Yığınlar dersinde kuruldu; burada tekrarlanmaz.

Aynı yapı bir soruya daha yanıt veriyor gibi görünür: k’ıncı en küçük ayrı değer. Tek fark, daha önce görülmüş bir değerin yığına konmamasıdır. Kod neredeyse aynıdır, çıktı bir sayıdır, kalıp yine ucuzdur.

PK47. Dağarcık önceki derslerin dağarcığıdır: 40 dizi, her biri 12 değer, değerler −9 ile 20 arasında; tohum 20260218. PK48. Kâhinin yanıtı k’ıncı elemandır: sıralı düzende k’ıncı konumdaki değer, tekrarlar dahil. PK49. Yığın adımları gerçek karşılaştırmalardır; değerler karşılaştırmayı sayan bir sarmalayıcıya konur. PK50. Dört k değeri süpürülür: 3, 4, 6 ve 8.

import heapq

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 dagarcik(tohum=TOHUM, n=DAGARCIK, uzunluk=UZUNLUK):
    r = uretec(tohum)
    return [{"no": i + 1, "dizi": [r(30) - 9 for _ in range(uzunluk)]}
            for i in range(n)]


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

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


class Olcu:
    """Yiginin her karsilastirmasini sayar. yon=-1 en buyuk yigin verir."""
    __slots__ = ("d", "yon", "s")

    def __init__(self, d, yon, s):
        self.d, self.yon, self.s = d, yon, s

    def __lt__(self, o):
        self.s.say()
        return self.d * self.yon < o.d * o.yon


def kahin_kinci(dizi, k, s):
    """Butun diziyi karsilastirarak yerlestirir, k'inci konumu okur."""
    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[k - 1]


def kalip_yigin(dizi, k, s):
    """k boyutlu en buyuk yigin tutar; tepesi k'inci en kucuk degerdir."""
    y = []
    for x in dizi:
        heapq.heappush(y, Olcu(x, -1, s))
        if len(y) > k:
            heapq.heappop(y)
    return y[0].d


def kalip_ayri_deger(dizi, k, s):
    """AYNI yapi, BASKA soru: k'inci en kucuk AYRI deger."""
    y, gorulen = [], set()
    for x in dizi:
        s.say()
        if x in gorulen:
            continue
        gorulen.add(x)
        heapq.heappush(y, Olcu(x, -1, s))
        if len(y) > k:
            heapq.heappop(y)
    return y[0].d if len(y) == k else None


K40 = dagarcik()
print("dagarcik: 40 dizi x 12 deger | tekrarli deger iceren dizi:",
      sum(1 for k in K40 if len(set(k["dizi"])) < UZUNLUK))
print(" k  kalip              ayrilan/40  kalip  kahin   oran")
for k in (3, 4, 6, 8):
    for ad, kalip in (("k'inci eleman    ", kalip_yigin),
                      ("k'inci ayri deger", kalip_ayri_deger)):
        ayrilan, ak, ah = 0, 0, 0
        for kayit in K40:
            s1, s2 = Sayac(), Sayac()
            a = kalip(kayit["dizi"], k, s1)
            b = kahin_kinci(kayit["dizi"], k, s2)
            ak, ah = ak + s1.adim, ah + s2.adim
            ayrilan += (a != b)
        print(f"{k:2d}  {ad}  {ayrilan:10d}  {ak:5d}  {ah:5d}  {ah / ak:5.2f}")
print()
ilk = K40[0]["dizi"]
print("girdi 1          :", ilk)
print("  sirali duzen   :", sorted(ilk))
print("  kahin k=4      :", kahin_kinci(ilk, 4, Sayac()))
print("  yigin k=4      :", kalip_yigin(ilk, 4, Sayac()))
print("  ayri deger k=4 :", kalip_ayri_deger(ilk, 4, Sayac()))

dagarcik: 40 dizi x 12 deger | tekrarli deger iceren dizi: 37
 k  kalip              ayrilan/40  kalip  kahin   oran
 3  k'inci eleman               0   1440   2640   1.83
 3  k'inci ayri deger           9   1640   2640   1.61
 4  k'inci eleman               0   1559   2640   1.69
 4  k'inci ayri deger          17   1723   2640   1.53
 6  k'inci eleman               0   1348   2640   1.96
 6  k'inci ayri deger          27   1503   2640   1.76
 8  k'inci eleman               0   1292   2640   2.04
 8  k'inci ayri deger          30   1381   2640   1.91

girdi 1          : [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1]
  sirali duzen   : [-8, -5, -1, -1, 1, 2, 2, 4, 5, 6, 16, 17]
  kahin k=4      : -1
  yigin k=4      : -1
  ayri deger k=4 : 1

Yığın kalıbı dört k değerinin dördünde de 40 girdinin 40’ında kâhinle aynı yanıtı veriyor; oran 1,69 ile 2,04 arasında. Ayrı değer biçimi ise k büyüdükçe daha çok ayrılıyor: 9, 17, 27, 30.

Birinci girdi farkı bir bakışta gösteriyor. Sıralı düzen [-8, -5, -1, -1, 1, ...]; dördüncü eleman −1, çünkü −1 iki kez var. Dördüncü ayrı değer ise 1. İki yanıt da doğrudur — ama iki ayrı soruya. Kalıbın kusuru değil, sorunun kaymasıdır.

Soru Aynı Görünüyor, Aynı Değil

Ayrılmanın nedeninin gerçekten tekrarlar olduğunu göstermek için bir denetim gerekir: aynı ölçüm, tekrarları ayıklanmış bir dağarcıkta yinelenir. Tekrar yoksa iki soru aynı soruya dönüşmelidir ve ayrılma sıfır olmalıdır.

PK51. Denetim dağarcığı, aynı dizilerin ayrı değerlerinden oluşur; başka bir üreteçten gelmez. Diziler kısaldığı için yalnız k=3 ve k=6 ölçülür. PK52. İkinci dağarcık 20260219 tohumundan gelir ve aynı dört k değeriyle süpürülür.

import heapq


def uretec(tohum):
    d = tohum

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


def dagarcik(tohum, n=40, uzunluk=12):
    r = uretec(tohum)
    return [[r(30) - 9 for _ in range(uzunluk)] for _ in range(n)]


def kahin_kinci(dizi, k):
    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[k - 1]


def kalip_yigin(dizi, k):
    y = []
    for x in dizi:
        heapq.heappush(y, -x)
        if len(y) > k:
            heapq.heappop(y)
    return -y[0]


def kalip_ayri_deger(dizi, k):
    y, gorulen = [], set()
    for x in dizi:
        if x in gorulen:
            continue
        gorulen.add(x)
        heapq.heappush(y, -x)
        if len(y) > k:
            heapq.heappop(y)
    return -y[0] if len(y) == k else None


print("tohum      k  k'inci eleman  k'inci ayri deger  ayri deger orani")
for tohum in (20260218, 20260219):
    K = dagarcik(tohum)
    for k in (3, 4, 6, 8):
        e = sum(1 for d in K if kalip_yigin(d, k) != kahin_kinci(d, k))
        f = sum(1 for d in K if kalip_ayri_deger(d, k) != kahin_kinci(d, k))
        print(f"{tohum}  {k:2d}  {e:13d}  {f:17d}  {f / 40:16.4f}")
print()
print("tekrarsiz dagarcikta ayni olcum (her dizinin ayri degerleri):")
for tohum in (20260218, 20260219):
    K = [sorted(set(d)) for d in dagarcik(tohum)]
    for k in (3, 6):
        f = sum(1 for d in K if kalip_ayri_deger(d, k) != kahin_kinci(d, k))
        print(f"  {tohum}  k={k}  ayrilan {f}/40")

tohum      k  k'inci eleman  k'inci ayri deger  ayri deger orani
20260218   3              0                  9            0.2250
20260218   4              0                 17            0.4250
20260218   6              0                 27            0.6750
20260218   8              0                 30            0.7500
20260219   3              0                 12            0.3000
20260219   4              0                 24            0.6000
20260219   6              0                 28            0.7000
20260219   8              0                 32            0.8000

tekrarsiz dagarcikta ayni olcum (her dizinin ayri degerleri):
  20260218  k=3  ayrilan 0/40
  20260218  k=6  ayrilan 0/40
  20260219  k=3  ayrilan 0/40
  20260219  k=6  ayrilan 0/40

Denetim kesin: tekrarları ayıklanmış dağarcıkta dört ölçümün dördünde ayrılan girdi sıfır. Ayrılmanın kaynağı kalıpta değil, dağarcıktaki tekrarlarda ve sorunun tanımındadır.

İkinci dağarcıkta oranlar 0,30 ile 0,80 arasında, birincide 0,2250 ile 0,7500 arasında — aynı büyüklük düzeninde ve aynı yönde artıyor. Sonuç dağarcığa bağlı değildir. Yığın kalıbının k’ıncı eleman sütunu sekiz satırın sekizinde sıfırdır.

Buradan çıkan uyarı, konunun en pratik uyarısıdır. İki soru arasındaki fark kodda tek bir satırdır ve o satır bir iyileştirme gibi görünür: aynı değeri iki kez yığına koymamak yığını küçültür, adım sayısını düşürür. Sekiz satırın hiçbirinde bu satırın yanlış olduğunu söyleyen bir belirti yoktur; belirti yalnız kâhinin sütunundadır.

Bölümlemenin Ön koşulu Pivot Seçimidir

İkinci kalıp diziyi bir pivot çevresinde bölümler: pivottan küçükler sola, büyükler sağa geçer ve pivot kendi son konumuna oturur. O konum k’ıncıysa yanıt bulunmuştur; değilse arama yalnız bir yanda sürer. Bölümleme yordamı Algoritmalar kursunda hızlı sıralama içinde kuruldu; burada tekrarlanmaz.

Bu kalıbın ön koşulu doğruluğa değil adıma dokunur: pivotun bölmeyi gerçekten ikiye ayırması gerekir. Pivot her seferinde uçtaki değere denk gelirse bölme bir eleman kadar ilerler ve arama alanı yavaş küçülür.

PK53. İki pivot seçimi karşılaştırılır: bölümün ilk değeri ve orta değeri. PK54. k, dizinin ortasıdır (uzunluk // 2), yani en çok bölümleme gerektiren konum. PK55. Ölçüm iki uzunlukta yinelenir: 12 ve 60 değer. Sıralı öbek, aynı dizilerin sıralanmış biçimidir.

def uretec(tohum):
    d = tohum

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


def dagarcik(tohum, n=40, uzunluk=12):
    r = uretec(tohum)
    return [[r(30) - 9 for _ in range(uzunluk)] for _ in range(n)]


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

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


def kahin_kinci(dizi, k, s):
    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[k - 1]


def kalip_bolumleme(dizi, k, pivot_ilk, s):
    """Bolumleme ile secim. ONKOSUL: pivot secimi girdinin duzeniyle ortusmemeli."""
    a, sol, sag = list(dizi), 0, len(dizi) - 1
    while sol < sag:
        p = sol if pivot_ilk else (sol + sag) // 2
        a[p], a[sag] = a[sag], a[p]
        pivot, i = a[sag], sol
        for j in range(sol, sag):
            s.say()
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[sag] = a[sag], a[i]
        if k - 1 == i:
            return a[i]
        if k - 1 < i:
            sag = i - 1
        else:
            sol = i + 1
    return a[sol]


print("uzunluk  girdi     pivot      ayrilan/40  kalip   kahin    oran")
for uzunluk in (12, 60):
    K = dagarcik(20260218, 40, uzunluk)
    for gad, hazirla in (("sirasiz", list), ("sirali ", sorted)):
        for pad, pivot_ilk in (("ilk deger ", True), ("orta deger", False)):
            ayrilan, ak, ah = 0, 0, 0
            for dizi in K:
                d = hazirla(dizi)
                s1, s2 = Sayac(), Sayac()
                a = kalip_bolumleme(d, uzunluk // 2, pivot_ilk, s1)
                b = kahin_kinci(d, uzunluk // 2, s2)
                ak, ah = ak + s1.adim, ah + s2.adim
                ayrilan += (a != b)
            print(f"{uzunluk:7d}  {gad}  {pad}  {ayrilan:10d}  {ak:5d}"
                  f"  {ah:6d}  {ah / ak:6.2f}")

uzunluk  girdi     pivot      ayrilan/40  kalip   kahin    oran
     12  sirasiz  ilk deger            0    943    2640    2.80
     12  sirasiz  orta deger           0   1073    2640    2.46
     12  sirali   ilk deger            0   2040    2640    1.29
     12  sirali   orta deger           0    473    2640    5.58
     60  sirasiz  ilk deger            0   6726   70800   10.53
     60  sirasiz  orta deger           0   7346   70800    9.64
     60  sirali   ilk deger            0  53400   70800    1.33
     60  sirali   orta deger           0   3407   70800   20.78

Sekiz satırın sekizinde ayrılan girdi sıfır. Bölümlemeli seçim, pivot ne olursa olsun doğru yanıt verir; bu kalıbın ön koşulu doğrulukla ilgili değildir.

Adım sütunu ise 60 değerlik sıralı girdide çarpıcıdır: ilk değeri pivot seçmek 53.400 adım, orta değeri seçmek 3407 adım harcıyor. Tek satırlık bir seçim, adımı 15,7 kat büyütüyor ve kalıbın oranını 20,78’den 1,33’e düşürüyor — yani kalıp neredeyse kâhin kadar pahalı hâle geliyor.

Bu satır kursun ikinci iddiasının bir başka yüzüdür: ön koşul bozulduğunda her zaman yanlış yanıt gelmez. Bazen yalnız adım patlar, ve patlaması için verinin bozuk olması gerekmez — burada girdi sıralı, yani en düzenli hâlindedir. Kalıbı bozan şey verinin düzensizliği değil, pivot kuralının o düzenle örtüşmesidir.

Üç Sayı

Ölçüt	Kâhin	Kalıp	Ayrılan girdi
Yığın, k’ıncı eleman (k=6)	2640 adım	1348 adım	0/40
Yığın, k’ıncı ayrı değer (k=6)	2640 adım	1503 adım	27/40
Bölümleme, 60 değer, sırasız, orta pivot	70.800 adım	7346 adım	0/40
Bölümleme, 60 değer, sıralı, ilk pivot	70.800 adım	53.400 adım	0/40

İlk iki satır doğruluğun sorunun tanımına bağlı olduğunu, son iki satır başarımın pivot kuralına bağlı olduğunu gösterir. Dört satırın hiçbirinde adım sütunu ayrılan girdi sütununu haber vermiyor: en düşük adımlı satır doğru, ikinci en düşük adımlı satır 27 girdide yanlış.

Özet

• K’ıncı eleman sorusu ortancanın genelidir; k boyutlu bir yığın tutmak, bütün diziyi yerleştirmeden yanıtı verir.
• Yığın kalıbı dört k değerinin dördünde de 40 girdinin 40’ında kâhinle aynı yanıtı veriyor; oran 1,69 ile 2,04 arasında.
• Tekrarlı değerlerde “k’ıncı eleman” ile “k’ıncı ayrı değer” ayrı sorulardır; ikincisi k=6 için 27 girdide kâhinden ayrılıyor ve fark kodda tek satırdır.
• Tekrarları ayıklanmış denetim dağarcığında ayrılan girdi dört ölçümün dördünde sıfırdır; kaynak kalıp değil, sorunun tanımıdır.
• Bölümlemeli seçim her pivotla doğrudur, ama sıralı 60 değerlik girdide ilk değeri pivot seçmek adımı 3407’den 53.400’e çıkarıyor ve oranı 20,78’den 1,33’e düşürüyor.

Sonraki Adım

Bu konunun yedi kalıbı da tek boyutlu veriyle çalıştı: bir dizi, bir akış, bir ardıl zinciri. Son kalıp veriyi iki boyutta ele alır. Bir ızgarada birbirine bağlı hücre kümeleri aranır ve gezinme, Veri Yapıları kursunun enine ve derine aramasıyla yapılır — o iki yordam tekrarlanmaz, doğrudan çağrılır. Ön koşul yine bir tanım seçimidir: komşuluğun ne demek olduğu. Sonraki ders iki komşuluk tanımının aynı ızgarada kaç farklı yanıt ürettiğini sayacak.