Karşılaştırma ve Sıralama

Önceki dört ders bir kabın kendi ögesine verdiği sözleri ölçtü. Sıralama bunlardan farklı bir soru sorar: bir kabın ögelerini hangi sırayla vereceğine kim karar veriyor? Bazen karar tipin kendi içindedir, bazen çağıranın elinde ayrı bir nesnedir — ve bu ders o ayrımı açıp, dışarıdan verilen kuralın kendi kusurlarını nereye düşürdüğünü ölçüyor.

Önceki dersin gösterdiği kalıp burada da sürüyor: bir kural derlenebilir, çoğu girdide doğru çalışabilir ve yine de belirli bir girdide ya sessizce yanlış sonuç üretebilir ya da adıyla düşebilir. Sıralamanın farkı, kuralın artık kabın dışında, çağıranın yazdığı bir nesnede durmasıdır — ve bu nesnenin kendi iç tutarlılığı, kabın davranışından önce sınanması gereken ayrı bir konudur.

Doğal Sıra Tipin Sözü, Karşılaştırıcı Çağıranın Sözü

Bir tip Comparable’ı gerçekleştirip kendi compareTo’sunu yazdığında, bu sıraya doğal sıra denir ve tipin kendi tanımının bir parçasıdır — sınıfın içinde durur, sınıfla birlikte derlenir. Comparator ise böyle değildir: çağıranın, sınıfa hiç dokunmadan, çağrı yerinde yazdığı ayrı bir nesnedir.

• KO21 — Aynı üç kayıt iki ayrı sırayla dizilir: biri kaydın kendi compareTo’suyla (ada göre), öteki çağıranın verdiği bir Comparator’la (uzunluğa göre). Kayıt sınıfı ikisinde de aynıdır.

// DogalSira.java — dogal sira tipin icinde, karsilastirici disarida
import java.util.*;

public class DogalSira {
    record Kayit(String ad, int uzunluk) implements Comparable<Kayit> {
        @Override public int compareTo(Kayit o) { return ad.compareTo(o.ad); }
    }

    public static void main(String[] args) {
        List<Kayit> liste = new ArrayList<>(List.of(
                new Kayit("zulu", 4), new Kayit("delta", 5), new Kayit("alfa", 4)));

        List<Kayit> dogal = new ArrayList<>(liste);
        Collections.sort(dogal);
        System.out.println("dogal sira (Kayit.compareTo, ada gore)           : " + dogal);

        List<Kayit> disaridan = new ArrayList<>(liste);
        disaridan.sort(Comparator.comparingInt(Kayit::uzunluk));
        System.out.println("disaridan verilen karsilastirici (uzunluga gore) : " + disaridan);
    }
}

dogal sira (Kayit.compareTo, ada gore)           : [Kayit[ad=alfa, uzunluk=4], Kayit[ad=delta, uzunluk=5], Kayit[ad=zulu, uzunluk=4]]
disaridan verilen karsilastirici (uzunluga gore) : [Kayit[ad=zulu, uzunluk=4], Kayit[ad=alfa, uzunluk=4], Kayit[ad=delta, uzunluk=5]]

Aynı üç kayıt, aynı List, aynı sort çağrısı ailesi — ve iki ayrı sonuç. Collections .sort(dogal) hiçbir sıralama bilgisi almıyor, çünkü Kayit’in kendisi zaten compareTo yazarak bir söz vermiş durumda; bu sözün nerede yazıldığı bellidir ve tek bir yerdedir. disaridan.sort(...) ise tam tersini yapıyor: Kayit sınıfı hiç değişmeden, çağıran kendi kuralını (uzunluk) çağrı satırında tanımlıyor. İki sıralamanın da geçerli olması, sıralamanın tek bir doğrusu olmadığını gösteriyor — geçerli olan, hangi sözün kullanıldığının açık olmasıdır.

Bu ayrımın önemi, compareTo’nun sınıfla birlikte derlenmesinden geliyor: Kayit sınıfını elinde bulunduran her kod aynı doğal sırayı görür, çünkü söz sınıfın kendi dosyasında bir kez yazılmıştır. Comparator ise her çağrı yerinde yeniden yazılabilir; aynı Kayit listesi bir yerde ada göre, başka bir yerde uzunluğa göre, üçüncü bir yerde başka bir alana göre sıralanabilir ve üçü de aynı ölçüde geçerlidir. Doğal sıra “bu tipin tek bir kanonik sırası vardır” iddiasını taşır; karşılaştırıcı böyle bir iddiada bulunmaz, yalnızca o çağrının ihtiyacına göre bir sıra sağlar.

Kararlı Sıralama: Arayüzün Kendi Garantisi

List.sort yalnızca bir sıra üretmiyor; eşit sayılan ögelerin göreli sırasını da koruyacağını belgesinde yazıyor. Bu sözün gerçekten iki ayrı gerçekleştirimde de aynı çıkıp çıkmadığı ölçülebilir.

• KO22 — Aynı yedi kayıt, her biri bir anahtar ve bir ilk sıra numarasıyla, ArrayList ve LinkedList’e aynı sırayla yazılır. Anahtar tekrar ediyor; ilk sıra numarası tekildir ve sıralama sonrası hangi kaydın önce geldiğini okumaya yarıyor.

// Kararlilik.java — kararli siralama iki liste gerceklestiriminde de ayni mi
import java.util.*;

public class Kararlilik {
    record Oge(int anahtar, int ilkSira) {}

    public static void main(String[] args) {
        List<Oge> kaynak = new ArrayList<>();
        int[] anahtarlar = {3, 1, 3, 2, 1, 3, 2};
        for (int i = 0; i < anahtarlar.length; i++) kaynak.add(new Oge(anahtarlar[i], i));

        List<Oge> dizi = new ArrayList<>(kaynak);
        List<Oge> baglantili = new LinkedList<>(kaynak);
        dizi.sort(Comparator.comparingInt(Oge::anahtar));
        baglantili.sort(Comparator.comparingInt(Oge::anahtar));

        System.out.println("ArrayList sonrasi  : " + dizi);
        System.out.println("LinkedList sonrasi : " + baglantili);
        System.out.println("iki sonuc birebir ayni mi : " + dizi.equals(baglantili));
    }
}

ArrayList sonrasi  : [Oge[anahtar=1, ilkSira=1], Oge[anahtar=1, ilkSira=4], Oge[anahtar=2, ilkSira=3], Oge[anahtar=2, ilkSira=6], Oge[anahtar=3, ilkSira=0], Oge[anahtar=3, ilkSira=2], Oge[anahtar=3, ilkSira=5]]
LinkedList sonrasi : [Oge[anahtar=1, ilkSira=1], Oge[anahtar=1, ilkSira=4], Oge[anahtar=2, ilkSira=3], Oge[anahtar=2, ilkSira=6], Oge[anahtar=3, ilkSira=0], Oge[anahtar=3, ilkSira=2], Oge[anahtar=3, ilkSira=5]]
iki sonuc birebir ayni mi : true

İki dizi de anahtara göre sıralı ve her anahtar grubunun içinde ilkSira artan: 1 anahtarlı iki kayıt 1, 4 sırasıyla, 3 anahtarlı üç kayıt 0, 2, 5 sırasıyla duruyor — hiçbiri yer değiştirmedi. ArrayList dizi tabanlı, LinkedList düğüm tabanlı; iki ayrı iç yapı olmasına karşın sonuç birebir aynı. Bu, önceki derslerde ölçülen “gezinme sırası” gibi gerçekleştirime bırakılmış bir şey değil: List.sort kararlılığı doğrudan kendi sözleşmesinde şart koşuyor ve iki gerçekleştirim de bu şartı aynen tutuyor. Kararlı sıralama burada arayüzün sözü, seçilen sınıfın tercihi değil.

Bu, önceki derste ölçülenle keskin bir tezat oluşturuyor: gezinme sırası, boş anahtar kabulü gibi sorular gerçekleştirime bırakılmıştı ve üç aile arasında ayrışıyordu. Kararlılık öyle değil — List arayüzünün sort yöntemi tanımı, bu yöntemi gerçekleştiren her sınıfı bağlıyor. Bir yöntemin sözleşmesi bazen “her gerçekleştirim aynı yanıtı verir” der, bazen “gerçekleştirim seçer” der; ikisi de aynı arayüzün içinde yan yana durabilir ve hangisinin hangi olduğu yalnızca belgeye bakılarak değil, birden çok gerçekleştirim koşturularak da doğrulanabilir.

Çağıranın Kuralı: Karşılaştırıcı equals İle Uyumsuz Olduğunda

Bir TreeSet ya da TreeMap tekilliği equals ile değil, verilen karşılaştırıcının 0 dönüp dönmediğiyle belirliyor. Karşılaştırıcı iki farklı ögeyi eşit sayarsa ne olur?

• KO23 — İki kayıt equals ile farklıdır (adları farklı) ama uzunlukları aynıdır. Uzunluğa göre kuran bir TreeSet’e ve adlara bakan bir HashSet’e aynı iki kayıt eklenir.

// Uyumsuz.java — karsilastirici equals ile uyumsuz olunca sirali kume ne yapiyor
import java.util.*;

public class Uyumsuz {
    record Kayit(String ad, int uzunluk) {}

    public static void main(String[] args) {
        Kayit a = new Kayit("elma", 4);
        Kayit c = new Kayit("kivi", 4);
        System.out.println("a.equals(c) : " + a.equals(c));

        Set<Kayit> siraliKume = new TreeSet<>(Comparator.comparingInt(Kayit::uzunluk));
        siraliKume.add(a);
        siraliKume.add(c);
        System.out.println("uzunluga gore siralanan kume boyutu : " + siraliKume.size());
        System.out.println("kume icerigi                        : " + siraliKume);

        Set<Kayit> hashKume = new HashSet<>();
        hashKume.add(a);
        hashKume.add(c);
        System.out.println("HashSet boyutu (ayni iki kayit)      : " + hashKume.size());
    }
}

a.equals(c) : false
uzunluga gore siralanan kume boyutu : 1
kume icerigi                        : [Kayit[ad=elma, uzunluk=4]]
HashSet boyutu (ayni iki kayit)      : 2

equals iki kaydı farklı buluyor; HashSet bunu doğru yansıtıyor, boyut 2. TreeSet ise anahtarını hiç equals’a sormuyor — yalnız karşılaştırıcıyı çağırıyor ve uzunluklar eşit olduğu için 0 dönüyor. TreeSet’in tekillik kuralı “compareTo/ Comparator 0 dönerse aynı ögedir” diyor; ikinci add çağrısı bu yüzden bir ekleme değil, birinci ögenin üzerine yazma girişimi sayılıyor ve boyut 1’de kalıyor. Kusur derlenirken görünmüyor, hiçbir istisna da fırlamıyor — kivi sessizce kayboluyor.

Bu, önceki derste ölçülen “equals yazıp hashCode yazmamak” kusuruyla aynı aileden ama ayrı bir mekanizmadan geliyor. Orada eksik olan hashCode’du ve sonuç aramanın bulamamasıydı. Burada hiçbir yöntem eksik değil; equals de compareTo/Comparator da tam yazılmış, ama ikisi birbiriyle tutarsız. TreeSet ve TreeMap’in kendi belgeleri bu tutarlılığı açıkça talep eder: karşılaştırıcının equals ile “uyumlu” olması beklenir, ama bu beklenti derleyicinin denetleyebileceği bir tip kısıtı değildir — yalnızca bir sözleşme cümlesidir ve çağıran onu okumazsa hiçbir uyarı almaz.

Geçişli Olmayan Karşılaştırıcı: Küçükte Sessiz, Büyükte İstisna

Bir karşılaştırıcının ikinci yükümlülüğü geçişliliktir: a b’den küçükse ve b c’den küçükse, a da c’den küçük olmalıdır. Bu tutulmazsa ne olur?

• KO24 — Aynı sayılar üç gruba (% 3 kalanına göre) ayrılır ve karşılaştırıcı bu üç grubu döngüsel bir sırayla karşılaştırır: 0. grup 1’den küçük, 1. grup 2’den küçük, 2. grup 0’dan küçük. Bu döngü geçişliliği baştan bozar. Aynı sabit tohumla üretilmiş rastgele sayılar iki ayrı büyüklükte (50 ve 100) sıralanır.

// TamOlcum.java — gecisli olmayan karsilastirici kucukte sessiz, buyukte istisna
import java.util.*;

public class TamOlcum {
    static int karsilastir(int x, int y) {
        int tx = x % 3, ty = y % 3;
        if (tx == ty) return 0;
        if ((tx == 0 && ty == 1) || (tx == 1 && ty == 2) || (tx == 2 && ty == 0)) return -1;
        return 1;
    }

    static int ihlalSayisi(Integer[] dizi) {
        int sayac = 0;
        for (int i = 0; i < dizi.length; i++)
            for (int j = i + 1; j < dizi.length; j++)
                if (karsilastir(dizi[i], dizi[j]) > 0) sayac++;
        return sayac;
    }

    static Integer[] rasgeleDizi(int n) {
        Integer[] dizi = new Integer[n];
        Random r = new Random(42);
        for (int i = 0; i < n; i++) dizi[i] = r.nextInt(1_000_000);
        return dizi;
    }

    public static void main(String[] args) {
        Integer[] kucuk = rasgeleDizi(50);
        Arrays.sort(kucuk, TamOlcum::karsilastir);
        System.out.println("n=50  -> istisna yok, ihlal sayisi=" + ihlalSayisi(kucuk));

        Integer[] buyuk = rasgeleDizi(100);
        try {
            Arrays.sort(buyuk, TamOlcum::karsilastir);
            System.out.println("n=100 -> istisna yok (beklenmiyordu)");
        } catch (IllegalArgumentException e) {
            System.out.println("n=100 -> " + e.getClass().getSimpleName());
        }
    }
}

n=50  -> istisna yok, ihlal sayisi=195
n=100 -> IllegalArgumentException

Elli ögelik dizi sessizce sıralanıyor — hiçbir istisna yok — ama sonuç, karşılaştırıcının kendi kuralına göre bile yanlış: her biri bir çift ögenin döngüsel kuralı ihlal ettiği 195 durum var, yani dizi tutarlı bir sıraya hiç oturmamış, yalnızca öyleymiş gibi görünüyor. Yüz ögelik dizide ise algoritmanın iç birleştirme adımları kendi varsaydığı düzenin tutmadığını tespit ediyor ve adıyla bir istisna fırlatıyor: “karşılaştırma yöntemi kendi genel sözleşmesini ihlal ediyor.” Eşik veriye bağlıdır ve burada 50 ile 100 arasında bir yerdedir; küçük diziler sıralama algoritmasının iç tutarlılık denetimini tetiklemeye yetecek kadar iş yapmadan bitebiliyor, büyük diziler bu denetime takılıyor. Geçişsizlik iki ayrı bedel ödetiyor: küçük ölçekte sessiz yanlış sonuç, büyük ölçekte istisna.

Bu iki bedel arasındaki fark, sıralama algoritmasının kendi iç yapısından geliyor. Küçük girdilerde sıralama algoritması veriyi daha az bölüp birleştirerek işliyor ve karşılaştırıcının döngüsel çelişkisiyle hiç karşılaşmadan bitebiliyor; girdi büyüdükçe algoritmanın kendi ürettiği ara parçaları birleştirirken tuttuğu bir iç varsayım (birleştirilen iki parçanın kendi içinde tutarlı sıralı olduğu) karşılaştırıcının çelişkisi yüzünden bozuluyor ve algoritma bunu kendi kontrolüyle yakalıyor. Bu denetim Comparator arayüzünün bir sözü değil, seçilen sıralama algoritmasının bir iç güvenlik önlemi; başka bir algoritma aynı veriyle hiç istisna vermeden, yalnızca yanlış bir sonuçla dönebilirdi.

Sınırlayıcı Ölçüm: Kusuru Doğuran Karşılaştırıcı Değil, Kabın Kullanımı

Bir önceki iki ölçüm karşılaştırıcının kendisini kusurlu gösteriyor gibi görünebilir. Aynı uzunluk karşılaştırıcısı bu kez yalnızca sıralamak için, bir TreeSete değil bir List’e verilirse ne olur?

• KO25 — Aynı uyumsuz karşılaştırıcı (Uyumsuz.java’daki uzunluk karşılaştırıcısı) bu kez üç kayıtlık bir listeyi sıralamak için kullanılır; kayıtlardan ikisi aynı uzunlukta ama equals ile farklıdır.

// ListedeGorunmuyor.java — ayni karsilastirici listede hicbir ogeyi kaybetmiyor
import java.util.*;

public class ListedeGorunmuyor {
    record Kayit(String ad, int uzunluk) {}

    public static void main(String[] args) {
        List<Kayit> liste = new ArrayList<>(List.of(
                new Kayit("armut", 5), new Kayit("elma", 4), new Kayit("kivi", 4)));
        liste.sort(Comparator.comparingInt(Kayit::uzunluk));
        System.out.println("siralanmis liste boyutu : " + liste.size());
        System.out.println("siralanmis liste        : " + liste);
    }
}

siralanmis liste boyutu : 3
siralanmis liste        : [Kayit[ad=elma, uzunluk=4], Kayit[ad=kivi, uzunluk=4], Kayit[ad=armut, uzunluk=5]]

Üç kayıt da yerinde; elma ile kivi aynı uzunlukta olduğu için yan yana duruyor, ama ikisi de listede kalıyor ve kararlılık gereği elma (girdide önce gelen) kivi’den önce yazılıyor. TreeSet ölçümünde kivi kaybolmuştu; burada kaybolmuyor. Fark karşılaştırıcıda değil, karşılaştırıcının nasıl kullanıldığındadır: List.sort onu yalnızca bir sıralama kuralı olarak okuyor ve 0 dönmesi hiçbir ögeyi silmiyor, yalnızca iki ögeyi yan yana bırakıyor. TreeSet ise aynı 0 dönüşünü tekillik kararı olarak okuyor. Aynı nesne, aynı yöntem, aynı dönüş değeri — iki ayrı kap onu iki ayrı soruya yanıt sayıyor. Kusuru doğuran karşılaştırıcının kendisi değil, onu tekillik kararı olarak kullanan kaptır.

Bu son ölçüm dersin bütün ipliklerini birbirine bağlıyor. Bir karşılaştırıcı yazmak başlı başına bir kusur değildir; kusur, o karşılaştırıcının hangi kabın elinde, hangi soruya yanıt vermek için kullanıldığında ortaya çıkar. List.sort ona yalnızca “hangi önce gelsin” diye sorar ve 0 dönüşünü “ikisi de aynı yerde durabilir” diye okur. TreeSet aynı 0 dönüşünü “bunlardan yalnız biri var olabilir” diye okur. Karşılaştırıcı tek bir yöntemdir ve tek bir kararı taşır; onu hangi sorunun yanıtı sayacağına karar veren çağıranın seçtiği kaptır.

Özet

• Doğal sıra bir tipin kendi compareTo’sunda durur ve tipin tanımının parçasıdır; karşılaştırıcı çağıranın çağrı yerinde yazdığı, sınıfa hiç dokunmayan ayrı bir nesnedir. Aynı veri iki ayrı sırayla dizilebilir.
• Kararlı sıralama List.sort’un kendi sözüdür: ArrayList ve LinkedList’te birebir aynı sonucu, eşit anahtarlı ögelerin göreli sırasını bozmadan, üretiyor.
• Çağıranın kuralı: bir karşılaştırıcı equals’la uyumsuzsa, sıralı bir kümede 0 dönen iki öge tek bir öge olarak kalıyor — kusur hiçbir istisna vermeden, sessizce oluşuyor.
• Geçişli olmayan bir karşılaştırıcı küçük girdide sessizce yanlış bir sıra üretiyor, yeterince büyük girdide ise sıralama algoritmasının kendi tutarlılık denetimine takılıp adıyla düşüyor; eşik veriye bağlıdır.
• Sınırlayıcı ölçüm: aynı uyumsuz karşılaştırıcı bir listede hiçbir öge kaybetmiyor. Kusuru üreten karşılaştırıcının kendisi değil, onun dönüş değerini tekillik kararı olarak okuyan kaptır.

Sonraki Adım

Bu payda ölçülen her şey, sıra kuralının artık kabın içinde değil, dışarıdan verilen bir nesnede durduğunu gösterdi — Comparator da, Comparable’ı gerçekleştiren bir tip de, kabın kendisinden bağımsız yazılmış küçük birer sözleşmeydi. Sıradaki konu o nesnenin kendisine bakıyor: Comparator de dahil olmak üzere kütüphanenin tek yöntemli tipleri (fonksiyonel arayüzler) ne söz veriyor, ve bu söz çağrı yerinde bir lambda ile yazıldığında hangi garanti yerinde kalıyor, hangisi kayboluyor.