Bölüm 3: Diziler

3.1Dizi kavramı

Bir sınıftaki 40 öğrencinin sınav notlarını saklayan bir program düşünelim. Her not için ayrı bir değişken açmak (not1, not2, …, not40) hem yorucudur hem de işe yaramaz. Notların ortalamasını almak için kırk değişkeni tek tek yazmak gerekir. Öğrenci sayısı 41'e çıkınca program da değişmek zorunda kalır. Asıl ihtiyaç, kırk notu tek bir ad altında toplamak ve her birine bir sıra numarasıyla ulaşmaktır. Dizi tam olarak bu ihtiyacı karşılar.

3.1.1Dizi nedir?

Dizi (array), aynı türden birden çok veriyi tek bir ad altında, düzenli biçimde saklayan yapıdır. Dizideki her veriye öğe (element) denir. Öğeler bir sıra içinde durur ve her birinin bir sıra numarası vardır. Bu numaraya indis (index) denir. Java'da, C'de ve pek çok dilde indis 0'dan başlar: ilk öğenin indisi 0, ikincininki 1'dir.

Tanımdaki her ifadenin bir sonucu vardır:

• Aynı tür. Bir int dizisinde yalnız tamsayılar, bir String dizisinde yalnız metinler durur. Bütün öğeler aynı türden olduğu için bellekte aynı sayıda bayt kaplar. Bu eşitlik, bir öğenin yerini hesaplamayı kolaylaştırır.
• Sabit boyut. Dizinin boyutu dizi oluşturulurken belirlenir ve sonradan değiştirilemez. Beş öğelik bir diziye altıncı bir hücre eklenemez. Daha çok yer gerekirse daha büyük yeni bir dizi oluşturulur ve eski öğeler ona kopyalanır.
• Ardışık bellek. Öğeler bellekte arada boşluk olmadan, art arda dizilir. 0. öğenin hemen arkasında 1. öğe, onun arkasında 2. öğe gelir.

Boyutun sabit olması, dizideki değerlerin de sabit olduğu anlamına gelmez. Öğelerin değerleri her zaman güncellenebilir: 2. hücredeki 4, istenince 40 yapılabilir. Sabit olan, hücre sayısıdır. Bu yüzden dizide “ekleme” ve “silme”nin anlamı biraz farklıdır. Araya bir öğe eklemek, sağdaki öğeleri birer hücre kaydırıp yer açmak demektir. Bir öğeyi silmek de sağdaki öğeleri sola kaydırıp boşluğu kapatmaktır. Bu kaydırmaların maliyeti 3.5.5 ve 3.5.6'da ayrıntılı incelenir.

Şekil 3.1, diziyi düşünmenin en kullanışlı yolunu gösterir: yan yana dizilmiş, numaralı kutular. Kutuların içinde değerler, üstlerinde indisler durur. Değer ile indisi karıştırmamak önemlidir. Şekildeki dizide 2 indisli öğe 4'tür; değeri 2 olan öğe ise 3 indislidir.

Diziler, aynı türden çok sayıda verinin bir arada işlendiği her yerde kullanılır. Birkaç tanıdık örnek:

• Matris. Satır ve sütunlardan oluşan sayı tabloları, iki boyutlu dizilerle tutulur (3.4).
• Resim. Dijital bir resim, piksellerden oluşan bir ızgaradır. Her piksel bir renk değeri taşır ve ızgara iki boyutlu bir dizide saklanır.
• Ses. Kaydedilmiş bir ses, saniyede binlerce kez ölçülen genlik değerlerinden, yani örneklerden oluşur. Bu örnekler zaman sırasıyla tek boyutlu bir dizide durur.

3.1.2İndisle erişim ve adres hesabı

Dizinin bir öğesine ulaşmak için dizinin adı ve köşeli parantez içinde indis yazılır: diziAdi[indis]. Aşağıdaki kod beş öğeli bir dizi oluşturur, ilk ve son öğeyi okur:

int[] dizi = {7, 2, 9, 5, 1};
int ilkOge = dizi[0];      // 7
int sonOge = dizi[dizi.length - 1];      // 1

İlk öğenin indisi 0'dır, bu yüzden dizi[0] 7'yi verir. Son öğenin indisi ise uzunluğun bir eksiğidir. Java'da her dizi kendi uzunluğunu length alanında taşır; burada dizi.length 5'tir ve son öğe dizi[dizi.length - 1], yani dizi[4] = 1'dir. Son öğeye dizi[4] diye sabit bir sayıyla değil de length üzerinden ulaşmak, dizinin boyu değişse de doğru çalışan kod yazmayı sağlar.

İndisin neden 0'dan başladığı, öğelerin bellekte nasıl bulunduğuyla ilgilidir. Bellek, her birinin bir numarası (adresi) olan baytlardan oluşur. Dizi oluşturulduğunda, bütün öğeleri sığacak kadar ardışık bir bellek bölgesi ayrılır. Bu bölgenin ilk baytının adresine dizinin başlangıç adresi denir. Bir int 4 bayt kapladığı için 0. öğe başlangıç adresinde, 1. öğe 4 bayt ötede, 2. öğe 8 bayt ötede durur. Genel olarak i. öğenin adresi şöyle hesaplanır:

adres(i) = başlangıç + i × öğe boyutu

İndis 0'dan başladığı için ilk öğenin adresi doğrudan başlangıç adresidir; formülde ek bir “−1” gerekmez. İndis, aslında öğenin başlangıçtan kaç öğe uzakta olduğunu söyler.

Bu hesap, dizinin en büyük üstünlüğünün kaynağıdır. Bir öğeye erişmenin süresi, dizinin kaç öğeli olduğuna ve istenen öğenin nerede durduğuna bağlı değildir. Beş öğeli bir dizide de beş milyon öğeli bir dizide de dizi[i] aynı sürede okunur. Bu özelliğe rastgele erişim (random access) denir; buradaki “rastgele”, “istenen herhangi bir öğeye doğrudan” anlamındadır. Erişimin maliyeti O(1)'dir (3.5.2).

3.1.3Dizi türleri

Diziler, öğelerin kaç yönde dizildiğine göre adlandırılır. Şekil 3.2 üç türü yan yana gösterir.

• Tek boyutlu dizi. Öğeler tek bir satırda saklanır ve her öğeye tek bir indisle ulaşılır. Şimdiye kadarki örneklerin hepsi tek boyutludur. Java'da tanımı: int[] a = new int[5];
• İki boyutlu dizi (two-dimensional array). Öğeler satırlar ve sütunlar hâlinde, bir tablo gibi saklanır. Böyle bir tabloya matris (matrix) da denir. Her öğeye iki indisle, önce satır sonra sütun numarasıyla ulaşılır. Tanımı: int[][] m = new int[3][3];
• Çok boyutlu dizi (multidimensional array). İkiden çok indis gerektiren düzenlerdir. Örneğin bir videonun kareleri zaman × satır × sütun biçiminde üç indisle tutulabilir. Tanımı: int[][][] k = new int[3][3][3];

Her yeni boyut, Java tanımında bir çift köşeli parantez ekler. Öğe sayısı da boyutların çarpımıdır: new int[3][3] 9, new int[3][3][3] 27 öğe içerir. Çok boyutlu dizilerin Java'da bellekte nasıl tutulduğu ilk bakışta sanıldığı gibi değildir; bu konu 3.4.2'de işlenir.

3.1.4Avantajlar ve dezavantajlar

Dizi her işe uygun bir yapı değildir. Bir problem için veri yapısı seçerken, dizinin nerede güçlü, nerede zayıf olduğunu bilmek gerekir. Tablo 3.1 iki tarafı karşılaştırır.

Avantajların çoğu ardışık bellekten gelir. Erişimin hızlı olmasının nedeni 3.1.2'deki adres hesabıdır. “Ek referans yükü yok” ifadesi, bağlı yapılarla karşılaştırınca daha iyi anlaşılır. Bağlı bir listede her öğe, bir sonraki öğenin yerini gösteren bir referansı da yanında taşır; bu referanslar ek bellek kaplar. Dizide ise sıradaki öğenin yeri zaten bellidir: hemen yanıdır. Böylece bellek yalnız veriye harcanır.

Önbellek (cache) dostluğu da ardışıklıktan doğar. İşlemci ana bellekten veriyi tek tek bayt olarak değil, bloklar hâlinde okur ve bu blokları işlemcinin yanındaki küçük ve çok hızlı önbellekte tutar. Bir dizinin 0. öğesi okunduğunda, aynı bloktaki 1., 2., 3. öğeler de önbelleğe gelmiş olur. Dizi baştan sona gezilirken sonraki öğelerin çoğu önbellekte hazır bekler. Bu yüzden aynı sayıda adım atan iki algoritmadan diziyle çalışanı pratikte çoğu zaman daha hızlıdır.

Dezavantajların çoğu da aynı kaynaktan, sabit boyut ve ardışıklıktan gelir. Dizinin ortasına bir öğe eklemek için yer açmak gerekir, çünkü öğeler arasında boşluk yoktur. Dizi dolunca sonuna bir hücre eklenemez, çünkü dizinin hemen arkasındaki bellek başka bir veriye ait olabilir. Öğe sayısı önceden bilinmiyorsa geniş bir dizi ayırmak gerekir ve kullanılmayan hücreler boşa yer kaplar.

Tablonun son satırındaki kovaryans kavramı biraz daha açıklama ister.

3.1.5Dizi kovaryansı ve ArrayStoreException

Java'da sınıflar arasında bir alt tür ilişkisi vardır. Örneğin String, Object'in alt türüdür: her String aynı zamanda bir Object'tir. Bu yüzden Object o = "Ali"; ataması geçerlidir. Soru şudur: String'ler dizisi de Object'ler dizisinin alt türü sayılır mı? Java'nın cevabı “evet”tir.

Kovaryansın kazancı esnekliktir. static void yazdir(Object[] a) biçiminde yazılmış tek bir metot, String[], Integer[] ya da başka herhangi bir referans dizisiyle çağrılabilir. Her tür için ayrı bir metot yazmak gerekmez. Ama bu esnekliğin bir bedeli vardır. Aşağıdaki kodu inceleyelim:

String[] isimler = {"Ali", "Ayşe"};
Object[] nesneler = isimler; // derlenir
nesneler[0] = 42;   // derlenir, ama
                    // çalışırken istisna!

Birinci satır iki öğeli bir String dizisi oluşturur. İkinci satırda nesneler değişkenine aynı dizinin referansı atanır; kovaryans sayesinde bu atama derlenir. Artık iki değişken heap bellekteki tek bir diziyi gösterir. Üçüncü satırda nesneler[0] = 42 yazılır. Derleyicinin gözünde nesneler bir Object[]'dir ve 42 (bir Integer olarak) bir Object'tir; bu yüzden derleyici itiraz etmez. Oysa nesnenin kendisi gerçekte bir String[]'dir ve içine tamsayı konamaz. Java sanal makinesi (Java Virtual Machine, JVM) bunu çalışma sırasında, atamanın yapıldığı anda fark eder ve ArrayStoreException: java.lang.Integer fırlatır.

Hatanın bir an önce, kod derlenirken yakalanması her zaman daha iyidir. Derleme hatası programcının masasında görülür; çalışma zamanı hatası ise belki aylar sonra, programı kullanan birinin karşısına çıkar. Dizi kovaryansı, bir tür hatasını derleme zamanından çalışma zamanına kaydırır. Tür güvenliğindeki “açık” budur.

Java'nın sonradan eklenen jenerik (generic) yapıları bu açığı kapatacak biçimde tasarlanmıştır. Jenerik listeler kovaryant değildir: List<String>, List<Object>'in alt türü sayılmaz. Bu yüzden List<Object> l = new ArrayList<String>(); satırı derlenmez. Aynı hata, dizideki gibi çalışırken değil, derleme sırasında yakalanır.

3.2Java'da diziler

Dizi kavramı bütün programlama dillerinde aynıdır, ama her dil diziyi kendine göre tanımlar ve bellekte kendine göre yerleştirir. Java'da dizinin bir nesne olması pek çok davranışı belirler: dizinin nerede durduğunu, atamanın ne kopyaladığını, bir metoda dizi verildiğinde neyin aktarıldığını. Bu kesim Java'daki dizileri sözdiziminden başlayarak bellek düzenine kadar anlatır.

3.2.1Dizi tanımlama ve varsayılan değerler

Java'da bir dizi şu kalıpla tanımlanır ve oluşturulur:

VeriTipi[] diziAdi = new VeriTipi[diziBoyutu];

Kalıbın üç parçası vardır:

• VeriTipi: Dizide saklanacak verilerin türüdür; int, double, String gibi. Türün yanındaki [], değişkenin tek bir değeri değil, bir diziyi gösterdiğini belirtir.
• diziAdi: Diziyi gösteren referans değişkenin adıdır; örneğin sayilar.
• diziBoyutu: Öğe sayısıdır. Sabit bir sayı olmak zorunda değildir; 5, n ya da 2 * n gibi, program çalışırken hesaplanan bir ifade de olabilir.

Eşittir işaretinin iki yanı ayrı işler yapar. Sol taraf, diziAdi adında bir referans (reference) değişkeni tanımlar. Referans, bir nesnenin bellekteki yerini tutan değerdir; nesnenin kendisi değildir. Sağ taraftaki new VeriTipi[diziBoyutu] ise bellekte o kadar öğelik yeni bir dizi nesnesi oluşturur. Atama, yeni dizinin referansını değişkene yazar. Bu ayrım ilk bakışta önemsiz görünür, ama 3.2.6'daki kopyalama konusunun temelidir.

int[] sayilar = new int[5];
// → [0, 0, 0, 0, 0]

Bu satır beş öğeli bir int dizisi oluşturur. Öğelere henüz değer atanmamıştır, ama boş da değildirler: new ile oluşturulan dizinin her öğesi, türünün varsayılan değerini alır. int için bu değer 0'dır; dizi [0, 0, 0, 0, 0] durumundadır. Tablo 3.2 türlere göre varsayılan değerleri verir.

Varsayılan değer kuralı, yerel değişkenlerle diziler arasındaki önemli bir farkı gösterir. Bir metodun içinde int x; yazıp x'e değer vermeden okumak derleme hatasıdır. Dizi öğeleri ise hiçbir zaman değersiz kalmaz; JVM diziyi oluştururken bütün hücreleri sıfırlar. Bu sıfırlama da bir iştir: n öğeli bir dizinin oluşturulması O(n) sürer.

char dizisinin varsayılanı olan '\u0000', ekranda görünmeyen ve boşluk karakterinden farklı olan özel bir karakterdir. String dizisinin varsayılanı ise boş metin ("") değil, null'dır. null, “hiçbir nesneyi göstermiyor” anlamına gelen referans değeridir. Bu öğelerden biri üzerinden bir metot çağrılırsa (örneğin isimler[0].length()) NullPointerException fırlatılır.

3.2.2Erişim, ilklendirme ve length

Öğelerin değerleri baştan biliniyorsa diziyi oluşturup hücreleri tek tek doldurmak gerekmez. Değerler süslü parantez içinde, virgülle ayrılarak yazılabilir. Bu listeye ilklendirici (initializer) listesi denir. Aşağıdaki kod ilklendirmeyi, okumayı, yazmayı ve length'i bir arada gösterir:

int[] sayilar = {10, 20, 30, 40, 50};   // 5 ilklendirici → boyut 5
int ilkOge    = sayilar[0];            // 10
int ikinciOge = sayilar[1];            // 20
sayilar[4] = 55;                         // son öğe güncellendi
int diziBoyutu   = sayilar.length;     // 5

sayilar = new int[] {1, 2, 3};          // sonradan atamada new int[] gerekir
int[] hatali = new int[3] {1, 2, 3};   // derleme hatası: boyut + liste

Kodu satır satır inceleyelim:

• 1. satır: İlklendirici listesinde beş değer vardır. Listede boyut yazılmaz; öğe sayısı boyutu belirler. Java beş öğeli bir int dizisi oluşturur, değerleri sırayla hücrelere yazar ve referansı sayilar'a atar.
• 2. ve 3. satır: Okuma. sayilar[0] ilk öğedir (10), sayilar[1] ikinci öğedir (20).
• 4. satır: Yazma. Okumayla aynı sözdizimi kullanılır; tek fark, ifadenin atamanın solunda durmasıdır. Son hücrenin (indis 4) değeri 50'den 55'e değişir.
• 5. satır: sayilar.length dizinin öğe sayısını, yani 5'i verir. length bir metot değil, dizinin bir alanıdır; bu yüzden ardından parantez gelmez.
• 7. satır: Değişkene sonradan yeni bir dizi atanıyor. İlklendirici listesi yalnız tanımlama satırında tek başına yazılabilir. Başka bir yerde kullanılacaksa önüne new int[] eklenir.
• 8. satır: Derleme hatası. Hem boyut (3) hem liste verilemez, çünkü boyutu zaten liste belirler. Doğru yazım new int[] {1, 2, 3}'tür.

3.2.3Kod izleme: dizide okuma ve yazma

Bir önceki kodun bellekte ne yaptığını adım adım izleyelim. İzlenen satırlar şunlardır:

int[] sayilar = {10, 20, 30, 40, 50};
int ilkOge    = sayilar[0];
int ikinciOge = sayilar[1];
sayilar[4] = 55;
int diziBoyutu   = sayilar.length;
sayilar = new int[] {1, 2, 3};

İlk satırda iki ayrı şey oluşur. Heap bellekte beş öğeli bir int[] nesnesi oluşur. sayilar değişkeni ise bu nesneyi değil, yalnız onun referansını tutar (Şekil 3.4, solda). Değişkenden diziye uzanan ok bu referansı gösterir.

2. satırdaki okuma, 3.1.2'deki adres hesabıyla yapılır: başlangıç + 0 × 4. Okuma tek adımda biter ve dizinin boyutu ne olursa olsun süresi değişmez. 3. satır aynı işi 1 indisi için yapar. 4. satırda aynı sözdizimi atamanın solunda yer alır ve bu kez okuma değil yazma yapılır: son hücrenin değeri 55 olur. 5. satır dizinin uzunluğunu okur. Bu değer dizi oluşturulurken sabitlenmiştir ve dizinin ömrü boyunca değişmez.

Son satır en öğretici olanıdır. new int[] {1, 2, 3} heap bellekte üç öğeli yeni bir dizi oluşturur ve sayilar artık onu gösterir. Eski dizi değişmemiştir; hâlâ [10, 20, 30, 40, 55] değerlerini taşır. Ama artık onu gösteren hiçbir referans kalmamıştır. Program o diziye bir daha hiçbir yoldan ulaşamaz. Java'nın çöp toplayıcısı (garbage collector, GC) böyle erişilemeyen nesneleri bulup belleklerini geri alır.

diziBoyutu'nun hâlâ 5 olması da dikkat çekicidir. 5. satırda diziBoyutu'na sayilar.length'in o anki değeri kopyalanmıştı. diziBoyutu diziyle bağlantılı bir değişken değildir; dizi değişince kendiliğinden güncellenmez.

3.2.4Örnek kod: tanımla, doldur, yazdır

Aşağıdaki tam program bir dizi oluşturur, bir döngüyle doldurur ve iki ayrı biçimde yazdırır:

public class DiziOrnegi {
    public static void main(String[] args) {
        int[] sayilar = new int[5];            // 5 öğeli dizi
        for (int i = 0; i < sayilar.length; i++)
            sayilar[i] = (i + 1) * 10;              // 10, 20, 30, 40, 50

        System.out.println("Dizinin birinci öğesi: " + sayilar[0]);
        System.out.println("Dizinin üçüncü öğesi: " + sayilar[2]);

        System.out.print("Dizi Öğeleri: ");
        for (int x : sayilar)                       // for-each: indis gerekmiyorsa
            System.out.print(x + " ");
    }
}

Programın çıktısı:

Dizinin birinci öğesi: 10
Dizinin üçüncü öğesi: 30
Dizi Öğeleri: 10 20 30 40 50

Programın yapısı, dizilerle çalışan çoğu programın iskeletidir:

• Oluşturma. new int[5] beş öğeli, sıfırlarla dolu bir dizi oluşturur.
• Doldurma. for döngüsü i'yi 0'dan başlatır ve i < sayilar.length olduğu sürece artırır. Her turda sayilar[i]'ye (i + 1) * 10 yazılır; sonuçta dizi 10, 20, 30, 40, 50 olur.
• Tek öğe yazdırma. sayilar[0] ve sayilar[2] okunur. Üçüncü öğenin indisi 2'dir.
• Bütün öğeleri yazdırma. İkinci döngü bir for-each döngüsüdür: for (int x : sayilar), “sayilar'daki her x için” diye okunur. Döngü değişkeni x, sırayla her öğenin değerini alır.

Beş ayrı sayilar[k] = … ataması yazmak yerine döngü kullanmanın asıl kazancı, kodun dizinin boyutuna bağlı olmamasıdır. Dizi 5 yerine 500 öğeli olsa da döngü değişmeden çalışır. Bunun koşulu, döngü sınırının sabit bir sayı değil sayilar.length olmasıdır. Sınırı i < 5 yazmak bugün çalışır, ama boyut değiştiğinde ya diziyi yarım doldurur ya da sınır dışına taşar.

Programda iki ayrı yazdırma metodu kullanılır. System.out.println yazdıktan sonra satır sonu ekler; sonraki çıktı yeni satıra geçer. System.out.print ise satır sonu eklemez; ardından gelen çıktı aynı satırda devam eder. Bu yüzden son döngüdeki öğeler tek satırda, aralarında birer boşlukla yazılır.

for-each döngüsü, indise ihtiyaç olmadığında daha okunaklı bir seçenektir. Ama iki sınırı vardır. Birincisi, öğenin indisi bilinmez; “hangi indiste bulundu” sorusunu for-each ile cevaplamak için ayrı bir sayaç gerekir. İkincisi, x öğenin kendisi değil, değerinin bir kopyasıdır. Döngü içinde x = 0 yazmak dizideki değeri değiştirmez. Diziye yazmak gereken her durumda indisli for döngüsü kullanılır.

3.2.5Kod izleme: doldur ve yazdır

Programın gövdesini adım adım izleyelim. Tablo 3.4 doldurma döngüsünü, ardından gelen yazdırmaları gösterir.

Döngünün son denetimi kolayca gözden kaçar. i 5 olduğunda 5 < 5 yanlıştır ve gövde çalışmaz; sayilar[5]'e hiç dokunulmaz. Koşulda < yerine <= yazılsaydı, son turda 5 indisli olmayan hücreye yazılmaya çalışılır ve program bir istisnayla dururdu.

Gövde 5 kez çalışmıştır ve her turda bir çarpma ile bir atama yapılmıştır. Öğe sayısı n olsaydı gövde n kez çalışırdı. Dizinin bütün öğelerini bir kez gezen her döngünün süresi n ile doğru orantılı büyür. Böyle bir döngünün maliyeti O(n)'dir (3.5).

3.2.6Dizi kopyalama: referans mı, kopya mı?

Java'da dizi bir nesnedir. Bütün nesneler gibi heap bellekte oluşur ve bir değişkene atandığında değişkene nesnenin kendisi değil, referansı yazılır. Bu kuralın en çok şaşırtan sonucu, atama işlecinin (=) diziyi kopyalamamasıdır. Aşağıdaki kod bu farkı gösterir:

int[] dizi = {1, 2, 3, 4, 5};
int[] referans = dizi;   // aynı nesne
int[] kopya =
    Arrays.copyOf(dizi, dizi.length);
referans[0] = 99;

Kodu dört adımda izleyelim. Heap bellekteki dizileri ayırt etmek için onlara #1 ve #2 diye numara verelim.

Gerçek bir kopya elde etmenin üç yaygın yolu vardır. Üçü de yeni bir dizi oluşturur ve öğeleri tek tek kopyalar; üçünün maliyeti de O(n)'dir:

• Arrays.copyOf(dizi, yeniBoyut): İstenen boyutta yeni bir dizi döndürür. Yeni boyut eskisinden büyükse fazla hücreler varsayılan değeri alır; küçükse dizi kırpılır. Bu yüzden dolan bir diziyi büyütmek için de kullanılır.
• dizi.clone(): Aynı boyutta bir kopya döndürür.
• System.arraycopy(kaynak, kaynakBas, hedef, hedefBas, adet): Var olan bir hedef diziye, istenen konumdan başlayarak istenen sayıda öğe kopyalar.

Aynı kural metot çağrılarında da geçerlidir. Bir metoda dizi verildiğinde metoda dizinin referansı aktarılır. Metot dizinin içindeki bir değeri değiştirirse, değişiklik çağıran yerde de görünür; çünkü ikisi aynı nesneye bakar. 3.3.4'teki ortanca metodunun diziyi sıralamadan önce kopyalaması bu yüzdendir.

3.2.7Hazır dizi işlemleri: java.util.Arrays

Java dizilerinin kendi üzerinde çağrılabilen sıralama, arama ya da yazdırma metotları yoktur. Bu işler java.util paketindeki Arrays sınıfının statik metotlarıyla yapılır. Statik metot, bir nesne üzerinden değil sınıfın adıyla çağrılır: a.sort() değil, Arrays.sort(a). Sınıfı kullanmak için dosyanın başına import java.util.Arrays; yazılır. Tablo 3.5 en sık kullanılan metotları ve maliyetlerini verir.

Tablodaki maliyetlerin çoğu O(n)'dir, çünkü bu metotlar her öğeye bir kez dokunur. sort daha pahalıdır; iyi bir sıralama algoritmasının maliyeti O(n log n)'dir (3.5.7). binarySearch ise daha ucuzdur, ama yalnız sıralı dizide doğru çalışır. İkili arama (binary search) aranan değeri dizinin ortasındaki öğeyle karşılaştırır. Değer daha küçükse sol yarıda, büyükse sağ yarıda aramayı sürdürür. Her adımda aralık yarıya indiği için n öğeli dizide yaklaşık log₂ n adım yeter: bir milyon öğede 20 adım.

Bu sınıfın neden gerektiğini, dizilerle en sık yapılan iki hata gösterir:

int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
a == b              // false: ayrı nesne
Arrays.equals(a, b) // true: aynı içerik
println(a)          // [I@1b6d3586

a ve b aynı içerikli iki ayrı dizidir. == işleci referansları karşılaştırır, yani “iki değişken aynı nesneyi mi gösteriyor?” sorusunu sorar. İki ayrı nesne olduğu için sonuç false'tur. İçeriğin eşitliğini sınamak için Arrays.equals(a, b) kullanılır; o, önce uzunlukları, sonra öğeleri tek tek karşılaştırır ve true döndürür.

İkinci hata, diziyi doğrudan yazdırmaktır. System.out.println(a) dizinin öğelerini değil, [I@1b6d3586 gibi bir metin basar. Bu metindeki [I “int dizisi” anlamına gelir; @ işaretinden sonraki kısım ise nesneye özgü bir sayıdır ve her çalıştırmada değişebilir. Öğeleri görmek için System.out.println(Arrays.toString(a)) yazılır; çıktı [1, 2, 3] olur.

3.2.8Değişken sayıda argüman

Bazı metotların kaç argüman alacağı önceden belli değildir. Sayıların ortalamasını hesaplayan bir metot iki, üç ya da on sayıyla çağrılabilir. Java bunun için değişken sayıda argüman (varargs) yazımını sağlar: parametre türünden sonra üç nokta yazılır.

static double ortalama(double... dizi) {
    if (dizi.length == 0)
        return Double.NaN;  // tanımsız
    var toplam = 0.0;
    for (var oge : dizi)
        toplam += oge;
    return toplam / dizi.length;
}

double... dizi parametresi, metodun istediği sayıda double argümanla çağrılabileceğini söyler. Derleyici, çağrıda verilen argümanları bir double[] dizisine koyar ve metoda o diziyi verir. Metodun içinde dizi sıradan bir dizidir: length'i vardır, indisle ya da for-each ile gezilebilir. Kuralları şunlardır:

• Değişken sayıda argüman alan parametre, metodun son parametresi olmalıdır.
• Bir metotta bu türden yalnız bir parametre bulunabilir.
• Hazır bir dizi de doğrudan geçirilebilir: ortalama(new double[] {1, 2}).

Metodun gövdesinde iki küçük ayrıntı daha vardır. Birincisi, boş çağrı (ortalama()) için ayrı bir denetim yapılır ve Double.NaN döndürülür. NaN (Not a Number: sayı değil), tanımsız bir sonucu gösteren özel bir double değeridir; hiç sayı yokken ortalama tanımsızdır. İkincisi, var anahtar sözcüğüyle tanımlanan yerel değişkenlerin türü, sağdaki değerden çıkarılır: 0.0 bir double olduğu için toplam da double'dır. Tablo 3.6 farklı çağrıların sonucunu gösterir.

Bu yazım aslında yabancı değildir. Her Java programının başındaki main(String[] args) metodu, komut satırından verilen argümanları bir dizi olarak alır. String.format ve System.out.printf gibi kütüphane metotları da değişken sayıda argüman alır.

3.2.9Kod izleme: ortalama(4, 8, 15)

ortalama(4, 8, 15) çağrısını izleyelim. Argümanlar tamsayıdır, ama parametre double olduğu için her biri double'a genişletilir: dizi [4.0, 8.0, 15.0] olur.

Döngü her öğeyi bir kez toplar; n argümanlı bir çağrıda n toplama yapılır ve süre O(n)'dir. Metot yalnız toplam ve oge değişkenlerini kullanır; argüman dizisi dışında ek bellek gerekmez. ortalama() çağrılsaydı length 0 olur, if koşulu doğru çıkar ve 3. satırdaki return Double.NaN çalışırdı. Bu denetim olmasaydı sonuç yine NaN çıkardı, çünkü 0.0 / 0 kayan noktalı bir bölmedir ve NaN verir. Açık denetim, bu durumun bilerek ele alındığını gösterir.

3.2.10Bellekte diziler: stack ve heap

Önceki örneklerde “stack bellekteki değişken” ve “heap bellekteki dizi” ifadeleri sık geçti. Java programı çalışırken belleği iki ana bölgeye ayırır. Bu bölgeler farklı işler görür ve farklı biçimde yönetilir.

• Stack bellek (yığın belleği): Metot çağrıları ve yerel değişkenler burada durur. Her metot çağrısı için stack bellekte bir çerçeve (stack frame) açılır. Çerçeve, metodun parametrelerini ve yerel değişkenlerini tutar. Metot bitince çerçevesi kendiliğinden silinir.
• Heap bellek (heap memory): new ile oluşturulan bütün nesneler burada durur. Java'da her dizi heap bellektedir; stack bellekte yalnız dizinin referansı bulunur.

Heap belleği 3.2.3'te adı geçen çöp toplayıcı yönetir. Çöp toplayıcı ara ara çalışır, hiçbir referansın göstermediği nesneleri bulur ve belleklerini serbest bırakır. Programcının bir nesneyi elle silmesi gerekmez, zaten Java'da buna izin veren bir komut da yoktur.

Bu iki bölgenin ömürleri farklıdır ve bu fark önemli bir sonuç doğurur. Bir metodun içinde oluşturulan dizi, metot bitince yok olmaz. Metodun çerçevesi ve dizinin referansını tutan yerel değişken silinir, ama dizi heap bellekte durmaya devam eder. Metot dizinin referansını döndürmüşse, çağıran yer o referansla diziyi kullanmayı sürdürür. 3.3.1'deki diziOku metodu tam olarak böyle çalışır.

Dizinin ömrü, ona en az bir referans olduğu sürece devam eder. Son referans da kaybolduğunda (değişkene başka bir dizi atandığında, değişken null yapıldığında ya da değişkenin metodu bittiğinde) dizi erişilemez olur ve çöp toplayıcı onu toplayabilir.

3.2.11“Statik” ve “dinamik” diziler: C ve Java

Dizilerle ilgili kaynaklarda statik dizi (static array) ve dinamik dizi (dynamic array) terimleri sık geçer. Bu terimler en çok C ve C++ için anlamlıdır, çünkü bu dillerde dizi iki ayrı yerde oluşturulabilir. Tablo 3.9 iki dili karşılaştırır.

C'de int a[10]; yazılınca dizi stack bellekte, fonksiyonun çerçevesinin içinde oluşur. Boyutu derleme sırasında bilinir ve fonksiyon bitince dizi de çerçeveyle birlikte yok olur. Bu tür dizilere “statik” denir. Boyut ancak çalışma sırasında belli oluyorsa dizi heap bellekte malloc (C) ya da new (C++) ile ayrılır ve buna “dinamik” denir. C'de heap bellekteki diziyi işi bitince free ile serbest bırakmak programcının görevidir. Unutulursa bellek boşa harcanır; aynı bellek iki kez serbest bırakılırsa programın davranışı tanımsız olur ve çoğu zaman program çöker.

Java'da bu ayrım yoktur. Bütün diziler heap bellekte oluşur. Boyut çalışma sırasında hesaplanabilir, ama dizi oluştuktan sonra değişmez. Aşağıdaki kod Java'daki tipik durumu gösterir:

int[] dinamikDizi = new int[n];   // heap'te n öğelik yer ayrılır
dinamikDizi = null;               // başka referans yoksa GC toplayabilir

İlk satır, n'nin o anki değeri kadar öğelik bir diziyi heap bellekte oluşturur. İkinci satır diziyi silmez; yalnız dinamikDizi değişkeninin referansını koparır. Diziyi gösteren başka bir referans yoksa çöp toplayıcı onu uygun bir anda toplar. System.gc() çağrısı da toplamayı garanti etmez; yalnız JVM'e bir istekte bulunur.

“Dinamik dizi” adının ikinci bir anlamı daha vardır. Dolunca kendiliğinden büyüyen diziler de bu adla anılır. Java'daki ArrayList böyle bir yapıdır: içinde sıradan bir dizi tutar ve dizi dolunca daha büyük bir dizi oluşturup öğeleri ona kopyalar. Bu anlamdaki dinamik dizi, sabit boyutlu dizinin üzerine kurulmuş bir yapıdır; dizinin kendisinin boyutu yine değişmez.

3.2.12İndis sınır dışı hatası

n öğeli bir dizide geçerli indisler 0'dan n − 1'e kadardır. Bu aralığın dışındaki bir indise erişilirse, yani indis negatifse ya da length'e eşit veya ondan büyükse, Java ArrayIndexOutOfBoundsException fırlatır. Bu istisna, daha genel IndexOutOfBoundsException'ın alt sınıfıdır.

int[] dizi = new int[5];
dizi[5] = 1;  // Index 5 out of
              // bounds for length 5
dizi[-1] = 1; // aynı hata

Beş öğeli dizide 5 indisli hücre yoktur. dizi[5] = 1 satırı derlenir, çünkü derleyici indisin değerini genellikle bilemez. Ama çalışma sırasında JVM her erişimden önce indisi denetler ve istisna fırlatır. İstisnanın iletisi sorunu açıkça söyler: Index 5 out of bounds for length 5 (5 indisi, 5 uzunluğun sınırları dışında). dizi[-1] de aynı hatayı verir. İstisna yakalanmazsa program o noktada sonlanır.

Bu denetim, Java'yı C'den ayıran önemli bir güvenlik özelliğidir. C dizi erişimlerini denetlemez. a[5] yazıldığında adres formülü yine hesaplanır ve dizinin hemen arkasındaki bellek okunur ya da üzerine yazılır. Orada başka bir değişken varsa onun değeri sessizce bozulur. Böyle bir hata program başka bir yerde tuhaf davranana kadar fark edilmeyebilir. Bu tür taşmalar tarih boyunca pek çok güvenlik açığının da nedeni olmuştur. Java'da ise hata, yapıldığı satırda ve açık bir iletiyle ortaya çıkar. Denetimin bedeli her erişimde yapılan küçük bir karşılaştırmadır.

Kullanıcıdan gelen ya da hesaplanan bir indisle erişim yapılacaksa indis önceden denetlenebilir:

if (indis >= 0
        && indis < dizi.length) {
    int deger = dizi[indis];
} else {
    System.out.println("Geçersiz");
}

Koşul iki parçalıdır: indis 0'dan küçük olmamalı ve length'ten küçük olmalıdır. İkisi && ile bağlanır; ikisi de doğruysa erişim güvenlidir.

3.3Dizi algoritmaları

Bu kesimdeki algoritmalar küçük ama öğreticidir. Her biri diziyi farklı bir biçimde kullanır: kimi baştan sona bir kez gezer, kimi önce sıralar, kimi iki uçtan ortaya doğru ilerler. Algoritmaları anlamanın en güvenilir yolu, küçük bir girdi üzerinde her adımı kâğıda yazarak izlemektir. Aşağıdaki izleme tabloları bu yöntemin örnekleridir.

3.3.1Diziyi kullanıcıdan okuma

Ortalama, ortanca ve mod programlarının üçü de aynı biçimde başlar: kullanıcıdan önce kaç sayı gireceğini, ardından sayıları tek tek ister. Bu ortak işi her programda yeniden yazmak yerine bir yardımcı metotta toplamak daha doğrudur:

import java.util.Scanner;

static double[] diziOku(Scanner scanner) {
    System.out.print("Dizi boyutunu girin: ");
    int boyut = scanner.nextInt();
    double[] dizi = new double[boyut];  // boyut çalışma zamanında
    for (int i = 0; i < boyut; i++) {
        System.out.print((i + 1) + ". öğeyi girin: "); // 1'den say
        dizi[i] = scanner.nextDouble();
    }
    return dizi;
}

Metot, klavyeden okuma yapan bir Scanner nesnesini parametre olarak alır. Scanner'ı metodun içinde değil dışarıda oluşturup vermenin nedeni, programın tek bir Scanner kullanmasıdır. Aynı girdi kaynağına bağlı birden çok Scanner açmak, okunan verilerin karışmasına yol açabilir.

Metodun adımları şunlardır:

1. Kullanıcıya boyut sorulur. print satır sonu eklemediği için imleç sorunun hemen yanında bekler.
2. nextInt() kullanıcının yazdığı tamsayıyı okur ve boyut'a atar.
3. new double[boyut] diziyi oluşturur. Boyut ancak bu satırda, program çalışırken belli olmuştur; Java'da bu bir sorun değildir. Hücrelerin hepsi 0.0 ile başlar.
4. Döngü her öğeyi sırayla okur. Kullanıcıya gösterilen sıra numarası i + 1'dir: dizi 0'dan sayar, ama insanlar 1'den sayar. “0. öğeyi girin” demek kullanıcıyı şaşırtır.
5. Dizinin referansı döndürülür.

Son adım, 3.2.10'daki bellek düzeninin pratikteki sonucudur. dizi değişkeni metodun yerel değişkenidir ve metot bitince silinir. Dizi ise heap bellektedir ve silinmez. Döndürülen referans çağıran yerdeki bir değişkene atanır ve dizi orada kullanılmaya devam eder.

Bu kesimde işlenecek üç istatistik Tablo 3.10'da özetlenmiştir. Hepsi aynı diziyi kullanır, ama maliyetleri farklıdır.

3.3.2Kod izleme: diziOku(sc)

Kullanıcının boyut olarak 4, ardından sırayla 4, 8, 15 ve 16 girdiğini varsayalım. Tablo 3.11 metodun her adımını gösterir.

İzlemede iki ayrıntıya dikkat edelim. Boyut okunmadan önce dizi yoktur; dizi ancak kullanıcı 4 yazdıktan sonra oluşur (Şekil 3.11). Ayrıca nextDouble() kullanıcının yazdığı 4'ü 4.0 olarak okur, çünkü dizi double türündedir.

Metot n öğe için n kez okuma yapar; süresi O(n)'dir. Gerçekte bu sürenin çoğu kullanıcının yazmasını beklemekle geçer, ama algoritmanın yaptığı iş öğe sayısıyla doğru orantılıdır.

3.3.3Ortalama hesaplama

Ortalama, bütün değerlerin toplamının değer sayısına bölümüdür. Aşağıdaki main metodu diziyi diziOku ile okur, ortalamayı hesaplar ve sonucu yazdırır:

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    double[] dizi = diziOku(sc);
    double toplam = 0;
    for (int i = 0; i < dizi.length; i++)
        toplam += dizi[i];
    double ortalama = toplam / dizi.length;
    System.out.println("Dizi: "
        + Arrays.toString(dizi));
    System.out.println("Ortalama: "
        + ortalama);
    sc.close();
}

Hesabın merkezinde bir toplayıcı değişken vardır. toplam 0 ile başlar ve döngünün her turunda bir öğe eklenir. Döngü bitince toplam bütün öğelerin toplamını tutar. Bu kalıp, dizi üzerinde biriktirme yapan bütün algoritmalarda görülür: en büyüğü bulmak, belirli bir koşula uyanları saymak, çarpım almak gibi.

toplam'ın türü double'dır ve başlangıç değeri olarak 0 yazılmıştır. Java bu tamsayıyı kendiliğinden 0.0'a genişletir. Bölme de double ile yapıldığı için sonuç ondalıklı çıkar.

Sonuç yazdırılırken dizi Arrays.toString(dizi) ile metne çevrilir. println(dizi) yazılsaydı 3.2.7'de görüldüğü gibi [D@… biçiminde bir tür ve sayı basılırdı. Programın sonundaki sc.close() çağrısı Scanner'ı kapatır.

Her öğe bir kez toplanır; n öğe için n toplama yapılır. Süre O(n)'dir. Algoritma dizinin dışında yalnız toplam, i ve ortalama değişkenlerini kullanır. Bu değişkenlerin sayısı n büyüse de değişmez; bu yüzden ek bellek O(1)'dir.

Sınır durumu da düşünülmelidir. Kullanıcı boyut olarak 0 girerse new double[0] geçerli ama boş bir dizi oluşturur. Döngü hiç dönmez, toplam 0.0 kalır ve 0.0 / 0 hesaplanır. Bu bir kayan noktalı bölmedir ve hata vermez; sonuç NaN olur. Program “Ortalama: NaN” yazar. Bu teknik olarak doğrudur, ama kullanıcıya yardımcı olmaz. Boş dizi için “hiç sayı girilmedi” gibi bir uyarı vermek daha iyidir.

3.3.4Ortanca

Ortalama, uç değerlere karşı çok duyarlıdır. Beş kişinin aylık geliri 3, 5, 7, 9 ve 1000 birim olsun. Ortalama (3 + 5 + 7 + 9 + 1000) / 5 = 204,8'dir; bu sayı beş kişiden hiçbirinin durumunu yansıtmaz. Tek bir uç değer ortalamayı yukarı çekmiştir. Böyle durumlarda “ortadaki kişinin” geliri daha anlamlı bir ölçüdür.

Yukarıdaki gelir örneğinde sıralı dizi 3, 5, 7, 9, 1000'dir ve ortanca 7'dir. 1000 yerine 10 ya da bir milyon yazılsa da ortanca değişmez. Ortanca, uç değerlerden etkilenmez.

static double ortanca(double[] dizi) {
    double[] s = dizi.clone(); // kopya
    Arrays.sort(s);             // O(n log n)
    int boyut = s.length;
    double ortanca;
    if (boyut % 2 == 0) {       // çift
        int o1 = boyut/2 - 1, o2 = boyut/2;
        ortanca = (s[o1] + s[o2]) / 2;
    } else {                    // tek
        ortanca = s[boyut / 2];
    }
    return ortanca;
}

Metot dört adımda çalışır:

1. Kopyalama. dizi.clone() ile dizinin bir kopyası alınır. Bu adım gereklidir, çünkü sonraki adım diziyi sıralar. Sıralama doğrudan dizi üzerinde yapılsaydı, çağıranın elindeki dizinin sırası da bozulurdu (3.2.6). Ortancayı soran birinin, verisinin yeniden düzenlenmesini beklemesi için bir neden yoktur.
2. Sıralama. Arrays.sort(s) kopyayı artan sıraya dizer. Bu adımın maliyeti O(n log n)'dir.
3. Tek mi, çift mi? boyut % 2, boyutun 2'ye bölümünden kalandır. Kalan 0 ise boyut çifttir.
4. Ortadaki değer. Çift boyutta o1 = boyut/2 − 1 ve o2 = boyut/2 indislerindeki iki değerin ortalaması alınır. Tek boyutta s[boyut / 2] döndürülür; tamsayı bölmesi tam ortadaki indisi verir.

3.3.5Kod izleme: ortanca()

Metodu biri çift, biri tek boyutlu iki diziyle çağıralım: önce {6, 2, 8, 4}, sonra {9, 3, 11, 7, 5}.

Tablonun son satırı, kopyalama adımının işe yaradığını gösterir: iki çağrıdan sonra da çağıranın dizileri ilk sıralarını korur. Sıralanan, yalnız metodun içindeki s kopyasıdır.

Metodun maliyetini sıralama belirler. Kopyalama O(n), sıralama O(n log n), ortadaki değeri okumak O(1)'dir. Toplam maliyet en büyük terimle belirlenir: O(n log n). Kopya için n öğelik ek bellek gerekir; ek bellek O(n)'dir. Ortancayı sıralamadan, ortalama O(n) sürede bulan daha ileri algoritmalar da vardır, ama sıralama yolu en kolay anlaşılanıdır.

3.3.6Mod

Mod bulmanın en düz yolu, her değer için dizide kaç kez geçtiğini saymaktır. Ama her öğe için bütün diziyi yeniden gezmek n × n karşılaştırma demektir. Daha iyi bir yol, diziyi önce sıralamaktır. Sıralı dizide eşit değerler yan yana gelir. Böylece her değerin tekrar sayısı, diziyi tek bir kez soldan sağa gezerek bulunur.

static int mod(int[] dizi) { // boş değil
    int[] s = dizi.clone();
    Arrays.sort(s);  // eşitler yan yana
    int enCok = s[0], enCokSayi = 1;
    int mevcutSayi = 1;
    for (int i = 1; i < s.length; i++) {
        if (s[i] == s[i - 1]) mevcutSayi++;
        else mevcutSayi = 1;   // yeni değer
        if (mevcutSayi > enCokSayi) {
            enCokSayi = mevcutSayi;
            enCok = s[i];
        }
    }
    return enCok;
}

Metodun değişkenleri şunlardır:

• s: dizinin sıralı kopyası. Kopyalamanın nedeni ortanca metodundakiyle aynıdır.
• mevcutSayi: o anda okunan değerin, şimdiye kadar art arda kaç kez görüldüğü.
• enCok ve enCokSayi: şimdiye kadarki rekor; en uzun tekrar dizisinin değeri ve uzunluğu.

Başlangıçta ilk değer (s[0]) bir kez görülmüştür ve rekor odur. Döngü 1 indisinden başlar ve her öğeyi solundakiyle karşılaştırır. Değer solundakiyle aynıysa aynı tekrar dizisi sürüyor demektir ve mevcutSayi bir artar. Farklıysa yeni bir değer başlamıştır ve sayaç 1'e döner. Her turun sonunda sayaç rekorla karşılaştırılır. Sayaç rekoru geçmişse rekor güncellenir.

Karşılaştırmanın > ile yapılması bir seçimdir. İki değer aynı sayıda tekrar ederse sonra gelen değer rekoru geçemez, yalnız eşitler. Bu yüzden rekor değişmez ve önce görülen değer kalır. Dizi artan sırada olduğu için önce görülen değer, eşitler arasında en küçük olandır. Koşul >= olsaydı eşitlikte sonraki, yani en büyük değer seçilirdi.

Metodun başındaki yorum (“boş değil”) bir ön koşuldur. Boş dizide s[0] olmadığı için metot ilk satırlarda ArrayIndexOutOfBoundsException fırlatır. Metodu çağıran, diziyi boş vermemekle yükümlüdür.

3.3.7Kod izleme: mod()

mod({4, 1, 4, 2, 1, 4}) çağrısını izleyelim. Girdide eşit değerler dağınıktır. Sıralanınca kopya s = {1, 1, 2, 4, 4, 4} olur. Başlangıçta enCok = 1, enCokSayi = 1, mevcutSayi = 1'dir.

Metot 4 döndürür: 4 değeri üç kez geçer. i = 4 satırı eşitlik kuralını gösterir. O anda 4 iki kez görülmüştür ve rekor da 2'dir. 2 > 2 yanlış olduğu için rekor 1'de kalır. Dizi o noktada bitseydi 1 ile 4 ikişer kez geçmiş olurdu ve metot önce görülen 1'i döndürürdü. Bu dizide 4 bir kez daha geçtiği için i = 5'te rekor 4'e geçer.

Maliyet iki parçalıdır. Sıralama O(n log n), ardından gelen tarama O(n)'dir; toplam O(n log n)'dir. Kopya için O(n) ek bellek kullanılır.

3.3.8Diziyi yerinde tersine çevirme

Bir diziyi tersine çevirmek, ilk öğeyi sona, son öğeyi başa, ikinci öğeyi sondan ikinciye götürmek demektir. {3, 8, 1, 9, 4, 6} dizisi {6, 4, 9, 1, 8, 3} olur. Bunun en basit yolu, aynı boyutta yeni bir dizi açıp öğeleri sondan başa kopyalamaktır: yeni[i] = dizi[n - 1 - i]. Bu yöntem doğrudur, ama n öğelik ikinci bir dizi ister. Aynı iş ek dizi kullanmadan, dizinin kendi içinde de yapılabilir.

Ek dizi kullanmadan, dizinin kendi üzerinde çalışan algoritmalara yerinde (in-place) algoritma denir. Yerinde tersine çevirmenin fikri basittir. Önce ilk ve son öğenin yeri değiştirilir, sonra ikinci ve sondan ikinci öğeninki. Bu, ortaya varılana kadar sürer. İki öğenin yerini değiştirmeye takas (swap) denir.

static void tersineCevir(int[] dizi) {
    int baslangic = 0;
    int bitis = dizi.length - 1;
    while (baslangic < bitis) {
        // uçtaki iki öğeyi takas et
        int gecici = dizi[baslangic];
        dizi[baslangic] = dizi[bitis];
        dizi[bitis] = gecici;
        baslangic++;   // içe doğru ilerle
        bitis--;
    }
}

Metot iki indis tutar. baslangic soldan, bitis sağdan başlar. Bu indislere, dizinin içinde bir konumu “gösterdikleri” için işaretçi de denir. Döngünün her turunda iki işaretçinin gösterdiği öğeler takas edilir, sonra soldaki bir sağa, sağdaki bir sola ilerler. İşaretçiler ortada karşılaşınca, yani baslangic < bitis yanlış olunca döngü biter.

Takas üç atamayla yapılır ve geçici bir değişken gerektirir. İlk atama soldaki değeri gecici'de saklar. İkinci atama sağdaki değeri sola yazar; bu anda soldaki eski değer dizide artık yoktur ve yalnız gecici'de durur. Üçüncü atama gecici'deki değeri sağa yazar. gecici olmadan, dizi[baslangic] = dizi[bitis]; dizi[bitis] = dizi[baslangic]; yazılsaydı, ilk atamadan sonra iki hücre de aynı değeri taşırdı ve soldaki değer kaybolurdu.

Altı öğeli dizide üç takas yapıldı. Öğe sayısı tek olsaydı ortadaki öğe kendi yerinde kalırdı: {1, 2, 3, 4, 5} dizisinde 1 ile 5, 2 ile 4 takas edilir; 3'e dokunulmaz ve sonuç {5, 4, 3, 2, 1} olur.

Yeni diziye kopyalama yöntemi de O(n) sürer: n kopyalama yapar. İki yöntemin farkı bellektedir. Kopyalama yöntemi O(n), yerinde yöntem O(1) ek bellek ister. Bellek kısıtlıysa ya da dizi çok büyükse yerinde yöntem tercih edilir. Buna karşılık kopyalama yöntemi orijinal diziyi bozmaz; orijinal dizi başka bir yerde de kullanılıyorsa bu bir üstünlüktür.

3.3.9Uygulama: Sezar şifresi

Sezar şifresi, adını Roma devlet adamı Julius Caesar'dan alan çok eski bir şifreleme yöntemidir. Metindeki her harf, alfabede sabit bir k adım ilerideki harfle değiştirilir. k = 3 ise A → D, B → E, C → F olur. Alfabenin sonuna gelindiğinde başa dönülür: X → A, Y → B, Z → C. Yöntem bugün hiçbir güvenlik sağlamaz, çünkü yalnız 25 farklı anahtar vardır ve hepsi kolayca denenebilir. Ama karakter dizileriyle ve kalan işlemiyle çalışmayı göstermek için iyi bir örnektir.

static String sifrele(String mesaj, int k) {
    char[] harf = mesaj.toCharArray();
    for (int i = 0; i < harf.length; i++) {
        int sira = harf[i] - 'A';        // 0..25 (yalnız A–Z)
        harf[i] = (char) ('A' + (sira + k) % 26);
    }
    return new String(harf);
}

Metodun her satırı bir Java ayrıntısına dayanır:

• toCharArray(). Java'da String nesneleri değiştirilemez; bir metnin 2. harfini başka bir harfle değiştirmenin yolu yoktur. Bu yüzden metnin harfleri önce yeni bir char[] dizisine kopyalanır. Dizinin öğeleri ise yerinde değiştirilebilir.
• harf[i] - 'A'. Java'da char değerleri aslında tamsayıdır; her karakterin bir kodu vardır ve büyük harflerin kodları alfabe sırasıyla ardışıktır. Bir harften 'A''yı çıkarmak, harfin alfabedeki sırasını verir: 'A' için 0, 'E' için 4, 'Z' için 25.
• (sira + k) % 26. Sıra k kadar ilerletilir. Sonuç 25'i aşarsa % 26 (26'ya bölümden kalan) onu başa sarar: (25 + 3) % 26 = 2.
• (char) ('A' + …). Yeni sıra yeniden harfe çevrilir: 'A''nın koduna sıra eklenir ve sonuç char'a dönüştürülür.
• new String(harf). Değiştirilmiş dizi yeniden metne çevrilip döndürülür.

sifrele("ZEKA", 3) çağrısını izleyelim:

Metot "CHND" döndürür. İlk satır, başa sarmanın nasıl çalıştığını gösterir: Z'nin sırası 25'tir, 3 ilerletilince 28 olur ve 28 % 26 = 2 sonucu C harfine karşılık gelir.

Şifreyi çözmek için ayrı bir metot gerekmez. Her harf 3 ileri kaydırıldıysa, 23 ileri daha kaydırılınca toplam 26 adım atılmış olur ve alfabe bir tam tur döner. Bu yüzden çözme, aynı metodu k = 26 − 3 = 23 ile çağırmaktır: sifrele("CHND", 23) yeniden "ZEKA" verir.

Her harf bir kez işlenir; n harfli metin için süre O(n)'dir. toCharArray ve new String de birer O(n) kopyalama yapar. Bu sabit sayıda geçiş, toplam maliyeti değiştirmez.

3.4Çok boyutlu diziler

Bazı veriler doğal olarak tek bir sıra hâlinde değil, bir tablo hâlinde durur: bir sınıfın haftalık ders programı, satranç tahtası, bir resmin pikselleri, bir şehrin semtler arası uzaklık çizelgesi. Bu verileri tek boyutlu bir diziye sıkıştırmak mümkündür, ama her erişimde satır ve sütun numarasından tek bir indis hesaplamak gerekir. İki boyutlu dizi bu hesabı dilin kendisine bırakır.

3.4.1İki boyutlu diziler

İki boyutlu dizi, öğeleri satırlar ve sütunlar hâlinde düzenlenmiş, tablo benzeri bir yapıdır. Matematikteki matrisin programlamadaki karşılığıdır. Bir öğeye iki indisle erişilir: matris[satır][sütun]. İlk indis satırı, ikinci indis sütunu seçer; ikisi de 0'dan başlar.

int[][] matris = new int[3][3];
matris[1][2] = 7;   // 2. satır, 3. sütun

İlk satır 3 satır ve 3 sütunlu, bütün hücreleri 0 olan bir matris oluşturur. İkinci satır, 1 indisli satırın 2 indisli sütununa 7 yazar. İndisler 0'dan başladığı için bu hücre, insanların saymasıyla 2. satırın 3. sütunudur.

İki boyutlu diziler, satranç tahtası (8 × 8), resim (piksel ızgarası) ve hesap tablosu gibi verilerde kullanışlıdır. Bir resimde resim[y][x], yukarıdan y. satırdaki, soldan x. pikselin rengidir.

3.4.2Java'da matris: dizilerin dizisi

Bazı dillerde iki boyutlu dizi, bellekte satır satır art arda dizilmiş tek bir blok hâlindedir. Java'da durum farklıdır. Java'da gerçek bir iki boyutlu dizi türü yoktur; matris, dizilerin dizisidir. int[][], öğeleri int[] olan bir dizidir.

int[][] matris = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
matris.length      // 3 (satır sayısı)
matris[0].length   // 3 (sütun sayısı)

Bu kod bellekte dört dizi oluşturur. Birincisi, üç öğeli bir dış dizidir; öğeleri sayı değil, referanstır. Diğer üçü, her biri bir satırı tutan üç öğeli int dizileridir. Dış dizinin her hücresi bir satır dizisini gösterir. matris değişkeni de dış diziyi gösterir.

Bu yapının birkaç doğrudan sonucu vardır:

• matris.length dış dizinin uzunluğudur, yani satır sayısıdır (3).
• matris[0] bir satır dizisidir; matris[0].length o satırın uzunluğu, yani sütun sayısıdır (3).
• matris[1][2] iki adımda okunur: önce matris[1] ile 1. satır dizisine ulaşılır, sonra o dizinin 2 indisli öğesi okunur. Sonuç 6'dır.
• İlklendiricide boyut yazılmaz. Satır sayısı dış listedeki iç liste sayısından, sütun sayısı iç listelerdeki öğe sayısından çıkar.

En önemli sonuç şudur: her satır ayrı bir dizi olduğu için satırların uzunlukları farklı olabilir. Böyle bir diziye düzensiz dizi (jagged array) denir.

3.4.3Düzensiz dizi: Pascal üçgeni

Düzensiz dizinin doğal bir örneği Pascal üçgenidir. Üçgenin her satırı bir öncekinden bir öğe uzundur. Her satırın iki ucu 1'dir. Aradaki her sayı, hemen üstündeki iki sayının toplamıdır:

p[i][j] = p[i−1][j−1] + p[i−1][j]

İlk dört satır 1; 1 1; 1 2 1; 1 3 3 1'dir. Kare bir matris kullanılsaydı her satır en uzun satır kadar yer kaplardı ve hücrelerin yarısına yakını boş kalırdı. Düzensiz dizi her satıra yalnız gerektiği kadar yer ayırır. Aşağıdaki kod ilk 4 satırı oluşturur:

int n = 4;
int[][] p = new int[n][];          // satırlar yok
for (int i = 0; i < n; i++) {
    p[i] = new int[i + 1];         // i + 1 uzunluk
    p[i][0] = p[i][i] = 1;
    for (int j = 1; j < i; j++)
        p[i][j] = p[i-1][j-1] + p[i-1][j];
}

Kodun çalışması şöyledir. new int[n][] yalnız 4 referanslık dış diziyi oluşturur; ikinci köşeli parantezin boş bırakılması, satır dizilerinin henüz oluşturulmadığını söyler. Dış dizinin dört hücresi de null'dır. Döngünün her turunda önce i. satır i + 1 uzunlukta oluşturulur. Sonra satırın iki ucuna 1 yazılır. p[i][0] = p[i][i] = 1 bir zincirleme atamadır ve sağdan sola çalışır: önce p[i][i] = 1 yapılır, bu atamanın değeri (1) de p[i][0]'a yazılır. Son olarak iç döngü, uçlar dışındaki hücreleri üst satırdan hesaplar.

0. satırda p[0][0] hem baş hem son hücredir; zincirleme atama aynı hücreye iki kez 1 yazar. 0. ve 1. satırlarda iç döngü hiç dönmez, çünkü uçlar dışında hücre yoktur. 3. satırın iç hücreleri 2. satırdan hesaplanır: p[3][1] = p[2][0] + p[2][1] = 1 + 2 = 3 ve p[3][2] = p[2][1] + p[2][2] = 2 + 1 = 3.

Üçgen toplam 1 + 2 + 3 + 4 = 10 hücre kullanır. Aynı veriyi 4 × 4'lük bir matriste tutmak 16 hücre gerektirirdi. n satırda fark daha da büyür: düzensiz dizi n(n + 1)/2, kare matris n² hücre kullanır. Kazanç, yarıya yakın bellektir.

3.4.4İki boyutlu dizide sığ ve derin kopya

Matrisin dizilerin dizisi olması, kopyalamada beklenmedik bir sonuç doğurur. 3.2.6'da clone()'un dizinin bağımsız bir kopyasını oluşturduğu söylenmişti. Bu, öğeleri sayı olan dizi için doğrudur. Matriste ise dış dizinin öğeleri referanstır ve clone() referansları kopyalar, gösterdikleri satırları değil.

Aşağıdaki kod iki kopya türünü yan yana gösterir:

int[][] m = { {1, 2}, {3, 4} };
int[][] s = m.clone();          // sığ kopya
s[0][0] = 9;                    // m[0][0] de 9!
s[1] = new int[] {7, 8};        // yalnız s değişir
int[][] d = new int[2][];       // derin kopya:
for (int i = 0; i < 2; i++)
    d[i] = m[i].clone();        // satırlar da
d[0][1] = 5;                    // m etkilenmez

Örnekteki 3. ve 4. adımlar, sığ kopyanın davranışını anlamanın anahtarıdır. s[0][0] = … ortak bir satırın içini değiştirir; bu değişiklik m'den de görünür. s[1] = … ise s'nin dış dizisindeki bir referansı değiştirir; s'nin dış dizisi m'ninkinden ayrı olduğu için m etkilenmez. Kural kısaca şudur: sığ kopyada iki dış dizi ayrıdır, satırlar ortaktır.

Derin kopyanın maliyeti, bütün hücrelerin kopyalanmasıdır: r satır ve c sütunlu matriste O(r · c) zaman ve O(r · c) ek bellek. Sığ kopya yalnız dış diziyi kopyaladığı için O(r) sürer. Sığ kopya ucuzdur, ama ancak satırlar hiç değiştirilmeyecekse güvenlidir.

3.4.5Matrisi doldurma ve yazdırma

Matrisin bütün hücrelerini gezmenin standart yolu iç içe iki döngüdür: dış döngü satırları, iç döngü sütunları gezer. Aşağıdaki program 3 × 3'lük bir matrisi 1'den 9'a kadar sayılarla doldurur ve tablo biçiminde yazdırır:

public class CokBoyutluDiziOrnegi {
  public static void main(String[] a) {
    int[][] matris = new int[3][3];
    // ilk değer atama: 1…9
    for (int i = 0; i < 3; i++)      // satır
      for (int j = 0; j < 3; j++)    // sütun
        matris[i][j] = i * 3 + j + 1;

    System.out.println("Matrisin İçeriği:");
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++)
        System.out.print(matris[i][j] + " ");
      System.out.println();   // yeni satır
    }
  }
}

Çıktı:

Matrisin İçeriği:
1 2 3
4 5 6
7 8 9

Doldurma döngüsünde her hücreye i * 3 + j + 1 yazılır. Bu ifade satır satır numaralandırmanın formülüdür. i. satırdan önce i tam satır, yani i × 3 hücre vardır. Satırın içinde j hücre daha geçilir. Sonuca 1 eklenir, çünkü numaralar 0'dan değil 1'den başlıyor. Tablo 3.17 dokuz atamayı sırasıyla gösterir.

Tablodaki sıra, iç içe döngülerin çalışma düzenini gösterir. i sabit kalırken j 0, 1, 2 değerlerini alır; iç döngü bitince i bir artar ve j yeniden 0'dan başlar. Dış döngünün her turu, iç döngünün bütün turlarını içerir. Bu yüzden gövde 3 × 3 = 9 kez çalışır. Genel olarak r × c'lik bir matriste gövde r · c kez çalışır ve doldurmanın maliyeti O(r · c)'dir.

Yazdırma döngüsü aynı düzeni izler, ama bir farkla. İç döngü bir satırın öğelerini print ile aynı satıra yazar. İç döngü bittiğinde dış döngünün gövdesindeki System.out.println() çalışır ve imleç alt satıra geçer. println() iç döngünün içine konsaydı her sayı ayrı satıra yazılırdı; hiç konmasaydı dokuz sayı tek satıra yazılırdı.

Programda sınırlar sabit 3 olarak yazılmıştır. Aynı kod i < matris.length ve j < matris[i].length ile yazılırsa her boyuttaki matriste, düzensiz dizilerde bile doğru çalışır. İç döngünün sınırının matris[0].length değil matris[i].length olması, düzensiz dizide her satırın kendi uzunluğunun kullanılmasını sağlar.

3.4.6Üç boyutlu diziler

Java'da üç ya da daha çok boyutlu diziler de tanımlanabilir. Üç boyutlu bir dizi, matrislerden oluşan bir dizidir. Zaman içinde değişen bir tablo (zaman × satır × sütun) ya da renkli bir resmin kırmızı, yeşil ve mavi katmanları böyle tutulabilir.

int[][][] ucBoyutluDizi =
        new int[3][3][3];
for (int x = 0; x < 3; x++)
  for (int y = 0; y < 3; y++)
    for (int z = 0; z < 3; z++)
      ucBoyutluDizi[x][y][z] =
          x * 9 + y * 3 + z + 1;

// yazdırma: aynı üç döngü;
// z döngüsünden sonra println (y),
// y döngüsünden sonra println (x)

Her boyut bir iç içe döngü demektir. 3 × 3 × 3'lük dizide en içteki atama 27 kez çalışır. Hücrelere yazılan x * 9 + y * 3 + z + 1 değeri, matris örneğindeki formülün bir boyut genişletilmiş hâlidir: her katman 9 hücre, her satır 3 hücre içerir. Örneğin ucBoyutluDizi[1][2][0] = 1 · 9 + 2 · 3 + 0 + 1 = 16'dır.

Yazdırma için de aynı üç döngü kullanılır. z döngüsü bittiğinde bir satır tamamlanmıştır ve println ile alt satıra geçilir. y döngüsü bittiğinde bir katman tamamlanmıştır ve katmanları ayırmak için bir boş satır daha yazılır.

Boyut sayısı arttıkça öğe sayısı hızla büyür: her boyutu 100 olan üç boyutlu bir int dizisi bir milyon öğe, yani yaklaşık 4 MB veri tutar. Dört boyutta bu 400 MB olur. Çok boyutlu diziler kullanılırken bellek ihtiyacı önceden hesaplanmalıdır.

Değişken adında Türkçe karakter kullanmak (örneğin üçBoyutluDizi) Java'da geçerlidir. Yine de kaynak dosyalar farklı kodlamalarla açılabildiği ve bazı araçlar bu karakterleri bozabildiği için ASCII adlar (ucBoyutluDizi) daha güvenlidir.

3.4.7Matris transpozu

Transpozda satırlar sütuna, sütunlar satıra dönüşür. 2 satır ve 3 sütunlu bir matrisin transpozu 3 satır ve 2 sütunludur. Matrisin 0. satırı, transpozun 0. sütunu olur.

static int[][] transpoz(int[][] m) {
    int satir = m.length;
    int sutun = m[0].length;
    int[][] t = new int[sutun][satir];
    for (int i = 0; i < satir; i++)
        for (int j = 0; j < sutun; j++)
            t[j][i] = m[i][j];
    return t;
}
static void yazdirMatris(int[][] m) {
    for (int[] s : m) {
        for (int x : s)
            System.out.print(x + " ");
        System.out.println();
    }
}

transpoz metodu önce boyutları bulur. m.length satır sayısıdır; m[0].length ilk satırın uzunluğu, yani sütun sayısıdır. Sonra boyutları yer değiştirmiş yeni bir matris oluşturur: new int[sutun][satir]. İç içe döngüler m'nin her hücresini bir kez gezer ve değerini t'deki yansımasına yazar: t[j][i] = m[i][j].

yazdirMatris metodu iki for-each döngüsüyle çalışır. Dış döngüde s sırayla her satır dizisini, iç döngüde x o satırın her öğesini alır. Bu yazım indis kullanmadığı için düzensiz dizilerde de doğru çalışır.

Metotlar static tanımlanmıştır. Bunun nedeni, onları çağıracak olan main'in de static olmasıdır. Statik bir metot, bir nesne oluşturmadan yalnız sınıfın öteki statik metotlarını doğrudan çağırabilir. static yazılmazsa main'den çağrı derleme hatası verir.

m = {{1, 2, 3}, {4, 5, 6}} için transpoz(m) çağrısını izleyelim. satir = 2, sutun = 3'tür ve t 3 × 2'lik, sıfırlarla dolu bir matris olarak başlar.

İlk üç atamadan sonra t'nin 0. sütunu 1, 2, 3 olmuştur; bu, m'nin 0. satırıdır. Son üç atama m'nin 1. satırını t'nin 1. sütununa yazar. yazdirMatris(t) çıktısı “1 4”, “2 5”, “3 6” satırlarıdır.

Her öğe bir kez kopyalanır: m × n'lik matriste m · n atama yapılır ve süre O(m · n)'dir. Sonuç yeni bir matriste tutulduğu için ek bellek de O(m · n)'dir. Kare matrislerin transpozu yerinde de alınabilir: köşegenin üstündeki her hücre, köşegenin altındaki yansımasıyla takas edilir. Kare olmayan matriste boyutlar değiştiği için bu yapılamaz.

3.4.8Uygulama: Tic Tac Toe

İki boyutlu dizilerin tipik bir uygulaması, tahta üzerinde oynanan oyunlardır. Tic Tac Toe (X-O oyunu) bunların en basitidir:

• Oyun 3 × 3'lük bir tahtada oynanır; tahta bir char[][] dizisidir.
• İki oyuncu, X ve O, sırayla boş bir hücreye kendi işaretini koyar.
• Kendi işaretini aynı satırda, aynı sütunda ya da bir çaprazda üçleyen oyuncu kazanır.
• Tahtada boş hücre kalmaz ve kimse kazanmamışsa oyun berabere biter.

Oyunun her hamlesi tek bir dizi atamasıdır: tahta[satir][sutun] = oyuncu. Programın geri kalanı, bu atamanın etrafındaki denetimlerdir. Ana döngü şöyledir:

public class TicTacToe {   // import java.util.Scanner;
    static Scanner scanner = new Scanner(System.in); // tek Scanner

    public static void main(String[] args) {
        char[][] tahta = new char[3][3];   // 3x3'lük oyun tahtası
        char oyuncu = 'X';                   // ilk oyuncu X
        boolean oyunDevamEdiyor = true;
        tahtaDoldur(tahta);                  // tüm hücreler ' '
        while (oyunDevamEdiyor) {
            tahtayiGoster(tahta);
            hamleYap(tahta, oyuncu);
            oyunDevamEdiyor = oyunDevamEdiyorMu(tahta, oyuncu);
            oyuncu = (oyuncu == 'X') ? 'O' : 'X';   // sıra değişir
        }
        tahtayiGoster(tahta);
    }

main metodu tahtayı oluşturur, ilk oyuncuyu X yapar ve oyun bitene kadar dört adımı yineler: tahtayı göster, hamle al, oyunun bitip bitmediğini denetle, sırayı öbür oyuncuya ver. Sıra değişimi koşul işleciyle yazılmıştır: (oyuncu == 'X') ? 'O' : 'X', oyuncu X ise O'yu, değilse X'i verir.

new char[3][3] ile oluşturulan tahtanın hücreleri '\u0000' ile başlar (3.2.1). Bu karakter ekranda görünmez ve boşluk karakterinden farklıdır. Boş hücreyi ' ' (boşluk) ile göstermek için tahta oyun başlamadan tahtaDoldur ile doldurulur. Sınıfın başında tanımlanan scanner alanı da static'tir, çünkü statik metotlardan kullanılır; programın tamamı tek bir Scanner ile çalışır.

static void tahtaDoldur(char[][] t) {
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      t[i][j] = ' ';
}
static void tahtayiGoster(char[][] t) {
  System.out.println("-------------");
  for (int i = 0; i < 3; i++) {
    System.out.print("| ");
    for (int j = 0; j < 3; j++)
      System.out.print(t[i][j]+" | ");
    System.out.println("\n-------------");
  }
}

tahtaDoldur iç içe döngüyle dokuz hücrenin hepsine boşluk yazar. tahtayiGoster tahtayı çizgilerle çevrili bir tablo olarak yazar. Her satırdan sonra yazılan "\n-------------" metnindeki \n, satır sonu karakteridir; önce satır biter, sonra ayırıcı çizgi yazılır.

static void hamleYap(char[][] t,
                     char oyuncu) {
  int satir, sutun;
  do {
    System.out.print("Sıra " + oyuncu
      + ": satır ve sütun (1-3): ");
    satir = scanner.nextInt() - 1;
    sutun = scanner.nextInt() - 1;
  } while (satir < 0 || satir > 2
        || sutun < 0 || sutun > 2
        || t[satir][sutun] != ' ');
  t[satir][sutun] = oyuncu;
}
// kullanıcı 1-3 girer, dizi 0-2;
// geçersiz/dolu hücre → tekrar sor

hamleYap metodu, geçerli bir hamle gelene kadar kullanıcıya sorar. Bunun için bir do-while döngüsü kullanır. Bu döngünün gövdesi koşul denetlenmeden önce bir kez çalışır; ilk soruyu sormadan önce denetlenecek bir şey olmadığı için bu yapı burada doğaldır. Kullanıcı satır ve sütunu 1–3 aralığında girer, dizi ise 0–2 kullanır; bu yüzden okunan sayılardan 1 çıkarılır. Döngü üç durumda soruyu yineler: satır geçersizse, sütun geçersizse ya da hücre dolu ise. Koşuldaki sıra önemlidir: önce indislerin geçerliliği denetlenir. || işleci soldan sağa değerlendirilir ve ilk doğru koşulda durur. Böylece geçersiz indisle t[satir][sutun]'a hiç erişilmez.

3.4.9Kazanma ve beraberlik denetimi

3 × 3'lük tahtada kazanmanın 8 yolu vardır: 3 satır, 3 sütun ve 2 çapraz. Bu sekiz çizgiyi tek tek yazmak yerine, satır ve sütunlar bir döngüyle, çaprazlar tek bir return ifadesiyle denetlenir:

static boolean kazandi(char[][] t, char o) {
    for (int i = 0; i < 3; i++)
        if ((t[i][0] == o && t[i][1] == o && t[i][2] == o)     // satır i
         || (t[0][i] == o && t[1][i] == o && t[2][i] == o))    // sütun i
            return true;
    return (t[0][0] == o && t[1][1] == o && t[2][2] == o)      // ana çapraz
        || (t[0][2] == o && t[1][1] == o && t[2][0] == o);     // ters çapraz
}
static boolean oyunDevamEdiyorMu(char[][] t, char o) {
    if (kazandi(t, o)) {
        System.out.println("Tebrikler, " + o + " oyuncusu kazandı!");
        return false;
    }
    for (char[] satir : t)
        for (char c : satir)
            if (c == ' ') return true;          // boş hücre var → devam
    System.out.println("Oyun berabere bitti.");
    return false;
}

kazandi metodunun döngüsü i = 0, 1, 2 için iki çizgiyi birden sınar. t[i][0], t[i][1], t[i][2] i. satırın; t[0][i], t[1][i], t[2][i] i. sütunun hücreleridir. Satır ile sütun arasındaki tek fark indislerin yer değiştirmesidir; transpozdaki ilişkinin aynısı. Döngüde kazanan bir çizgi bulunmazsa iki çapraz denetlenir: ana çapraz [0][0], [1][1], [2][2]; ters çapraz [0][2], [1][1], [2][0].

oyunDevamEdiyorMu önce son hamleyi yapan oyuncunun kazanıp kazanmadığına bakar. Kazanmışsa tebrik iletisini yazar ve false döndürür. Kazanmamışsa tahtada boş hücre arar. Tek bir boş hücre bulmak oyunun sürmesi için yeter; metot ilk boş hücrede true döndürür. Hiç boş hücre yoksa oyun berabere biter. Yalnız son hamleyi yapan oyuncunun denetlenmesi yeterlidir, çünkü bir hamle yalnız onu yapanı kazandırabilir.

Kazanma denetimini şu tahta üzerinde izleyelim: son hamleyi X yapmıştır ve tahta satır satır X O _ / _ X O / _ _ X durumundadır (_ boş hücre).

Tablo, && ve || işleçlerinin kısa devre davranışını gösterir. && ile bağlı üç koşuldan biri yanlış çıkınca ifadenin sonucu kesin olarak yanlıştır ve kalan koşullara bakılmaz. Satır 0'da t[0][0] 'X'tir, ama t[0][1] 'O' olduğu için t[0][2]'ye hiç bakılmaz. Satır 1'de ilk hücre t[1][0] zaten boştur ve kalan iki hücre atlanır. Son satırda ||'nin sol tarafı, yani ana çapraz doğrudur; ifadenin sonucu kesinleşmiştir ve ters çapraza hiç bakılmaz. Metot true döndürür.

Tahta hep 3 × 3 olduğu için kazandi en çok 8 çizgiyi, yani 24 hücreyi denetler; bu sabit bir iştir. Tahta n × n olsaydı ve n işaretin üçlenmesi gerekseydi, 2n + 2 çizginin her biri n hücre içerirdi ve denetim O(n²) sürerdi. Daha akıllı bir denetim yalnız son hamlenin satırına, sütununa ve (varsa) çaprazlarına bakar ve O(n)'de biter.

3.5Dizi işlemlerinin karmaşıklığı

Önceki kesimlerde her algoritmanın sonunda bir maliyet verildi: O(1), O(n), O(n log n). Bu kesim bu gösterimi kısaca açıklar ve dizi üzerindeki temel işlemlerin maliyetlerini tek tek gerekçelendirir. Amaç, “bu işlem hızlı mı?” sorusunu ezbere değil, işlemin dizide ne yaptığına bakarak cevaplayabilmektir.

3.5.1Dizi işlemlerinin maliyeti

Algoritma karmaşıklığı, bir algoritmanın çalışma süresinin ve bellek kullanımının girdi boyutu n büyüdükçe nasıl büyüdüğünü anlatır. Süre saniye olarak ölçülmez, çünkü saniye bilgisayardan bilgisayara değişir. Bunun yerine algoritmanın attığı temel adımlar (karşılaştırma, atama, toplama gibi) sayılır ve bu sayının n'ye göre büyüme hızına bakılır.

Sık karşılaşılan büyüme hızlarının anlamı şudur:

• O(1), sabit: adım sayısı n'ye bağlı değildir.
• O(log n), logaritmik: n iki katına çıkınca yalnız bir adım artar.
• O(n), doğrusal: n iki katına çıkınca adım sayısı da iki katına çıkar.
• O(n log n): doğrusaldan biraz hızlı büyür; iyi sıralama algoritmalarının maliyetidir.
• O(n²), karesel: n iki katına çıkınca adım sayısı dört katına çıkar.

Farkın ne kadar büyük olduğunu bir örnek gösterir. Bir milyon öğeli dizide log₂ n yaklaşık 20, n bir milyon, n² ise bir trilyondur. Saniyede bir milyar adım atan bir bilgisayarda doğrusal bir algoritma binde bir saniyede biter; karesel bir algoritma ise yaklaşık 17 dakika sürer.

Aynı algoritmanın süresi girdinin kendisine de bağlı olabilir. Doğrusal aramada aranan değer dizinin başındaysa iş hemen biter, hiç yoksa bütün dizi gezilir. Bu yüzden maliyetler çoğu zaman en iyi durum, ortalama durum ve en kötü durum için ayrı verilir. Aksi söylenmedikçe verilen maliyet en kötü durumun maliyetidir; algoritmanın hiçbir girdide bundan yavaş çalışmayacağını garanti eder. Tablo 3.20 dizi işlemlerini özetler.

3.5.2Erişim: O(1)

int[] dizi = {10, 20, 30, 40, 50};
int oge = dizi[2];      // 30 — tek adımda, O(1)

dizi[2] okunurken dizinin başından başlanıp öğeler sayılmaz. 3.1.2'deki formül uygulanır: başlangıç adresine indis ile öğe boyutunun çarpımı eklenir. Bu, dizinin boyutundan bağımsız olarak bir çarpma, bir toplama ve bir bellek okumasıdır. Beş öğeli dizide de beş milyon öğeli dizide de aynı sürer. Erişim bu yüzden O(1)'dir. Aynı hesap yazma için de geçerlidir: dizi[2] = 35 da O(1)'dir.

Bu üstünlük her veri yapısında yoktur. Bağlı listede öğeler bellekte dağınık durur ve her öğe yalnız bir sonrakinin yerini bilir. k. öğeye ulaşmak için baştan başlayıp k adım yürümek gerekir; erişim O(n)'dir. İndisle erişimin sık yapıldığı her problemde dizi bu yüzden doğal seçimdir.

3.5.3Doğrusal arama: O(n)

Erişim, indisi bilinen bir öğeyi okumaktır. Arama ise ters soruyu sorar: belli bir değer dizide var mı, varsa nerede? Dizi sırasızsa değerin nerede olabileceği hakkında hiçbir ipucu yoktur. Tek yol, öğelere baştan başlayarak tek tek bakmaktır. Bu yönteme doğrusal arama (linear search) denir.

static boolean dogrusalArama(int[] dizi,
                           int hedef) {
    for (int oge : dizi)
        if (oge == hedef)
            return true; // bulundu
    return false;
}

Metot dizinin her öğesini sırayla hedefle karşılaştırır. Eşit bir öğe bulduğu anda true döndürür ve döngüden çıkar; kalan öğelere bakmaz. Döngü bütün diziyi gezip bitirdiyse hedef dizide yoktur ve metot false döndürür. return false'un döngünün dışında durması önemlidir.

Metodu {7, 2, 9, 5, 1, 8} dizisinde iki kez çağıralım: önce 5'i, sonra 3'ü arayalım.

İlk çağrıda 5, 3 indisinde bulunur ve 4 karşılaştırma yapılır; 1 ve 8'e hiç bakılmaz. İkinci çağrıda 3 dizide yoktur. Bunu kesin olarak söyleyebilmek için bütün öğelere bakmak gerekir: n = 6 karşılaştırma.

Üç durumu ayrı ayrı düşünelim:

• En iyi durum: Hedef ilk öğedir. 1 karşılaştırma yeter: O(1).
• En kötü durum: Hedef son öğedir ya da dizide yoktur. n karşılaştırma gerekir: O(n).
• Ortalama durum: Hedef dizide varsa ve her konumda olma olasılığı eşitse, ortalama (n + 1)/2 karşılaştırma yapılır. Bu da n ile doğru orantılıdır: O(n).

Dizi sıralıysa çok daha hızlı bir yol vardır. 3.2.7'deki ikili arama her adımda aralığı yarıya indirir ve O(log n)'de biter. Ama diziyi sıralamak O(n log n) sürer. Tek bir arama için sıralamak, doğrusal aramadan pahalıdır. Aynı dizide çok sayıda arama yapılacaksa bir kez sıralayıp her aramayı ikili aramayla yapmak kazançlıdır.

3.5.4İç içe döngü: iki dizide ortak öğe

İki dizide ortak olan öğeleri bulmak istensin. En düz yol, birinci dizinin her öğesini ikinci dizinin her öğesiyle karşılaştırmaktır:

static void eslestir(int[] dizi1, int[] dizi2) {
    for (int oge1 : dizi1)          // n kez
        for (int oge2 : dizi2)      // m kez
            if (oge1 == oge2)
                System.out.println(
                    "Eşleşen öğe: " + oge1);
}

Dış döngü dizi1'in her öğesi için bir kez döner: n tur. Her turda iç döngü dizi2'nin bütün öğelerini gezer: m tur. Toplam karşılaştırma sayısı n · m'dir ve bu sayı girdiye göre değişmez. Eşleşme bulunsa da iç döngü sürer, çünkü kodda erken çıkış yoktur.

eslestir({3, 7, 5}, {5, 1, 3, 8}) çağrısını izleyelim:

Metot “Eşleşen öğe: 3” ve “Eşleşen öğe: 5” satırlarını yazar ve 3 × 4 = 12 karşılaştırma yapar. Şekil 3.28, bu karşılaştırmaları bir tablo olarak gösterir: her satır dizi1'in bir öğesi, her sütun dizi2'nin bir öğesidir ve tablonun her hücresi bir karşılaştırmadır.

İki dizi de n öğeliyse karşılaştırma sayısı n²'dir: O(n²). Küçük dizilerde bu sorun değildir. Ama iki dizi de 100.000 öğeli olsa 10 milyar karşılaştırma gerekir. Daha iyi iki yol vardır:

• İkinci diziyi sıralayıp birinci dizinin her öğesini ikili aramayla aramak. Sıralama O(n log n), n ikili arama da O(n log n)'dir; toplam O(n log n).
• İkinci dizinin öğelerini bir hash kümesine koyup birinci dizinin her öğesini kümede aramak. Kümede arama ortalama O(1) sürdüğü için toplam ortalama O(n)'dir.

3.5.5Araya ekleme: sağa kaydırma

Dizinin boyutu sabit olduğu için “ekleme” ancak dizide kullanılmayan yer varsa yapılabilir. Uygulamada dizi çoğu zaman kapasitesinden az öğe tutar ve kaç hücrenin dolu olduğu ayrı bir değişkende (boyut) izlenir. Dolu hücreler her zaman dizinin başında, arada boşluk olmadan durur. 3.2.11'de anılan dinamik dizi de bu düzenle çalışır.

Dizinin ortasına bir öğe eklemek için önce yer açmak gerekir. Ekleme konumundan sonraki bütün öğeler birer hücre sağa kaydırılır, sonra açılan hücreye yeni değer yazılır:

static int ekle(int[] a, int boyut,
             int indis, int deger) {
  // ön koşul: boyut < a.length
  for (int k = boyut; k > indis; k--)
    a[k] = a[k - 1];   // sağa kaydır
  a[indis] = deger;
  return boyut + 1;   // yeni boyut
}

Metot dört parametre alır: dizi a, dolu hücre sayısı boyut, ekleme konumu indis ve eklenecek deger. Yorumdaki ön koşul, metodun yalnız dizide boş yer varken çağrılabileceğini söyler. Döngü k'yi boyut'tan başlatır ve indis'e kadar geriye doğru götürür. Her turda k − 1'deki öğe k'ye kopyalanır. Döngü bitince indis'teki hücreye yeni değer yazılır ve yeni boyut döndürülür.

Kapasitesi 6 olan a = {7, 2, 9, 5, 1, _} dizisinde (5 hücre dolu) 4'ü 1 indisine ekleyelim: ekle(a, 5, 1, 4).

Metot 6 döndürür. Dört kaydırma yapılmıştır: 1, 5, 9 ve 2 birer sağa geçmiştir. Döngü bittiğinde a[1] ile a[2] geçici olarak aynı değeri (2) taşır; a[1] = 4 ataması bu durumu düzeltir.

Kaydırmanın neden sağdan başladığı önemlidir. Soldan başlansaydı ilk adımda a[2] = a[1] yazılır ve 9 kaybolurdu: 9'un üzerine 2 yazılmıştır ve 9 hiçbir yerde saklanmamıştır. Sonraki adımlarda da 2 sağa doğru çoğalırdı. Sağdan başlamak, her öğenin üzerine yazılmadan önce sağa taşınmasını sağlar. İlk kopyalama boş hücreye yapılır, sonraki her kopyalama da bir önceki adımda taşınmış öğenin eski yerine.

Kaydırma sayısı boyut − indis'tir. Maliyet ekleme konumuna bağlıdır:

• Başa ekleme (indis = 0): n kaydırma, O(n). En kötü durum budur.
• Ortaya ekleme: yaklaşık n/2 kaydırma; bu da O(n)'dir.
• Sona ekleme (indis = boyut): döngü hiç dönmez, yalnız bir atama yapılır: O(1).

Dizi doluysa (boyut == a.length) ekleme yapılamaz. Önce daha büyük bir dizi oluşturulup öğeler ona kopyalanmalıdır; bu da O(n) sürer. Kapasite her seferinde iki katına çıkarılırsa bu kopyalamalar seyrek olur ve sona eklemenin ortalama maliyeti sabit kalır.

3.5.6Aradan silme: sola kaydırma

Silme, eklemenin tersidir. Bir öğe silindiğinde dizide boşluk kalmaması gerekir; silinen konumdan sonraki bütün öğeler birer hücre sola kaydırılır:

static int sil(int[] a, int boyut, int indis) {
  for (int k = indis; k < boyut - 1; k++)
    a[k] = a[k + 1];   // sola kaydır
  a[boyut - 1] = 0;    // eski son hücreyi temizle
  return boyut - 1;    // yeni boyut
}

Döngü k'yi silinen konumdan başlatır ve her turda sağdaki öğeyi sola kopyalar. Bu kez kaydırma soldan başlar. İlk kopyalama silinecek değerin üzerine yazar; silinen değerin kaybolması zaten istenen şeydir. Sonraki her kopyalama, bir önceki adımda sola taşınmış öğenin eski yerine yazar. Sağdan başlansaydı bu kez öğeler kaybolurdu.

Önceki eklemenin sonucunda a = {7, 4, 2, 9, 5, 1}'dir. 1 indisindeki 4'ü silelim: sil(a, 6, 1).

Metot 5 döndürür ve dizi eklemeden önceki hâline döner. Dört kaydırma yapılmıştır. Döngü bittiğinde son hücrede, sola taşınmış olan 1'in eski bir kopyası kalmıştır. Bu hücre artık kullanılmayan alana düştüğü için a[5] = 0 ile temizlenir. int dizisinde bu temizlik zorunlu değildir; boyut zaten 5'e indiği için o hücre okunmaz. Ama nesne dizisinde bu hücreye null yazmak gerekir. Yazılmazsa hücre, silinmiş bir nesnenin referansını tutmaya devam eder ve çöp toplayıcı o nesneyi toplayamaz. Programın artık kullanmadığı nesnelerin böyle bellekte kalmasına bellek sızıntısı denir.

Kaydırma sayısı boyut − indis − 1'dir. Baştan silmede n − 1 kaydırma yapılır: O(n). Sondan silmede döngü hiç dönmez: O(1). Ekleme ve silme maliyetlerinin ikisi de konuma bağlıdır ve dizinin başında en yüksektir. Sık sık baştan ekleme ya da silme yapılan bir problemde dizi iyi bir seçim değildir.

3.5.7Sıralama algoritmalarının maliyeti

Sıralı bir dizi pek çok işi kolaylaştırır: ikili arama, ortanca, mod, tekrar eden öğeleri bulma. Ama sıralamanın kendisi de bir maliyettir ve bu maliyet kullanılan algoritmaya bağlıdır. Tablo 3.25 sık kullanılan beş algoritmayı karşılaştırır.

* Kabarcık sıralamasının en iyi durumu, hiç takas yapılmayan bir turda duran sürüm için geçerlidir. Zaten sıralı bir dizide bu sürüm tek bir turda durur.

** Hızlı sıralamanın ek belleği özyinelemenin derinliğidir: ortalamada O(log n), en kötü durumda O(n). Önce küçük parçayı sıralayan gerçeklemeler en kötü durumda da O(log n)'de kalır.

Tablodan üç gözlem çıkar. Birincisi, ilk üç algoritma basittir ve ek bellek istemez, ama ortalama durumda O(n²)'dir; ancak küçük dizilerde kullanışlıdır. İkincisi, hızlı sıralama ortalamada çok hızlıdır, ama en kötü durumu karesel olabilir. Bu durum kötü pivot seçiminde ortaya çıkar. Pivot, diziyi ikiye bölmek için seçilen öğedir. Örneğin zaten sıralı bir dizide her seferinde ilk öğe pivot seçilirse bölmeler hep dengesiz olur. Üçüncüsü, birleştirme sıralaması her durumda O(n log n)'dir, ama O(n) ek bellek ister.

Java'nın Arrays.sort metodu türe göre farklı algoritma kullanır. İlkel tipli dizilerde (int[], double[] …) çift pivotlu hızlı sıralama kullanılır. Nesne dizilerinde ise kararlı (stable) bir algoritma olan TimSort kullanılır. Kararlı bir sıralama, eşit anahtarlı öğelerin baştaki göreli sırasını korur. Öğrencileri önce ada, sonra nota göre sıralayan bir program, ikinci sıralamada aynı notu alanların ad sırasının bozulmamasını ister. İlkel değerlerde eşit öğeler birbirinden ayırt edilemediği için kararlılık gerekmez.

3.5.8Seçimli sıralama

Seçimli sıralama diziyi iki kısma ayrılmış olarak düşünür: solda sıralanmış kısım, sağda sıralanmamış kısım. Başta sıralanmış kısım boştur. Her turda sıralanmamış kısmın en küçük öğesi seçilir ve o kısmın başındaki öğeyle takas edilir. Böylece sıralanmış kısım bir öğe büyür. n − 1 turdan sonra dizi sıralıdır; son öğe kendiliğinden yerine oturur.

int[] dizi = {64, 25, 12, 22, 11};
int n = dizi.length;
for (int i = 0; i < n - 1; i++) {
    int minIndis = i;
    for (int j = i + 1; j < n; j++)
        if (dizi[j] < dizi[minIndis])
            minIndis = j;
    // takas: indislerle, yerinde
    int gecici = dizi[minIndis];
    dizi[minIndis] = dizi[i];
    dizi[i] = gecici;
}

Dış döngünün i değişkeni, sıralanmamış kısmın başıdır. minIndis şimdilik i'dir; yani “şu ana kadar görülen en küçük öğe, sıralanmamış kısmın ilk öğesi”dir. İç döngü i + 1'den sonuna kadar gider ve daha küçük bir öğe gördüğünde minIndis'i günceller. İç döngü bitince en küçük öğe i konumundaki öğeyle takas edilir. Takas, 3.3.8'deki gibi geçici bir değişkenle ve indisler üzerinden yapılır.

{64, 25, 12, 22, 11} dizisini sıralayalım:

1. turda en küçük öğe 11'dir ve dizinin sonundadır; 64 ile takas edilir ve 0 indisi kesin olarak yerini bulur. 2. turda sıralanmamış kısım 1 indisinden başlar ve en küçüğü 12'dir. 4. turda en küçük öğe zaten başta durur (minIndis = i = 3); takas kendisiyle yapılır ve dizi değişmez. Son öğe olan 64 kendiliğinden yerindedir.

Örnekte n = 5'tir ve 4 + 3 + 2 + 1 = 10 = 5 · 4 / 2 karşılaştırma yapılmıştır. Seçimli sıralama zaten sıralı bir dizide de 10 karşılaştırma yapar; girdinin sıralı olduğunu fark etmez. Buna karşılık takas sayısı en çok n − 1'dir. Takasın pahalı olduğu durumlarda (örneğin öğeler büyük kayıtlar olduğunda) bu bir üstünlüktür.

3.5.9Eklemeli sıralama

Eklemeli sıralama, elindeki iskambil kâğıtlarını sıraya koyan bir oyuncunun yöntemine benzer. Oyuncu kâğıtları birer birer alır ve her yeni kâğıdı, elindeki sıralı kâğıtların arasında doğru yere sokar. Dizide de sol kısım her zaman sıralıdır. Başta bu kısım yalnız a[0]'dır; tek öğeli bir dizi her zaman sıralıdır. Her turda sıralı kısmın hemen sağındaki öğe alınır ve sıralı kısımda doğru yerine yerleştirilir.

static void eklemeliSirala(int[] a) {
    for (int k = 1; k < a.length; k++) {
        int anahtar = a[k];
        int j = k;
        while (j > 0 && a[j - 1] > anahtar) {
            a[j] = a[j - 1];   // sağa kaydır
            j--;
        }
        a[j] = anahtar;        // yerleş
    }
}

Her turda sıradaki öğe anahtar değişkenine alınır. Bu andan sonra anahtarın hücresi bir “boşluk” sayılabilir; değeri anahtar'da güvendedir. while döngüsü boşluğun solundaki öğeye bakar. O öğe anahtardan büyükse bir sağa, boşluğa kaydırılır ve boşluk bir sola geçer. Soldaki öğe anahtardan büyük değilse ya da sıralı kısmın başına gelinmişse (j == 0) döngü durur ve anahtar boşluğa yerleştirilir. Bu kaydırma, 3.5.5'teki araya eklemenin aynısıdır; tek fark, ekleme konumunun kaydırma sırasında bulunmasıdır.

{5, 2, 4, 1, 3} dizisini sıralayalım:

3. turu ayrıntılı izleyelim. Anahtar 1'dir ve sıralı kısım {2, 4, 5}'tir. a[2] = 5 > 1 olduğu için 5 sağa kayar, boşluk 2 indisine geçer. a[1] = 4 > 1 olduğu için 4 sağa kayar, boşluk 1 indisine geçer. a[0] = 2 > 1 olduğu için 2 de kayar ve boşluk 0 indisine gelir. j artık 0'dır ve döngü durur; a[0] = 1 yazılır. Anahtar, sıralı kısmın hepsinden küçük olduğu için bütün kısım kaydırılmıştır.

Toplam 1 + 1 + 3 + 2 = 7 kaydırma yapılmıştır. Bu sayı rastgele değildir; dizinin ne kadar “bozuk” olduğunu ölçen bir büyüklüğe eşittir.

{5, 2, 4, 1, 3} dizisinin ters sıralı çiftleri (değerleriyle) şunlardır: (5, 2), (5, 4), (5, 1), (5, 3), (2, 1), (4, 1), (4, 3). Toplam 7 çift vardır; kaydırma sayısı da 7'dir.

Teorem, eklemeli sıralamanın neden “neredeyse sıralı” dizilerde çok hızlı olduğunu açıklar. Az sayıda öğesi yerinden oynamış bir dizide ters sıralı çift az olur ve algoritma doğrusala yakın sürede biter. Seçimli sıralama ise sıralı dizide bile n(n − 1)/2 karşılaştırma yapar. TimSort gibi gerçek kütüphane algoritmaları bu yüzden küçük parçaları eklemeli sıralamayla sıralar. Eklemeli sıralama ayrıca kararlıdır: a[j − 1] > anahtar koşulu eşit öğede durur ve eşit öğelerin sırası korunur.

3.5.10Alan karmaşıklığı ve bellek kullanımı

Alan karmaşıklığı (space complexity), bir algoritmanın ya da veri yapısının bellek ihtiyacının n ile nasıl büyüdüğünü anlatır. Zaman karmaşıklığıyla aynı gösterim kullanılır. n öğeli bir dizi O(n) alan kaplar. Bayt olarak miktar ise öğe tipine bağlıdır.

Tablonun iki ayrıntısı açıklama ister. Java'da char, UTF-16 kodlamasında bir kod birimidir ve 2 bayt kaplar; ASCII karakterler için de böyledir. Referansın 4 mü 8 bayt mı olduğu JVM'e ve ayarlarına bağlıdır. 64 bitlik JVM'ler çoğu zaman referansları sıkıştırıp 4 baytta tutar.

Veri kısmına ek olarak iki maliyet daha vardır:

• Ek yük. Her dizi nesnesinin ayrıca yaklaşık 16 baytlık bir başlığı vardır. Başlıkta nesnenin türü ve dizinin length değeri gibi bilgiler tutulur. Büyük dizilerde bu yük önemsizdir; çok sayıda küçük dizide ise toplamı fark edilir.
• Referans dizileri. String[] gibi nesne dizilerinde yalnız referanslar ardışıktır. Gösterilen nesneler heap bellekte ayrı ayrı yer kaplar ve kendi başlıklarını taşır. 100 öğeli bir String[]'in 400 baytı yalnız referanslardır; metinlerin kendisi bunun üstüne eklenir.

Algoritmaların alan maliyeti de aynı biçimde düşünülür. Girdinin kendisi sayılmaz; algoritmanın ayrıca ayırdığı bellek hesaplanır. Bu bölümdeki algoritmalardan doğrusal arama, ortalama, yerinde tersine çevirme, ekleme, silme, seçimli ve eklemeli sıralama O(1) ek bellek kullanır. Ortanca ve mod, girdiyi kopyaladıkları için O(n); transpoz yeni bir matris oluşturduğu için O(m · n) ek bellek kullanır. Zaman ile bellek arasında çoğu zaman bir değiş tokuş vardır: daha çok bellek kullanmak bir algoritmayı hızlandırabilir, belleği kısmak yavaşlatabilir.

3.6Sık yapılan hatalar

Dizilerle ilgili hataların çoğu birkaç kaynaktan çıkar: indisin 0'dan başlaması, dizinin bir nesne olması ve = ile =='nin referanslar üzerinde çalışması. Tablo 3.29 notun farklı yerlerinde ele alınan hataları bir arada verir.

Tablodaki hataların ortak bir dersi vardır: bir dizi değişkeni, dizinin kendisi değil, ona giden bir oktur. = oku kopyalar, == okları karşılaştırır, println okun kendisini yazar. Dizinin içeriğiyle çalışmak isteyen her işlem ya indislerle hücrelere tek tek erişir ya da bunu yapan bir Arrays metodu kullanır.

3.7Özet

• Dizi, aynı türden sabit sayıda öğeyi bellekte ardışık yuvalarda tutar. İndisler 0'dan length − 1'e kadardır. i. öğenin adresi başlangıç + i × öğe boyutu ile tek adımda hesaplanır; bu yüzden indisle erişim O(1)'dir.
• Dizinin üstünlükleri hızlı erişim, ek referans yükünün olmaması ve önbellek dostu olmasıdır. Zayıflıkları sabit boyut, araya ekleme ve silmede kaydırma (O(n)) ve boşa giden kapasitedir. Java dizileri kovaryanttır; yanlış türde atama ancak çalışırken ArrayStoreException ile yakalanır.
• Java'da dizi bir nesnedir ve heap bellekte durur; stack bellekteki değişken yalnız referansını tutar. new ile oluşturulan dizinin öğeleri varsayılan değerleri alır (0, 0.0, false, '\u0000', null). length bir alandır.
• = referansı kopyalar; gerçek kopya için clone(), Arrays.copyOf ya da System.arraycopy kullanılır (O(n)). == referansları karşılaştırır; içerik için Arrays.equals, yazdırmak için Arrays.toString gerekir.
• Erişilemez hâle gelen dizileri çöp toplayıcı toplar. Sınır dışı erişim ArrayIndexOutOfBoundsException fırlatır; Java her erişimi denetler, C denetlemez.
• Ortalama tek geçişte O(n) zaman ve O(1) ek bellekle hesaplanır. Ortanca ve mod, dizinin sıralı bir kopyası üzerinde bulunur; maliyetleri sıralamanın getirdiği O(n log n)'dir. Kopya, çağıranın dizisini korur.
• Diziyi yerinde tersine çevirme iki uçtan ortaya ilerleyen işaretçilerle ⌊n/2⌋ takas yapar: O(n) zaman, O(1) ek bellek. Sezar şifresi, char değerlerinin tamsayı olmasından ve % 26 ile başa sarmadan yararlanır.
• Java'da matris dizilerin dizisidir: m.length satır, m[i].length o satırın sütun sayısıdır. Satırlar farklı uzunlukta olabilir (düzensiz dizi). m.clone() sığ kopya verir; derin kopya için her satır ayrıca kopyalanır.
• m × n'lik bir matrisi gezmek, doldurmak ya da transpozunu almak O(m · n)'dir. İç içe döngülerde gövde, döngü sayılarının çarpımı kadar çalışır.
• Doğrusal arama en kötü durumda O(n), ikili arama sıralı dizide O(log n)'dir. İki dizide ortak öğeyi iç içe döngüyle bulmak O(n · m)'dir.
• Araya ekleme sağdan sola, aradan silme soldan sağa kaydırır; ikisi de en kötü durumda O(n), sonda ise O(1)'dir.
• Seçimli sıralama her girdide n(n − 1)/2 karşılaştırma yapar. Eklemeli sıralama, ters sıralı çift sayısı kadar kaydırma yapar: sıralı dizide O(n), en kötü durumda O(n²). İkisi de O(1) ek bellek kullanır.

3.8Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• dizi array
• öğe element
• indis index
• ilklendirici initializer
• kapasite capacity
• statik dizi static array
• dinamik dizi dynamic array
• referans reference
• kovaryans covariance
• heap bellek heap memory
• çerçeve stack frame
• iki boyutlu dizi two-dimensional array
• çok boyutlu dizi multidimensional array
• matris matrix
• düzensiz dizi jagged array
• sığ kopya shallow copy
• derin kopya deep copy
• transpoz transpose
• ortanca median
• mod mode
• yerinde in-place
• takas swap
• doğrusal arama linear search
• ikili arama binary search
• kabarcık sıralaması bubble sort
• seçimli sıralama selection sort
• eklemeli sıralama insertion sort
• hızlı sıralama quick sort
• birleştirme sıralaması merge sort
• kararlı stable (sort)
• zaman karmaşıklığı time complexity
• alan karmaşıklığı space complexity

3.9Kendini Dene

1. int[] a = {4, 7, 1}; int[] b = a; a = new int[] {0}; b[1] = 9; satırlarından sonra a ve b hangi dizileri gösterir?

   Cevap

   a = [0], b = [4, 9, 1]. b = a ile iki değişken ilk diziyi gösterir. Sonra a'ya yeni bir dizi atanır; bu yalnız a'nın referansını değiştirir, b hâlâ ilk diziyi gösterir. b[1] = 9 o diziyi değiştirir. Yeni dizi bu değişiklikten etkilenmez.

2. Arrays.toString(new double[3]), Arrays.toString(new boolean[2]) ve Arrays.toString(new String[2]) ne yazar?

   Cevap

   [0.0, 0.0, 0.0], [false, false] ve [null, null]. new ile oluşturulan dizinin öğeleri türün varsayılan değerini alır; String'in varsayılanı boş metin değil, null'dır.

3. {10, 2, 7, 3, 100, 1} dizisinin ortalaması ve ortancası nedir? Hangisi verinin “ortasını” daha iyi anlatır?

   Cevap

   Toplam 123, ortalama 123 / 6 = 20,5'tir. Sıralı dizi {1, 2, 3, 7, 10, 100}'dür; boyut çift olduğu için 2 ve 3 indislerindeki 3 ile 7'nin ortalaması alınır: ortanca 5,0'tır. Altı değerden beşi 10 ya da altındadır; 100 değeri ortalamayı yukarı çekmiştir. Ortanca uç değerden etkilenmediği için ortayı daha iyi anlatır.

4. mod({8, 3, 8, 5, 3, 8}) ne döndürür? Döngü sırasında rekor (enCok) kaç kez değişir?

   Cevap

   Sıralı kopya {3, 3, 5, 8, 8, 8}'dir. i = 1'de 3 ikinci kez görülür ve rekor 3 (2 kez) olur. i = 2 ve i = 3'te yeni değerler başlar, sayaç 1'dir. i = 4'te 8 iki kez görülmüştür, ama 2 > 2 yanlıştır. i = 5'te 8 üç kez görülür ve rekor 8 (3 kez) olur. Metot 8 döndürür; rekor döngüde iki kez değişir.

5. sifrele("JAVA", 5) ne döndürür? Şifreyi çözmek için aynı metot hangi k ile çağrılmalıdır?

   Cevap

   J: 9 + 5 = 14 → O. A: 0 + 5 = 5 → F. V: 21 + 5 = 26, 26 % 26 = 0 → A. A → F. Sonuç "OFAF"'tır. Çözmek için k = 26 − 5 = 21 kullanılır: sifrele("OFAF", 21) → "JAVA".

6. Pascal üçgeni kodu n = 6 ile çalıştırılırsa p[5] satırı nedir? Üçgen toplam kaç hücre kullanır?

   Cevap

   Satırlar 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1; 1 5 10 10 5 1'dir. p[5] = [1, 5, 10, 10, 5, 1]. Örneğin p[5][2] = p[4][1] + p[4][2] = 4 + 6 = 10'dur. Hücre sayısı 1 + 2 + … + 6 = 21'dir; 6 × 6'lık kare matris 36 hücre kullanırdı.

7. 3 × 3 × 3'lük diziye x * 9 + y * 3 + z + 1 yazılmıştır. 20 değeri hangi hücrededir?

   Cevap

   20 − 1 = 19 = 2 · 9 + 0 · 3 + 1 olduğu için x = 2, y = 0, z = 1'dir: ucBoyutluDizi[2][0][1]. Yani 20, üçüncü katmanın ilk satırının ikinci hücresindedir.

8. a = {5, 6, 8, 9, 0} ve boyut = 4 iken ekle(a, 4, 0, 7) çağrılıyor. Kaç kaydırma yapılır ve dizi ne olur? Ardından sil(a, 5, 4) çağrılırsa ne olur?

   Cevap

   Başa ekleme dört öğenin hepsini kaydırır: k = 4, 3, 2, 1 için 4 kaydırma. Dizi {7, 5, 6, 8, 9} olur ve metot 5 döndürür. sil(a, 5, 4) son öğeyi siler: döngü koşulu 4 < 4 baştan yanlıştır, kaydırma yapılmaz. a[4] = 0 yazılır; dizi {7, 5, 6, 8, 0} olur ve metot 4 döndürür. Başa ekleme O(n), sondan silme O(1)'dir.

9. {4, 3, 2, 1} dizisi önce seçimli, sonra (aynı ilk diziyle) eklemeli sıralamayla sıralanıyor. Seçimli sıralama kaç karşılaştırma, eklemeli sıralama kaç kaydırma yapar? {1, 2, 3, 4} için cevaplar ne olur?

   Cevap

   Seçimli sıralama her girdide n(n − 1)/2 = 6 karşılaştırma yapar; iki dizide de 6'dır. Eklemeli sıralamada kaydırma sayısı ters sıralı çift sayısıdır. {4, 3, 2, 1}'de bütün çiftler ters sıralıdır: 6 kaydırma (1 + 2 + 3). {1, 2, 3, 4}'te ters sıralı çift yoktur: 0 kaydırma. Bu durumda her tur tek bir karşılaştırmayla biter ve toplam 3 karşılaştırma yapılır.

10. new int[1000][1000] ile oluşturulan matrisin veri kısmı kaç bayttır? Bu matriste bir değeri bütün hücreleri tek tek gezerek aramak en kötü durumda kaç karşılaştırma gerektirir?

    Cevap

    Veri kısmı 1.000.000 × 4 = 4.000.000 bayttır (yaklaşık 4 MB); bunun üstüne 1000 satır dizisinin ve dış dizinin başlıkları ile dış dizideki 1000 referans eklenir. Matrisin bütün hücrelerini gezen bir arama, değer yoksa 1.000.000 karşılaştırma yapar: r × c'lik matriste O(r · c).

3.10İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Kesim 3.1: dizilerde sıralama, java.util.Arrays, karakter dizileriyle basit şifreleme ve iki boyutlu dizilerle tahta oyunları gibi bu nottaki konuları Java koduyla işler.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 1.1 ve 2.1: Java'da dizilerin kullanımını, referans ile kopya ayrımını ve seçimli ile eklemeli sıralamanın karşılaştırmalı analizini açık örneklerle verir.
• J. Gosling ve öteki yazarlar, The Java Language Specification, Java SE 17 Edition, Bölüm 10: dizilerin tanımlanmasını, ilklendirilmesini, varsayılan değerleri, clone'un sığ kopya davranışını ve ArrayStoreException'ı dilin resmî tanımıyla anlatır.

3.11Kaynaklar

1. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
2. J. Gosling, B. Joy, G. Steele, G. Bracha, A. Buckley, D. Smith, G. Bierman, The Java Language Specification, Java SE 17 Edition, Oracle, 2021.
3. R. Lafore, Data Structures and Algorithms in Java, 2. baskı, Sams, 2002.
4. Oracle, Java SE 17 API Specification: java.util.Arrays ve java.lang.System belgeleri.
5. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.

İlgili sayfalar: Bölüm 3 sunumu · Çalışma soruları · Dizi simülatörü · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.