Testten Geçen Ama Yanlış: Kararsız Merge Sort ve 997. Elemanda Çöken İkili Arama Ağacı

Yapay zekânın yazdığı merge sort ve ikili arama ağacı, yine onun yazacağı türden tipik testlerin hepsinden geçti. Eşit puanlı kayıtlarla merge sort sırayı tersine çevirdi, sıralı 1000 sayıda ağaç 997. eklemede RecursionError verdi. Testlerin neyi göremediği, gerçek çıktılar ve düzeltmeler.

Ağustos sonunda iki klasik algoritma yazısı yayımlamıştık: Bubble Sort ve Merge Sort ile İkili Arama Ağacı. Kodu bir yapay zekâ yazmıştı. Örnek çıktılar doğruydu. Bu kez bu iki koda, bir yapay zekânın da yazacağı türden tipik testler yazdık ve hepsi geçti. Sonra iki farklı girdi denedik: eşit değerli kayıtlar ve sıralı gelen sayılar. Merge sort eşit kayıtların sırasını tersine çevirdi. Ağaç, 997. sayıyı eklerken RecursionError verdi. Bu yazıda testlerin neden geçtiğini, neyi göremediğini ve düzeltmeleri gerçek çıktılarıyla anlatıyoruz.

Neden Bu Konu?

Yapay zekâya bir algoritma yazdırıp “testini de yaz” dediğinizde genellikle şuna benzer bir test gelir:

for _ in range(1000):
    data = [random.randint(-50, 50) for _ in range(random.randint(0, 60))]
    assert merge_sort(data) == sorted(data)

Bu iyi bir test. Bin rastgele liste, Python’ın kendi sorted() fonksiyonuyla karşılaştırılıyor. Ağaç için de benzeri yazılır: sayıları karıştır, ağaca ekle, hepsini ara, sıra içi dolaşımın sıralı çıktığına bak. İki test de geçiyor.

Sorun şu: testi yazan da kodu yazan da aynı varsayımla çalışıyor. Rastgele tamsayılar, eşit değerlerin hangi sırada çıktığını göremez, çünkü iki 22 birbirinden ayırt edilemez. Karıştırılmış sayılar da ağacın en kötü durumunu göremez, çünkü karıştırma ağacı kendiliğinden dengeli tutar. Kodun zayıf olduğu yer, testin hiç bakmadığı yerdir.

2 Kasım yazımızda regex desenlerinde aynı durumu görmüştük: örnek girdiler düz ASCII olduğu için sorunlar görünmüyordu. Burada da örnek girdiler ve testler “iyi huylu”.

Proje bilgisi Yazarlar: Ahmet Aksoy & Claude · Tarih: 02.11.2026 Ortamlar: Python 3.12.3 (Ubuntu 24.04) ve Docker’da python:3.9-slim, 3.11-slim, 3.13-slim, 3.14-slim, 3.15-slim. Sonuçlar süre ölçümleri ve bir satırdaki tek sayı dışında aynı. İncelenen projeler: 31, 32 · Örnek kod: proje 51

Önce Testler: Hepsi Geçiyor

Proje 51’deki betik, özgün kodu (“says”) ve düzeltilmiş kodu (“checks”) aynı testlerden geçiriyor. İlk bölümün çıktısı:

== 1. The typical tests ==
  says merge_sort        1000 random int lists == sorted(): True
  checks merge_sort      1000 random int lists == sorted(): True
  says tree              1000 shuffled inserts, search + in-order: True
  checks tree            1000 shuffled inserts, search + in-order: True

Özgün kod da düzeltilmiş kod da geçiyor. Yani bu testler iki sürümü birbirinden ayıramıyor. Aşağıdaki dört bulgunun hiçbiri bu testlerle görünmüyor.

1. Merge Sort Eşit Değerlerin Sırasını Bozuyor

Bir sıralama algoritması, eşit değerli elemanları girdideki sıralarıyla bırakıyorsa ona kararlı (stable) denir. Python’ın sorted() ve list.sort() fonksiyonları kararlı olduklarını garanti eder. Merge sort da ders kitaplarında kararlı algoritmaların tipik örneğidir. Özgün kodun belge yorumu bile “O(n log n) stable across all cases” diyor. Oradaki “stable” kelimesi sürenin her durumda aynı kaldığını anlatıyor, ama okuyan herkes algoritmanın kararlı olduğunu düşünür.

Birleştirme adımındaki karşılaştırma şöyle:

if left[i] < right[j]:
    sorted_result.append(left[i])
    i += 1
else:
    sorted_result.append(right[j])
    j += 1

İki değer eşitse < yanlış döner ve sağdaki eleman önce alınır. Sağdaki eleman girdide daha sonra geliyordu. Yani her eşitlikte sıra ters çevriliyor.

Tamsayılarla bunu görmek imkânsız. Kayıtlarla görmek kolay. Puanına göre sıralanan dört öğrenci aldık. Ayse, Berk ve Deniz aynı puanı (1) paylaşıyor:

== 2. merge sort and equal keys ==
  input                  Ayse Can Berk Deniz   (Ayse, Berk, Deniz share score 1)
  sorted()               Can Ayse Berk Deniz
  says                   Can Deniz Berk Ayse
  checks                 Can Ayse Berk Deniz

sorted() eşit puanlıları girdideki sırasıyla bırakıyor. Özgün merge sort onları tam tersine çeviriyor.

Bunun bir önemi var mı? Kararlılık, iki aşamalı sıralamanın temelidir. Bir listeyi önce ada, sonra puana göre sıralarsanız, kararlı bir algoritmada aynı puanlılar ada göre sıralı kalır. Python belgelerindeki “Sort Stability and Complex Sorts” bölümü tam bu yöntemi anlatıyor. Özgün kodla denedik:

  score, then name       expected Ali Bora Cem Dila Eda
  says (two passes)      Bora Ali Eda Dila Cem
  checks (two passes)    Ali Bora Cem Dila Eda

İkinci aşama birinci aşamanın işini geri alıyor. Aynı puanlı öğrenciler alfabenin tersine diziliyor.

Düzeltme tek karakter: < yerine <=. Eşitlikte soldaki, yani girdide önce gelen eleman alınır:

if left[i] <= right[j]:  # on a tie take the left one: this keeps the sort stable

Kodun tip ipucu list[int], yani yazar yalnızca tamsayı düşünmüş olabilir. Ama Python tip ipucunu zorlamaz. Fonksiyon kayıtlarla, demetlerle ya da karşılaştırılabilen her nesneyle sessizce çalışır. Bir sonraki adımda yapay zekâdan “buna bir key parametresi ekle” isterseniz, eşitlik artık sık görülen bir durum olur ve sorun ortaya çıkar.

Bu arada bubble_sort kararlı, çünkü yalnızca data[j] > data[j + 1] olduğunda yer değiştiriyor. Basit algoritma doğru, “gelişmiş” olan yanlış.

2. Kısa Listede Sizin Listenizi Geri Veriyor

Özgün yazı, kodun “orijinal veriyi kopyalayarak dış dünyadaki veriyi istem dışı değiştirmesini engellediğini” söylüyordu. Bu bubble_sort için doğru. merge_sort ise bir ya da sıfır elemanlı listelerde şunu yapıyor:

if len(arr) <= 1:
    return arr

Yeni bir liste değil, çağıranın kendi listesi dönüyor. Sonucu değiştirdiğinizde orijinal de değişiyor:

== 3. merge sort and short lists ==
  says                   same object: True   original after append: [42, -1]
  checks                 same object: False  original after append: [42]

Daha uzun listelerde sorun yok, çünkü arr[:mid] dilimleme işlemi zaten kopya üretiyor. Bu yüzden betikteki 10 elemanlı örnekte “orijinal korundu” mesajı doğru çıkıyor. Hata yalnızca sınırda görünüyor: bir kullanıcının tek ürünlü sepeti, tek satırlık bir rapor. Düzeltme: return list(arr). sorted() da her zaman yeni bir liste döndürür.

Küçük bir çelişki daha: bubble_sort‘un belge yorumu “Sorts a mutable list in place” ve “O(1) auxiliary” diyor. Hemen altındaki satır data = list(arr) ile kopya alıyor ve yeni liste döndürüyor. Özgün yazı da “Bubble Sort’un mevcut dizi üzerinde işlem yaptığını (in-place) fark ettik” diyordu. Kodun davranışı doğru, yorum ve yazı yanlış.

3. Sıralı Veride Ağaç Zincire Dönüyor ve Çöküyor

İkili arama ağacında her değer, kendisinden küçükse sola, büyük ya da eşitse sağa yerleşir. Sayılar karışık geldiğinde ağaç dengeli büyür. Peki sayılar zaten sıralı gelirse? 0 köke yerleşir, 1 onun sağına, 2 onun sağına… Ağaç bir zincire, yani bağlı bir listeye dönüşür. Yüksekliği eleman sayısına eşit olur.

Özgün kodun ekleme, arama ve dolaşım metotlarının üçü de özyinelemeli. Her düğüm için fonksiyon kendini bir kez daha çağırıyor. Python’ın varsayılan özyineleme sınırı 1000:

== 4. sorted input and the recursive tree ==
  says, 900 sorted       ok, height 900
  says, 1000 sorted      RecursionError after 997 inserts
  checks, 1000 sorted    ok, height 1000

900 sıralı sayı sorunsuz. 1000 sıralı sayıda ağaç 997. eklemeden sonra RecursionError veriyor. Eşiği beş Python sürümünde (3.11–3.15) ayrı ayrı aradık. Ekleme, arama ve sıra içi dolaşım 996 ile 999 eleman arasında çöküyor. Fark, çağrı yığınında zaten kaç fonksiyon olduğundan geliyor.

Sıralı veri uç bir durum değil. Otomatik artan kayıt numaraları, zaman damgaları, bir veritabanından ORDER BY ile okunan satırlar, alfabetik bir dosya listesi hep sıralı gelir. Ağaç örneğindeki [50, 30, 70, 20, 40, 60, 80] ise tam dengeli bir ağaç üreten bir sıra. Örnek, kodun en iyi durumunu gösteriyor.

Düzeltme: Üç metodu döngüyle yazmak. Arama örneği:

def search(self, target):
    node = self.root
    while node is not None:
        if target == node.value:
            return True
        node = node.left if target < node.value else node.right
    return False

Ekleme de aynı şekilde döngüyle yazılıyor. Sıra içi dolaşım için açık bir yığın (liste) kullanılıyor. Kodun tamamı proje 51’de. sys.setrecursionlimit() ile sınırı yükseltmek de akla gelebilir, ama bu sorunu ertelemekten öteye geçmez: sınır yükseldikçe Python’ın kendi C yığını tükenebilir ve program bu kez RecursionError yerine doğrudan çöker.

4. “O(log n)” Yalnızca Dengeli Ağaçta Geçerli

Döngüyle yazılan ağaç artık çökmüyor. Ama zincir hâlâ zincir. Özgün yazı “milyonlarca elemanlı bir ağaçta bile birkaç karşılaştırmayla sonuca ulaşabiliyoruz” diyordu. Kod yorumunda da “O(log n) average time” yazıyor. “Ortalama” kelimesi, verinin rastgele sırada geldiği varsayımına dayanıyor. Aynı 10 000 sayıyı karışık ve sıralı olarak ekledik:

== 5. 'O(log n)' needs a balanced tree ==
  checks, 10000 shuffled height    34  build   0.03 s  2000 lookups  0.006 s
  checks, 10000 sorted   height 10000  build   5.77 s  2000 lookups  1.541 s
  bisect list, 10000 sorted               build   0.01 s  2000 lookups  0.002 s

Karışık veride ağacın yüksekliği 34, sıralı veride 10 000. Sıralı veride ağacı kurmak yaklaşık 190 kat, aramak yaklaşık 250 kat yavaş. Eleman sayısı iki katına çıktığında kurma süresi dört katına çıkıyor. 20 000 sıralı sayıda kurma 23 saniye sürdü.

Gerçek çözüm, kendini dengeleyen bir ağaç (AVL, kırmızı-siyah ağaç). Özgün yazı bunları “sonraki adım” olarak öneriyordu. Asıl ihtiyacınız “sıralı bir koleksiyon ve hızlı arama” ise Python’da çoğu zaman ağaca hiç gerek yok. Tablonun son satırı standart kütüphanedeki bisect modülüyle sıralı tutulan sıradan bir liste. Ekleme teoride O(n), çünkü elemanlar kaydırılıyor, ama bu kaydırma C’de tek bir bellek kopyalama işlemiyle yapılıyor. Bu ölçekte hem kurma hem arama bizim ağacımızın karışık verideki hızına yakın ya da ondan iyi. Sıra gerekmiyorsa set ve dict zaten ortalama O(1).

Dördü Bir Arada

Betiğin tamamı (proje 51) yalnızca standart kütüphaneyi kullanıyor ve Python 3.9 veya daha yenisinde çalışıyor. Kendi bilgisayarımızdaki çıktısı:

Python 3.12.3

== 1. The typical tests ==
  says merge_sort        1000 random int lists == sorted(): True
  checks merge_sort      1000 random int lists == sorted(): True
  says tree              1000 shuffled inserts, search + in-order: True
  checks tree            1000 shuffled inserts, search + in-order: True

== 2. merge sort and equal keys ==
  input                  Ayse Can Berk Deniz   (Ayse, Berk, Deniz share score 1)
  sorted()               Can Ayse Berk Deniz
  says                   Can Deniz Berk Ayse
  checks                 Can Ayse Berk Deniz
  score, then name       expected Ali Bora Cem Dila Eda
  says (two passes)      Bora Ali Eda Dila Cem
  checks (two passes)    Ali Bora Cem Dila Eda

== 3. merge sort and short lists ==
  says                   same object: True   original after append: [42, -1]
  checks                 same object: False  original after append: [42]

== 4. sorted input and the recursive tree ==
  says, 900 sorted       ok, height 900
  says, 1000 sorted      RecursionError after 997 inserts
  checks, 1000 sorted    ok, height 1000

== 5. 'O(log n)' needs a balanced tree ==
  checks, 10000 shuffled height    34  build   0.03 s  2000 lookups  0.006 s
  checks, 10000 sorted   height 10000  build   5.77 s  2000 lookups  1.541 s
  bisect list, 10000 sorted               build   0.01 s  2000 lookups  0.002 s

Betiği Docker’da Python 3.9, 3.13 ve 3.15’te de çalıştırdık. Süreler dışında tek fark 4. bölümde: 3.9 ve 3.13’te çöküş 997 yerine 996. eklemeden sonra geliyor. 12 Kasım yazımızda bu iki projenin sürüm iddialarını ayrıca incelemiştik.

Yapay Zekânın Yazdığı Algoritmayı Test Ederken Ne Arıyoruz?

  • Eşit değerlerle denendi mi? Sıralama, gruplama ya da birleştirme yapan her kodu, aynı anahtara sahip ama birbirinden ayırt edilebilen kayıtlarla deneyin. Tamsayılar eşitliği gizler.
  • Sıralı, ters sıralı ve hep aynı değerden oluşan girdiler denendi mi? Rastgele veri ortalama durumu test eder. Ağaçlar, hızlı sıralama (quicksort) ve özyinelemeli her algoritma için en kötü durum genellikle sıralı veridir.
  • Sınırlar denendi mi? Boş liste, tek elemanlı liste, sınırın bir altı ve bir üstü. merge_sort‘un tek elemanlı listede orijinali geri vermesi ancak orada görünür.
  • Özyineleme derinliği veriye mi bağlı? Derinlik log n ise sorun yok. Derinlik n olabiliyorsa yaklaşık 1000 elemanda çöküş var demektir.
  • Karmaşıklık iddiası ölçüldü mü? Eleman sayısını iki katına çıkarıp süreye bakmak yeter. O(n log n) bir algoritmada süre iki katın biraz üstüne, O(n²) bir algoritmada dört katına çıkar.
  • Hazır bir çözüm var mı? sorted(), bisect, heapq, set ve dict yıllardır test ediliyor. Öğrenmek için algoritma yazmak güzel. Gerçek veriniz için yazdırdığınız algoritma ise bu yazıdaki testlerden geçmeden kullanılmamalı.

Bu dört hatanın hiçbiri yapay zekâya özgü değil. Merge sort’taki < ile <= farkı, bilinen ve insanların da sık yaptığı bir hatadır. Yapay zekâ bu kalıpları insanların yazdığı koddan öğrendi. Bizim önerimiz şu: yapay zekâdan bir algoritma istediğinizde, testlerini de ondan isteyin, ama girdi listesini kendiniz verin. “Eşit anahtarlı kayıtlar, sıralı 10 000 sayı, tek elemanlı liste” demek yeterli. Bu yazıdaki girdileri doğrudan kullanabilirsiniz.

Kodu Kendiniz Deneyin

Beş bölümün tamamı proje 51’de tek bir main.py dosyasında. Ek paket gerekmiyor:

python3 main.py
  1. bölüm sıralı ağacı kurarken birkaç saniye bekletebilir. Özgün kodlar 31 ve 32 numaralı projelerde duruyor. Kararlılık ve RecursionError sınırlamaları, 22 Ekim’deki README bakımından beri bu projelerin README dosyalarında not olarak duruyordu. Bu yazıyla 31’e tek elemanlı liste notunu, ikisine de bu yazının bağlantısını ekledik.

Kaynaklar

Ahmet Aksoy & Claude

Not: Bu yazıda incelediğimiz kodu ve benzer projelerin kaynak kodlarını https://github.com/ahmetax/practical-python-examples adresinde bulabilirsiniz.

Bir Yanıt Bırak

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir