--- title: "K'ıncı Eleman" source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/kinci-eleman' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:30+00:00' license: 'CC BY-SA 4.0' --- # K'ıncı Eleman Seçim problemlerinde yığın tabanlı ve bölümlemeli çözümler; sorunun tanımı kaydığında 27 girdide ayrılan yanıt ve pivot seçiminin adımı 15 kat büyütmesi. Ö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. ```python 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. ```python 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. ```python 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.