Diziler

10.1Dizi kavramı

Şimdiye kadarki programlarda her değer kendi değişkeninde duruyordu: int not1, int not2, int not3. Üç not için bu yöntem işe yarar. Kırk not için kırk değişken gerekir; bunların ortalamasını bulmak için kırk terimli bir toplama yazılır. Not sayısı kırk bire çıkarsa program değiştirilmek zorundadır. Sorunun kaynağı, değişkenlerin birbirinden bağımsız olmasıdır. Program “üçüncü not” ya da “sıradaki not” diye bir şey söyleyemez, çünkü değişken adları sayı değil, metindir.

10.1.1Dizi nedir?

Tanımdaki üç koşulun her birinin bir nedeni vardır. Aynı tip koşulu, her hücrenin aynı büyüklükte olmasını sağlar: bir int dizisinin her hücresi 4 bayt tutar. Sabit sayı koşulu, dizinin bellekte tek parça hâlinde yer almasına izin verir. Art arda hücreler ise herhangi bir öğenin yerinin tek bir hesapla bulunmasını mümkün kılar.

Java'da bir dizi bir nesnedir (object). Nesneler, belleğin heap adı verilen bölgesinde oluşturulur. Metotların yerel değişkenleri ise yığın (stack) adı verilen ayrı bir bölgede tutulur. Dizi değişkeni yığında durur, ama içinde öğeler yoktur. Değişken, heap'teki dizi nesnesinin referansını (reference), yani nesnenin bellekteki yerini gösteren bir değeri saklar. Şekillerde referans bir okla çizilir.

Şekil 10.1 bu ayrımı gösterir. Soldaki kutu değişkenin kendisidir; içinde yalnızca bir ok, yani referans vardır. Sağdaki beş hücre dizi nesnesidir. Bu ayrım ilk bakışta gereksiz bir ayrıntı gibi görünür. Oysa dizilerle ilgili en şaşırtıcı davranışların çoğu buradan çıkar. İki değişken aynı diziyi gösterebilir; bir metoda dizi verildiğinde metot asıl diziyi değiştirebilir; == işleci iki dizinin içeriğini değil, referanslarını karşılaştırır. Bu davranışların her biri ilerleyen kesimlerde örnekle işlenir.

10.1.2İndis ve adres hesabı

Dizinin öğelerine köşeli parantez içinde indis yazılarak erişilir. a[0] ilk öğe, a[1] ikinci öğedir. Beş öğeli bir dizide son öğe a[4]'tür. Genel kural şudur: uzunluğu n olan bir dizinin ilk indisi 0, son indisi n − 1'dir. Java'da dizinin uzunluğu a.length ile okunur; bu yüzden son öğe her zaman a[a.length - 1] diye yazılabilir.

İndisin 0'dan başlaması yeni başlayanlara garip gelir. Gündelik hayatta sayma 1'den başlar. Java'da, C'de ve birçok başka dilde ise indis aslında bir uzaklıktır: dizinin başından kaç hücre ileri gidileceğini söyler. İlk öğe başlangıçtadır, uzaklığı sıfırdır. a[2] ise başlangıçtan iki hücre ötededir.

Bu yorum, erişimin neden hızlı olduğunu da açıklar. Dizi bellekte art arda hücrelerden oluştuğu için i numaralı hücrenin adresi tek bir formülle hesaplanır:

adres(a[i]) = başlangıç adresi + i × hücre boyu

Hesabın uzunluğu dizinin boyuna bağlı değildir. Beş öğeli dizide de bir milyon öğeli dizide de tek bir çarpma ve tek bir toplama yapılır. Bu yüzden indisle erişimin maliyeti sabit zamandır, büyük O gösterimiyle O(1). Büyük O gösterimi bir işlemin süresinin girdi büyüdükçe nasıl arttığını özetler. O(1) “girdi ne kadar büyük olursa olsun aynı süre”, O(n) ise “süre öğe sayısıyla doğru orantılı artar” demektir. Gerçek Java programında başlangıç adresi programcıya gösterilmez ve JVM her erişimde ayrıca indisin geçerli olup olmadığını denetler. Ama hesap ilkesi aynıdır.

10.1.3Dizinin güçlü ve zayıf yanları

Dizinin yapısı ona bazı üstünlükler kazandırır, bazı sınırlar da koyar. İkisi aynı kaynaktan gelir: sabit boyutlu, art arda hücreler.

Tablodaki “öğe tipi tutarlıdır” ile “tek bir öğe tipi tutar” aynı özelliğin iki yüzüdür. Derleyici, bir int dizisine yanlışlıkla metin konmasını engeller; bu bir güvencedir. Buna karşılık bir öğrencinin adını, numarasını ve notunu aynı dizide tutmak mümkün değildir; bunun için üç ayrı dizi ya da başka bir yapı gerekir.

Şekil 10.3'ün sağ yarısı araya eklemenin neden pahalı olduğunu gösterir. {10, 20, 30, 40} dizisinde 10 ile 20 arasına 15 konacak olsun. Hücreler art arda olduğu için “araya hücre sokmak” diye bir işlem yoktur. 40 bir sağa, sonra 30 bir sağa, sonra 20 bir sağa taşınır ve boşalan 1 numaralı hücreye 15 yazılır. Kaydırılan öğe sayısı, ekleme noktasından sonraki öğe sayısı kadardır. En kötü durumda, başa eklemede, bütün öğeler kayar. Bu yüzden araya ekleme ve aradan silme O(n) maliyetlidir. Üstelik dizinin sonunda boş hücre yoksa ekleme hiç yapılamaz: uzunluk sabittir. Daha büyük yeni bir dizi oluşturulur ve eski öğeler oraya kopyalanır.

10.2Dizi bildirme ve oluşturma

Bir diziyi kullanmak iki ayrı iş gerektirir. Önce dizi değişkeni bildirilir; bu, yığında bir referans kutusu açar. Sonra dizi nesnesi oluşturulur ve referansı bu kutuya yazılır. İki iş tek satırda da yapılabilir, ayrı satırlarda da.

10.2.1Bildirim ve new

Java'da bir dizi tipi, öğe tipinin ardına köşeli parantez çifti eklenerek yazılır: int[] “int dizisi”, String[] “String dizisi”, double[] “double dizisi” demektir. Dizi nesnesi new işleciyle oluşturulur ve uzunluk köşeli parantez içinde verilir. Aşağıdaki program dört ayrı bildirimi bir arada gösterir:

public class Bildirim {
    public static void main(String[] args) {
        int[] sayilar = new int[5];
        String[] adlar = {"Ada", "Can", "Ece"};
        double[] olcumler;
        olcumler = new double[10];
        System.out.println(sayilar.length + " " + adlar.length + " " + olcumler.length);
    }
}

5 3 10

Satırları sırayla inceleyelim.

1. int[] sayilar = new int[5]; bildirim ile oluşturmayı tek satırda yapar. new int[5] heap'te beş hücreli bir int dizisi oluşturur. Atama, bu dizinin referansını sayilar değişkenine yazar.
2. String[] adlar = {"Ada", "Can", "Ece"}; diziyi değerleriyle birlikte oluşturur. Uzunluk yazılmaz; derleyici değerleri sayar ve uzunluğu 3 yapar.
3. double[] olcumler; yalnızca değişkeni bildirir. Bu noktada heap'te hiçbir dizi yoktur.
4. olcumler = new double[10]; on hücreli diziyi sonradan oluşturur ve referansını değişkene yazar.

Uzunluk bir sabit olmak zorunda değildir; çalışma sırasında hesaplanan bir int de olabilir. new int[n], n'nin o anki değeri kadar hücre açar. Uzunluk 0 olabilir; böyle bir diziye boş dizi denir ve hiç hücresi yoktur. Negatif uzunluk ise program çalışırken NegativeArraySizeException hatasına yol açar. Dizi bir kez oluşturulduktan sonra uzunluğu değiştirilemez. olcumler'e daha sonra new double[20] atanırsa eski dizi büyümez; değişken yeni, ayrı bir diziyi göstermeye başlar.

Atanmamis.java:4: error: variable sayilar might not have been initialized
        sayilar[0] = 7;
        ^
1 error

10.2.2Varsayılan değerler

new ile oluşturulan bir dizinin hücreleri boş kalmaz. Java her hücreye öğe tipinin varsayılan değerini (default value) yazar. Sayı tiplerinde bu değer sıfırdır, boolean'da false'tur. Nesne tiplerinde, örneğin String'de, varsayılan değer null'dır. null, “bu referans hiçbir nesneyi göstermiyor” anlamına gelen özel değerdir.

Aşağıdaki program Şekil 10.4'teki değerleri konsola yazar. char dizisinin varsayılan değeri de eklenmiştir:

public class Varsayilan {
    public static void main(String[] args) {
        int[] a = new int[3];
        double[] d = new double[2];
        boolean[] b = new boolean[2];
        String[] s = new String[2];
        char[] c = new char[2];
        System.out.println(a[1] + " " + d[0] + " " + b[1] + " " + s[0]);
        System.out.println((int) c[0]);
        System.out.println(a.length + d.length + s.length);
    }
}

0 0.0 false null
0
7

İlk satırda dört farklı dizinin birer hücresi yazdırılır: 0, 0.0, false ve null. char dizisinin varsayılan değeri kodu 0 olan karakterdir. Bu karakter ekranda görünmediği için (int) dönüşümüyle sayı olarak yazdırılmıştır. Son satırda bir tuzak vardır. a.length + d.length + s.length ifadesinde hiç dizgi yoktur. Bu yüzden + toplama yapar ve sonuç 3 + 2 + 2 = 7 olur.

Varsayılan değer kuralı yalnızca dizi hücreleri ve sınıf alanları için geçerlidir. Bir metodun içinde bildirilen yerel değişkenlere Java kendiliğinden değer vermez. int x; System.out.println(x); derlenmez. Buna karşılık new int[1] ile oluşturulan dizinin hücresi her zaman 0 ile başlar.

10.2.3İlklendirici

Öğelerin değerleri baştan biliniyorsa dizi, süslü parantez içinde değerler yazılarak oluşturulur. Bu yazıma ilklendirici (array initializer) denir: int[] puanlar = {70, 85, 90};. Uzunluk yazılmaz, çünkü derleyici değerleri sayar. Burada uzunluk 3'tür.

İlklendiricinin kısa biçimi yalnızca bildirim satırında kullanılabilir. Önce bildirilmiş bir değişkene sonradan bu biçimle atama yapılamaz:

public class IlkHata {
    public static void main(String[] args) {
        int[] a;
        a = {1, 2, 3};
    }
}

IlkHata.java:4: error: illegal start of expression
        a = {1, 2, 3};
            ^
IlkHata.java:4: error: not a statement
        a = {1, 2, 3};
             ^
IlkHata.java:4: error: ';' expected
        a = {1, 2, 3};
              ^
3 errors

Derleyici tek bir yanlış için üç ileti verir. Bu tür ileti yağmurunda ilk ileti esas alınır: “ifadenin geçersiz başlangıcı”. Doğru yazım, ilklendiricinin önüne dizi tipini eklemektir: a = new int[]{1, 2, 3};. Bu uzun biçim, bir metoda doğrudan dizi vermek için de kullanılır: ara(new int[]{2, 4, 6, 8}, 5).

Java dizi değişkeninin iki yazımını da kabul eder: int[] a ve int a[]. İkincisi C dilinden kalmadır. Bu notta ve sunumda birinci biçim kullanılır, çünkü tip bilgisi (int[]) tek parçada durur.

10.2.4Dizi oluşturma adım adım

Aşağıdaki program bir diziyi önce bildirir, sonra oluşturur, iki hücresine değer yazar ve iki dizinin uzunluğunu yazdırır:

public class Olustur {
    public static void main(String[] args) {
        int[] sayilar;
        sayilar = new int[4];
        sayilar[0] = 7;
        sayilar[3] = 2;
        String[] adlar = {"Ada", "Can", "Ece"};
        System.out.println(sayilar.length + " "
                           + adlar.length);
    }
}

4 3

Programın her adımında yığın ve heap'te ne olduğunu Tablo 10.2 gösterir.

Tablonun ilk satırı dikkat ister: int[] sayilar; çalıştığında heap'te hiçbir şey olmaz. Şekil 10.5 bu boşluğu ve ardından gelen değişimi gösterir. İkinci satırdaki new heap'te nesneyi açar, atama işleci de referansı değişkene yazar. Bundan sonra sayilar[0] = 7 gibi her erişim aynı yolu izler: değişkendeki ok takip edilir, heap'teki diziye gidilir, indisle hücre bulunur ve değer yazılır.

Son satırda sayilar.length ve adlar.length okunur. length bir metot değil, dizinin bir alanıdır; bu yüzden parantezsiz yazılır. String sınıfında ise uzunluk length() metoduyla alınır. Bu fark sık karıştırılır: dizide a.length(), dizgide s.length yazmak derleme hatasıdır. length alanı yalnızca okunur; sayilar.length = 10; da derlenmez.

10.3Öğelere erişim

10.3.1Okuma ve yazma

Bir dizi öğesi, sıradan bir değişken gibi kullanılır. puanlar[1] bir ifadenin içinde geçerse hücredeki değer okunur. Atamanın solunda geçerse hücrenin kendisi kastedilir ve oraya yeni değer yazılır. Köşeli parantezin içine sabit bir sayı yazmak şart değildir; int değer veren her ifade indis olabilir: a[i], a[i + 1], a[a.length - 1].

public class Okuma {
    public static void main(String[] args) {
        int[] puanlar = {70, 85, 90};
        int ilk = puanlar[0];
        puanlar[1] = 88;
        int son = puanlar[puanlar.length - 1];
        System.out.println(ilk + " " + son);
    }
}

70 90

4. satırdaki puanlar[puanlar.length - 1] yazımı, son öğeyi okumanın genel yoludur. Önce iç ifade hesaplanır: 3 − 1 = 2. Sonra puanlar[2] okunur. Dizi beş öğeli olsaydı aynı satır hiç değişmeden puanlar[4]'ü okurdu. Son indisi elle yazmak (puanlar[2]) ise dizi büyüdüğünde sessizce yanlış öğeyi verir.

Şekil 10.6 önemli bir ayrıntıyı da gösterir: int ilk = puanlar[0]; diziden değeri kopyalar. Bu satırdan sonra puanlar[0] değişse bile ilk 70 kalır. Temel tiplerde (int, double, boolean, char) atama her zaman değeri kopyalar.

10.3.2Sınır dışı hatası

Geçerli indisler 0 ile length − 1 arasındaki tam sayılardır. Negatif bir indis ya da length'in kendisi geçersizdir. Geçersiz indisle erişim, Java'da programı ArrayIndexOutOfBoundsException ile durdurur. Bu bir istisnadır (exception): program çalışırken ortaya çıkan ve olağan akışı kesen bir hata durumu.

Derleyici bu hatayı genellikle yakalayamaz, çünkü indis çoğu zaman program çalışırken hesaplanır. Aşağıdaki program kusursuz derlenir:

public class Negatif {
    public static void main(String[] args) {
        int[] a = {4, 8, 6};
        System.out.println(a[-1]);
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3
	at Negatif.main(Negatif.java:4)

İleti üç bilgi verir. Hatanın türü ArrayIndexOutOfBoundsException'dır. Ayrıntı kısmı “Index -1 out of bounds for length 3” der, yani “indis −1, uzunluğu 3 olan dizinin sınırları dışında”. Son satır da hatanın yerini gösterir: Negatif.java dosyasının 4. satırı. Bu denetim C gibi dillerde yoktur; orada sınır dışı yazma, belleğin başka bir değişkene ait bölümünü sessizce bozabilir. Java'nın denetimi bir maliyet getirir, ama hatayı tam yerinde yakalar.

10.3.3Bir tur fazla: adım adım

Sınır dışı hatasının en yaygın kaynağı, döngü koşulunda < yerine <= yazmaktır. Hataya bir tur fazla (ya da bir eksik) hatası denir:

public class Sinir {
    public static void main(String[] args) {
        int[] a = {4, 8, 6};
        for (int i = 0; i <= a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

> java Sinir
4
8
6
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
	at Sinir.main(Sinir.java:5)

İlk üç tur sorunsuzdur ve 4, 8, 6 yazılır. Dördüncü turda i 3 olur. Koşul 3 <= 3 doğrudur, gövdeye girilir ve a[3] okunmaya çalışılır (Şekil 10.8). Program bu noktada durur. Dikkat edilirse hata, önceki çıktıları silmez: 4, 8 ve 6 konsolda kalır. Bu yüzden hatalı bir program “neredeyse doğru” görünebilir.

Çözüm, koşulu i < a.length yapmaktır. O zaman i 3 olduğunda 3 < 3 yanlıştır ve döngü gövdeye girmeden biter. Akılda tutulacak kural kısadır: indis 0'dan başlıyorsa koşul < length olur. <= length - 1 da doğrudur, ama daha uzun ve hataya açıktır.

10.4Döngülerle gezinme

Dizinin asıl gücü döngüyle birleştiğinde ortaya çıkar. İndis bir değişken olabildiği için tek bir döngü, dizinin bütün öğelerine sırayla uğrayabilir. Dizinin her öğesini bir kez ziyaret etmeye gezinme (traversal) denir. Java'da gezinmenin iki yolu vardır: klasik for ve gelişmiş for.

10.4.1Klasik for

Klasik for döngüsünde bir sayaç, genellikle i, 0'dan başlar ve her turda 1 artar. Koşul i < dizi.length olduğu için sayaç tam olarak geçerli indisleri dolaşır:

public class Klasik {
    public static void main(String[] args) {
        int[] puanlar = {70, 88, 90};
        for (int i = 0; i < puanlar.length; i++) {
          System.out.printf("%d: %d%n", i, puanlar[i]);
        }
    }
}

0: 70
1: 88
2: 90

printf biçimli yazdırma yapar: kalıptaki ilk %d yerine i, ikinci %d yerine puanlar[i] yazılır, %n de satırı bitirir. Döngünün izlemesi Tablo 10.5'te verilmiştir.

Son satır önemlidir: i 3 olduğunda koşul yanlıştır ve puanlar[3]'e hiç erişilmez. Koşul her turun başında, gövdeden önce sınanır. Bu yüzden i'nin geçersiz bir değere ulaşması sorun değildir; sorun, geçersiz değerle gövdeye girmektir.

Klasik for'un yapısı serbesttir. Başlangıç, koşul ve adım değiştirilerek dizi farklı biçimlerde gezilebilir. for (int i = a.length - 1; i >= 0; i--) diziyi sondan başa doğru gezer. i += 2 adımı bir öğe atlayarak ilerler. Bu esneklik indisi doğrudan kontrol etmekten gelir.

10.4.2Gelişmiş for

Pek çok gezinmede indisin kendisine ihtiyaç yoktur; yalnızca öğelerin değerleri gerekir. Bu durumlar için Java'nın daha kısa bir döngüsü vardır.

Yazım “dizideki her x için” diye okunur. İki noktanın solunda öğe tipiyle bir değişken, sağında dizi bulunur. Tanımdaki “kopya” sözcüğü aşağıdaki programın davranışını açıklar:

public class Gelismis {
    public static void main(String[] args) {
        int[] puanlar = {70, 88, 90};
        for (int puan : puanlar) {
            puan = puan + 5;
            System.out.println(puan);
        }
        System.out.println(puanlar[0]);
    }
}

75
93
95
70

Her turda puan beş artırılıp yazdırılır: 75, 93, 95. Son satır ise 70 yazar. Dizi hiç değişmemiştir. Şekil 10.9 nedenini gösterir: puan, hücrenin kendisi değil, ayrı bir değişkendir. Hücredeki değer her turun başında oraya kopyalanır. Kopyaya yapılan atama diziye geri yazılmaz. Döngü bittiğinde puan değişkeni de kapsam dışına çıkar.

Diziyi gerçekten değiştirmek için hücreye indisle yazmak gerekir. Bu da klasik for ister:

import java.util.Arrays;

public class Artir {
    public static void main(String[] args) {
        int[] puanlar = {70, 88, 90};
        for (int i = 0; i < puanlar.length; i++) {
            puanlar[i] = puanlar[i] + 5;
        }
        System.out.println(Arrays.toString(puanlar));
    }
}

[75, 93, 95]

Bu programda atamanın solunda puanlar[i] vardır; değer doğrudan hücreye yazılır. Arrays.toString dizinin bütün öğelerini köşeli parantez içinde yazdırır. Bu metot java.util.Arrays sınıfındadır ve programın başında import edilir.

10.4.3Hangi döngü ne zaman?

İki döngü birbirinin yerine her zaman kullanılamaz. Seçimi, işin indise ihtiyaç duyup duymadığı belirler.

Gelişmiş for kısa olduğu kadar güvenlidir de: indis olmadığı için sınır dışı hatası yapılamaz. Bu yüzden yalnızca okuma yapılan gezinmelerde tercih edilir. İndis gerektiğinde klasik for'a geçilir.

10.5Temel dizi işlemleri

Bu kesimdeki işlemler, dizilerle yazılan programların büyük bölümünün yapı taşlarıdır. Her birinde aynı soru sorulur: diziyi kaç kez gezmek gerekir ve gezerken hangi bilgi saklanmalıdır? Örneklerin hepsi O(n) zamanda çalışır, çünkü her öğeye sabit sayıda bakılır.

10.5.1Toplam ve ortalama

Toplam bulmak için bir biriktirici değişken kullanılır. Biriktirici, toplamanın etkisiz elemanı olan 0 ile başlar ve her öğe ona eklenir:

public class Toplam {
    public static void main(String[] args) {
        int[] sayilar = {4, 7, 2, 6};
        int toplam = 0;
        for (int deger : sayilar) toplam += deger;
        double ortalama = 0;
        if (sayilar.length > 0)
            ortalama = (double) toplam / sayilar.length;
        System.out.println(toplam + " " + ortalama);
        System.out.println(toplam / sayilar.length);
    }
}

19 4.75
4

Ortalamada iki ayrıntı vardır. Birincisi (double) dönüşümüdür. toplam ve sayilar.length ikisi de int'tir; iki int'in bölümü tam sayı bölmesidir ve kesir kısmı atılır. Programın son satırı bunu gösterir: toplam / sayilar.length 4 verir. Dönüşüm, bölmeden önce toplam'ı double'a çevirir; bölme de ondalıklı yapılır ve 4.75 bulunur. İkincisi if (sayilar.length > 0) denetimidir. Boş dizide uzunluk 0'dır. Ondalıklı bölmede 0.0 / 0 hata vermez ama NaN (Not a Number, sayı değil) üretir. Denetim bu durumda ortalamayı güvenli bir başlangıç değeri olan 0.0'da bırakır.

Maliyet: döngü her öğe için bir toplama yapar; n öğe için n toplama, yani O(n) zaman. Ek bellek olarak yalnızca iki değişken kullanılır; bu da O(1) ek alan demektir.

10.5.2En küçük ve en büyük

En küçük ve en büyük öğeyi bulmak için iki aday değişken tutulur. Her öğe adayla karşılaştırılır; aday geçilirse yerini öğe alır. Adayların başlangıç değeri bu yöntemin en kritik noktasıdır:

public class MinMax {
    public static void main(String[] args) {
        int[] sayilar = {5, 3, 9, 1};
        int min = sayilar[0], max = sayilar[0];
        for (int deger : sayilar) {
            if (deger < min) min = deger;
            if (deger > max) max = deger;
        }
        System.out.println(min + " " + max);
    }
}

1 9

Adaylar dizinin ilk öğesiyle başlatılır. Aday her zaman dizide gerçekten bulunan bir değerdir; bu yüzden sonuç da dizinin bir öğesi olur. Adayı 0 ile başlatmak cazip görünür ama yanlıştır. Bütün öğeleri pozitif olan bir dizide min hiç güncellenmez ve dizide olmayan 0 bulunur. Bütün öğeleri negatif bir dizide aynı sorun max'ta çıkar.

Programda dikkat çeken bir başka nokta: döngü ilk öğeyi de inceler, oysa adaylar zaten o öğeyle başlamıştır. İlk turdaki karşılaştırmalar (5 < 5, 5 > 5) yanlış çıkar ve zarar vermez. İsteyen döngüyü i = 1'den başlayan klasik for ile yazabilir; sonuç değişmez.

0
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
	at BosDizi.main(BosDizi.java:5)

10.5.3Diziyi ters çevirme

Bir diziyi ters çevirmenin kolay yolu, yeni bir dizi açıp öğeleri sondan başa doğru oraya kopyalamaktır. Bu yol n hücrelik ek bellek ister. Daha tutumlu yol, diziyi yerinde (in place) çevirmektir: iki uçtaki öğeler yer değiştirir, sonra uçlar birer adım içeri kayar. Bu yöntemde iki indis kullanıldığı için yönteme iki işaretçi (two pointers) yöntemi denir.

import java.util.Arrays;

public class Ters {
    public static void main(String[] args) {
        int[] dizi = {1, 2, 3, 4, 5};
        int sol = 0, sag = dizi.length - 1;
        while (sol < sag) {
            int gecici = dizi[sol];
            dizi[sol] = dizi[sag];
            dizi[sag] = gecici;
            sol++;
            sag--;
        }
        System.out.println(Arrays.toString(dizi));
    }
}

[5, 4, 3, 2, 1]

Takas işlemi üç atamayla yapılır. dizi[sol] = dizi[sag] doğrudan yazılırsa soldaki değer kaybolur; bu yüzden önce gecici değişkeninde saklanır. Ardından sağdaki değer sola, saklanan değer sağa yazılır.

Beş öğeli dizide iki takas yapılır. Üçüncü turda iki işaretçi de 2'yi gösterir; ortadaki öğenin yerini değiştirmeye gerek yoktur ve 2 < 2 yanlış olduğu için döngü biter. Genel olarak n öğeli bir dizide ⌊n/2⌋ takas yapılır; bu da O(n) zamandır. Ek bellek yalnızca üç değişkendir: O(1).

10.5.4Ortalamanın üstündekileri sayma

Bazı sorular tek geçişte cevaplanamaz. “Kaç öğrencinin notu ortalamanın üstünde?” sorusu bunlardan biridir. Bir notun ortalamanın üstünde olup olmadığını bilmek için önce ortalama gerekir. Ortalama ise ancak bütün notlar okunduktan sonra bulunur. Bu yüzden dizi iki kez gezilir. Dizinin değerli bir yanı da budur: veriyi saklar ve ikinci kez okumaya izin verir.

public class Ustte {
    public static void main(String[] args) {
        int[] notlar = {60, 75, 90, 45, 80};
        int toplam = 0;
        for (int x : notlar) toplam += x;
        double ort = (double) toplam / notlar.length;
        int ustte = 0;
        for (int x : notlar)
          if (x > ort) ustte++;
        System.out.println(ort + " " + ustte);
    }
}

70.0 3

Birinci geçişin sonunda toplam 350'dir ve ortalama 350 / 5 = 70.0 bulunur. İkinci geçişte her not 70.0 ile karşılaştırılır; 75, 90 ve 80 üstündedir. Program 70.0 3 yazar. İki geçişin toplam maliyeti 2n karşılaştırma ve toplamadır. Büyük O gösteriminde sabit çarpanlar yazılmaz; maliyet yine O(n)'dir.

10.5.5En büyük ikinci öğe

Dizideki en büyük ikinci öğe için diziyi sıralamak gerekmez. Tek geçişte iki aday tutulur: enBuyuk ve ikinci. Tekrarlanan değerler soruyu inceltir: {7, 12, 5, 12, 9} dizisinde en büyük 12'dir ve iki kez geçer; en büyük ikinci öğe ise 9'dur.

public class Ikinci {
    public static void main(String[] args) {
        int[] a = {7, 12, 5, 12, 9};
        int enBuyuk = Integer.MIN_VALUE;
        int ikinci = Integer.MIN_VALUE;
        for (int x : a) {
          if (x > enBuyuk) {
            ikinci = enBuyuk;
            enBuyuk = x;
          } else if (x > ikinci && x != enBuyuk) {
            ikinci = x;
          }
        }
        System.out.println(ikinci);
        System.out.println(Integer.MIN_VALUE);
    }
}

9
-2147483648

İki aday da Integer.MIN_VALUE ile başlar. Bu sabit int tipinin alabileceği en küçük değerdir, yani −2147483648; programın ikinci çıktı satırı onu gösterir. Böylece dizinin ilk öğesi, ne olursa olsun, adaylardan büyük çıkar. Her öğe için iki durum vardır:

1. x > enBuyuk ise yeni bir en büyük bulunmuştur. Eski en büyük boşa gitmez, ikinciliğe iner: önce ikinci = enBuyuk, sonra enBuyuk = x. Sıra ters olursa eski değer kaybolur.
2. Değilse ve x hem ikinci'den büyük hem de en büyükten farklıysa, x yeni ikincidir. x != enBuyuk koşulu, en büyüğün tekrarının ikinci sayılmasını engeller.

Dizi tek kez gezilir: O(n) zaman, O(1) ek alan. Dizide yalnızca tek bir farklı değer varsa, örneğin {4, 4}, ikinci hiç güncellenmez ve Integer.MIN_VALUE kalır. Gerçek bir programda bu durum “ikinci en büyük yok” diye ayrıca bildirilmelidir.

10.5.6Frekans sayma: zar histogramı

Bir zarın altı yüzünden her birinin kaç kez geldiğini saymak için altı sayaç gerekir. Altı ayrı değişken ve uzun bir if-else zinciri yerine tek bir sayaç dizisi kullanılır. Yöntemin püf noktası, değeri indis olarak kullanmaktır: zar 3 geldiyse sayac[3] bir artırılır.

public class Histogram {
    public static void main(String[] args) {
        int[] atislar = {3, 6, 3, 1, 6, 3};
        int[] sayac = new int[7];
        for (int zar : atislar)
          sayac[zar]++;
        for (int y = 1; y <= 6; y++) {
          System.out.print(y + ": ");
          for (int k = 0; k < sayac[y]; k++)
            System.out.print("*");
          System.out.println();
        }
    }
}

1: *
2: 
3: ***
4: 
5: 
6: **

Sayaç dizisi 7 hücrelidir, çünkü zar değerleri 1 ile 6 arasındadır ve 6 numaralı hücreye ihtiyaç vardır. 0 numaralı hücre hiç kullanılmaz. Bir hücre boşa gider, ama karşılığında sayac[zar] yazımı doğrudan okunur. Atışlar örnekte sabit verilmiştir; gerçek bir programda rastgele.nextInt(6) + 1 ile üretilir.

İlk döngü atışları sayar. sayac[zar]++ tek bir deyimdir: önce zar'ın değeri okunur, o numaralı hücre bulunur ve hücredeki değer bir artırılır. Altı atıştan sonra sayaç dizisi [0, 1, 0, 3, 0, 0, 2] olur. İkinci döngü her yüz için bir satır yazar; iç döngü o satıra sayaç kadar yıldız koyar. 2, 4 ve 5 hiç gelmediği için o satırlarda yıldız yoktur.

Sayma döngüsü her atış için tek bir artırma yapar; m atış için O(m) zaman. if-else zinciri kullanılsaydı her atış için altıya kadar karşılaştırma gerekirdi. Aynı yöntem harflerin ya da sınav notlarının frekansını bulmakta da kullanılır; tek koşul, değerlerin küçük ve negatif olmayan tam sayılara karşılık gelmesidir.

10.5.7Eratosthenes eleği

Belirli bir sayıya kadar bütün asal sayıları bulmanın eski ve hızlı bir yolu, Eratosthenes eleğidir. Yöntem asal sayıları aramaz; asal olmayanları eler. 2'den başlanır. Elenmemiş her sayı asaldır ve onun katları elenir. Elenmiş sayıların yerini tutmak için bir boolean dizisi kullanılır: asalDegil[k] true ise k elenmiştir.

public class Elek {
    public static void main(String[] args) {
        int n = 20;
        boolean[] asalDegil = new boolean[n + 1];
        for (int i = 2; i * i <= n; i++)
          if (!asalDegil[i])
            for (int k = i * i; k <= n; k += i)
              asalDegil[k] = true;
        for (int i = 2; i <= n; i++)
          if (!asalDegil[i]) System.out.print(i + " ");
        System.out.println();
    }
}

2 3 5 7 11 13 17 19 

Dizi n + 1 hücrelidir, çünkü indis olarak 20 de kullanılır. Başlangıçta bütün hücreler false'tur; bu, boolean dizisinin varsayılan değeridir ve “henüz elenmedi” anlamına gelir. İç döngü katları işaretler. Elemenin adımları JDK 21 ile ayrıca izlenmiş, her i için işaretlenen hücreler Tablo 10.13'te verilmiştir.

Yöntemde iki hızlandırma vardır. Birincisi, katlar i * i'den başlar. 3'ün 6 gibi daha küçük katları, daha küçük bir asalın (2'nin) katı olarak zaten elenmiştir. İkincisi, dış döngü i * i <= n koşuluyla durur. 20'ye kadar asal olmayan her sayının √20 ≈ 4,47'den küçük ya da ona eşit bir böleni vardır. Bu yüzden 5 ve sonrası için eleme yapmaya gerek kalmaz. Aynı program n = 100 ile çalıştırılınca 25 asal bulur.

Elek, bir dizinin hem veri hem de “işaret tahtası” olarak kullanılabildiğini gösterir. Her sayının asal olup olmadığını bölme deneyerek sınamak, büyük n'ler için elekten çok daha yavaştır. Eleğin zaman maliyeti O(n log log n)'dir; pratikte n'ye çok yakın büyür. Bedeli ise n + 1 hücrelik bir boolean dizisidir.

10.6Kopyalama, Arrays sınıfı ve metotlar

Dizi değişkeninin bir referans tuttuğu, en çok kopyalamada önem kazanır. Temel tipte int y = x; değeri kopyalar ve iki değişken birbirinden bağımsız olur. Dizilerde aynı yazım bambaşka bir sonuç verir.

10.6.1Referans kopyası ve öğe kopyası

int[] b = a; deyimi yeni bir dizi oluşturmaz. a'daki referans b'ye kopyalanır; artık iki değişken aynı nesneyi gösterir. Bu duruma referans kopyası denir. Birinin üzerinden yapılan değişiklik ötekinden de görülür, çünkü ortada tek bir dizi vardır.

Bağımsız bir kopya için dizinin öğeleri yeni bir diziye aktarılmalıdır. Java bunun için üç hazır yol sunar:

• a.clone(): aynı uzunlukta yeni bir dizi oluşturur ve bütün öğeleri kopyalar.
• Arrays.copyOf(a, a.length): aynı işi yapar; ikinci argümanla yeni dizinin uzunluğu da seçilebilir.
• System.arraycopy(kaynak, kBas, hedef, hBas, adet): var olan bir hedef diziye, belirli bir konumdan başlayarak belirli sayıda öğe kopyalar.

Üçüncü yol en esnek olanıdır, ama hedef dizinin önceden oluşturulmuş olmasını ister:

import java.util.Arrays;

public class ArrayCopy {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        int[] d = new int[7];
        System.arraycopy(a, 1, d, 2, 3);
        System.out.println(Arrays.toString(d));
    }
}

[0, 0, 2, 3, 4, 0, 0]

System.arraycopy(a, 1, d, 2, 3) çağrısı “a'nın 1 numaralı hücresinden başlayarak 3 öğeyi, d'nin 2 numaralı hücresinden başlayarak yaz” demektir. Kopyalanan öğeler 2, 3 ve 4'tür; d'nin 2, 3 ve 4 numaralı hücrelerine yazılırlar. Kalan hücreler varsayılan değer olan 0'da kalır.

clone, Arrays.copyOf ve System.arraycopy sığ kopya yapar. int dizilerinde bu bir sorun yaratmaz, çünkü hücrelerde sayıların kendisi durur. Nesne dizilerinde ve iki boyutlu dizilerde ise nesneler kopyalanmaz, paylaşılır. Bu tuzak iki boyutlu dizilerle birlikte ayrıca işlenir.

10.6.2Kopyalama adım adım

Aşağıdaki program iki kopya türünü yan yana gösterir. Son satır, iki referansı == ile karşılaştırır:

public class Kopya {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = a;
        b[0] = 99;
        System.out.println(a[0]);
        int[] c = a.clone();
        c[1] = 50;
        System.out.println(a[1] + " " + c[1]);
        System.out.println((a == b) + " " + (a == c));
    }
}

99
2 50
true false

b[0] = 99 satırı yalnızca b'yi değiştiriyor gibi görünür. Oysa b'nin gösterdiği nesne a'nın da nesnesidir ve a[0] 99 olur. clone çağrısı ise o anki içeriği yeni bir nesneye kopyalar. Bundan sonra c üzerindeki değişiklik a'yı etkilemez. Son satırdaki true false çıktısı iki ilişkiyi özetler. a == b doğrudur, çünkü iki değişken aynı referansı tutar. a == c yanlıştır; içerikleri aynı olsa da bunlar farklı nesnelerdir.

10.6.3Arrays yardımcıları

java.util.Arrays sınıfı, dizilerle sık yapılan işler için hazır metotlar içerir. Bu metotlar static'tir ve sınıf adıyla çağrılır: Arrays.toString(a). Programın başına import java.util.Arrays; satırı eklenir. Aşağıdaki program sunumdaki tablonun her satırını JDK 21 ile çalıştırır:

import java.util.Arrays;

public class Yardimci {
    public static void main(String[] args) {
        int[] a = {5, 2, 9}, r = {10, 20, 30, 40, 50}, p = {1, 2, 3}, q = {1, 2, 3}, f = new int[4];
        int[][] m = {{1, 2}, {3, 4}};
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.deepToString(m));
        System.out.println(Arrays.toString(m).startsWith("[[I@"));
        Arrays.fill(f, 7);
        System.out.println(Arrays.toString(f));
        System.out.println((p == q) + " / " + p.equals(q));
        System.out.println(Arrays.equals(p, q));
        System.out.println(Arrays.toString(Arrays.copyOf(a, 5)));
        System.out.println(Arrays.toString(Arrays.copyOf(a, 2)));
        System.out.println(Arrays.toString(Arrays.copyOfRange(r, 1, 4)));
        System.out.println(a);
    }
}

[5, 2, 9]
[[1, 2], [3, 4]]
true
[7, 7, 7, 7]
false / false
true
[5, 2, 9, 0, 0]
[5, 2]
[20, 30, 40]
[I@548c4f57

Programın son satırı, diziyi doğrudan println ile yazdırmanın sonucunu gösterir: [I@ ile başlayan bir metin. Baştaki [I “int dizisi” demektir. @ işaretinden sonraki onaltılık sayı nesneye ait bir koddur ve her çalıştırmada değişebilir. Bu çıktı öğeler hakkında hiçbir bilgi vermez. İki boyutlu bir diziye Arrays.toString uygulandığında da aynı şey olur: dış dizinin hücreleri satır dizilerinin referanslarıdır ve her biri [I@… biçiminde yazılır. Program bu satırda yalnızca metnin [[I@ ile başladığını sınar ve true yazar; kodun kendisi çalıştırmadan çalıştırmaya değiştiği için gösterilmemiştir.

equals konusu ayrıca dikkat ister. String'de equals içeriği karşılaştırır. Dizilerde ise p.equals(q), p == q ile aynı işi yapar ve yalnızca referansa bakar. İçeriği karşılaştırmak için Arrays.equals(p, q), iki boyutlu dizilerde Arrays.deepEquals kullanılır.

copyOfRange'teki aralık, Java'nın genel bir alışkanlığını izler: başlangıç indisi dahil, bitiş indisi hariçtir. copyOfRange(r, 1, 4) 1, 2 ve 3 numaralı öğeleri alır; kopyanın uzunluğu 4 − 1 = 3'tür. Aynı kural String sınıfının substring metodunda da geçerlidir.

10.6.4Diziler ve metotlar

Bir metot dizi alabilir ve dizi döndürebilir. Java'da metoda verilen her argüman kopyalanarak aktarılır. Dizi argümanında kopyalanan şey referanstır, dizinin kendisi değil. Bu yüzden metottaki parametre, çağıran taraftaki diziyle aynı nesneyi gösterir. Sonuç iki kurala bağlanır:

1. Metot parametre üzerinden hücrelere yazarsa, değişiklik çağıranın dizisinde de görülür.
2. Metot parametreye yeni bir dizi atarsa, yalnızca kendi yerel kopyasındaki referans değişir; çağıranın değişkeni etkilenmez.

import java.util.Arrays;

public class Metot {
    static void ikiKatinaCikar(int[] dizi) {
        for (int i = 0; i < dizi.length; i++)
            dizi[i] = dizi[i] * 2;
    }

    static void yeniDiziAta(int[] dizi) {
        dizi = new int[]{0, 0, 0};
    }

    static int[] kareler(int n) {
        int[] sonuc = new int[n];
        for (int i = 0; i < n; i++)
            sonuc[i] = (i + 1) * (i + 1);
        return sonuc;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        ikiKatinaCikar(a);
        System.out.println(Arrays.toString(a));
        yeniDiziAta(a);
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(kareler(4)));
    }
}

[2, 4, 6]
[2, 4, 6]
[1, 4, 9, 16]

ikiKatinaCikar(a) çağrısında dizi parametresi a'nın nesnesini gösterir ve hücrelere yazar; a [2, 4, 6] olur. yeniDiziAta(a) ise dizi'ye yeni bir nesne bağlar. Bu atama yalnızca metodun kendi değişkenini etkiler; a eski nesneyi göstermeyi sürdürür ve [2, 4, 6] kalır. kareler(4) metodu yeni bir dizi oluşturup referansını döndürür. Metot bittiğinde yerel sonuc değişkeni ortadan kalkar, ama heap'teki dizi yaşamaya devam eder, çünkü referansı çağırana verilmiştir.

Bu davranışın bir yan etkisi vardır. Diziyi sıralayan, ters çeviren ya da dolduran bir metot, çağıranın verisini kalıcı olarak değiştirir. Özgün sıranın korunması gerekiyorsa metot önce bir kopya almalıdır. Sıralama ve ortanca örneklerinde bu kural yeniden karşımıza çıkar. Bu arada main metodunun parametresi de bir dizidir: String[] args, komut satırından verilen argümanları tutar ve args.length argüman sayısını verir.

10.7Arama ve sıralama

Doğrusal arama, ikili arama, kabarcık sıralaması ve eklemeli sıralama algoritmalarının fikri, sözde kodu ve ayrıntılı izlemeleri Algoritmalar ders notunda anlatılmıştır. Bu kesim aynı algoritmaların Java dizileriyle yazımına, kısa izlemelerine ve dizilere özgü noktalara odaklanır: indis sınırları, yerinde değişiklik, Arrays sınıfının hazır metotları.

10.7.1Doğrusal arama

Doğrusal arama diziyi baştan sona gezer ve her öğeyi hedefle karşılaştırır. İlk eşleşmede indisi döndürür; hedef yoksa −1 döndürür. −1 geçerli bir indis olamayacağı için “bulunamadı” anlamında kullanılır.

public class Dogrusal {
    static int ara(int[] dizi, int hedef) {
        for (int i = 0; i < dizi.length; i++)
            if (dizi[i] == hedef) return i;
        return -1;
    }

    public static void main(String[] args) {
        int[] d = {8, 3, 6, 2};
        System.out.println(ara(d, 6));
        System.out.println(ara(d, 5));
    }
}

2
-1

Java yazımında iki nokta göze çarpar. Birincisi, return i döngünün içindedir; metot ilk eşleşmede biter ve kalan öğelere bakılmaz. return -1 ise döngünün dışındadır ve ancak bütün öğeler denendikten sonra çalışır. Bu satırı yanlışlıkla döngünün içine, bir else koluna koymak, aramayı ilk öğede bitirir. İkincisi, dizi parametresi d ile aynı diziyi gösterir; çağrı sırasında hiçbir öğe kopyalanmaz. 5 dizide olmadığı için ikinci çağrı dört karşılaştırmadan sonra −1 döndürür. En kötü durumda n karşılaştırma yapılır: O(n).

10.7.2Arrays.sort ve Arrays.binarySearch

Java, sıralama ve ikili arama için hazır metotlar sunar. Arrays.sort(a) diziyi küçükten büyüğe sıralar. Arrays.binarySearch(a, x) sıralı bir dizide x'i ikili aramayla arar.

import java.util.Arrays;

public class Sirala {
    public static void main(String[] args) {
        int[] a = {5, 2, 9, 1, 7};
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.binarySearch(a, 7));
        System.out.println(Arrays.binarySearch(a, 6));
    }
}

[1, 2, 5, 7, 9]
3
-4

Arrays.sort yeni bir dizi döndürmez; dizinin kendisini yerinde değiştirir (Şekil 10.15). Özgün sıra kaybolur. Özgün sıra başka bir iş için gerekiyorsa önce kopya alınır ve kopya sıralanır.

Arrays.binarySearch hedefi bulursa indisini döndürür. Bulamazsa negatif bir değer döndürür: -(eklenme noktası) - 1. Eklenme noktası, hedefin sıralı dizide gireceği konumdur. Sıralı [1, 2, 5, 7, 9] dizisinde 6, 5 ile 7 arasına, yani 3 numaralı konuma girerdi. Dönüş değeri −3 − 1 = −4'tür. Formüldeki “− 1”, eklenme noktası 0 olduğunda bile sonucun negatif çıkmasını sağlar; −0 ile 0 ayırt edilemezdi.

Her iki metot da java.util.Arrays sınıfındadır ve import java.util.Arrays; gerektirir. Temel tipteki diziler için Arrays.sort, ortalama O(n log n) zamanda çalışan bir hızlı sıralama türü kullanır. Bu, kabarcık ve eklemeli sıralamanın O(n²) maliyetinden büyük dizilerde çok daha iyidir.

10.7.3Ortanca

Ortancanın ortalamadan üstün bir yanı, uç değerlerden etkilenmemesidir. {1, 2, 3, 4, 100} dizisinin ortalaması 110 / 5 = 22.0'dır; bu değer öğelerin hiçbirine yakın değildir. Ortanca ise 3'tür. Gelir, ev fiyatı ya da yanıt süresi gibi verilerde birkaç aşırı değer bulunur; bu yüzden ortanca daha anlamlı bir “tipik değer” verir.

import java.util.Arrays;

public class Medyan {
    public static void main(String[] args) {
        int[] a = {7, 3, 9, 1, 5};
        int[] s = Arrays.copyOf(a, a.length);
        Arrays.sort(s);    // a bozulmaz
        int n = s.length;
        double m = (n % 2 == 1) ? s[n / 2]
            : (s[n/2 - 1] + s[n/2]) / 2.0;
        System.out.println(m);   // 5.0
        System.out.println(Arrays.toString(a) + " " + Arrays.toString(s));
    }
}

5.0
[7, 3, 9, 1, 5] [1, 3, 5, 7, 9]

Programda üç dizilere özgü nokta vardır. Birincisi, sıralama kopya üzerinde yapılır: Arrays.copyOf ile s oluşturulur ve a'nın özgün sırası korunur. Programın ikinci satırı bunu doğrular: a hâlâ [7, 3, 9, 1, 5]'tir. İkincisi, koşullu işleç (? :) tek ve çift durumu tek ifadede birleştirir. Üçüncüsü, çift durumda 2.0 ile bölünür. 2 ile bölünseydi iki int'in bölümü alınırdı ve (3 + 6) / 2 sonucu 4.5 yerine 4 çıkardı. Aşağıdaki program bu farkı ve uç değer örneğini JDK 21 ile doğrular:

import java.util.Arrays;

public class Medyan2 {
    static double ortanca(int[] a) {
        int[] s = Arrays.copyOf(a, a.length);
        Arrays.sort(s);
        int n = s.length;
        return (n % 2 == 1) ? s[n / 2] : (s[n/2 - 1] + s[n/2]) / 2.0;
    }

    public static void main(String[] args) {
        int[] u = {1, 2, 3, 4, 100};
        int t = 0;
        for (int x : u) t += x;
        System.out.println((double) t / u.length + " " + ortanca(u));
        System.out.println(ortanca(new int[]{8, 2, 6, 3}));
        System.out.println((3 + 6) / 2);
    }
}

22.0 3.0
4.5
4

Maliyeti sıralama belirler: O(n log n). Kopya için n hücrelik ek bellek gerekir. Sıralama yapmadan ortancayı ortalama O(n) zamanda bulan yöntemler de vardır, ama bu dersin kapsamı dışındadır.

10.7.4Kabarcık sıralaması

Kabarcık sıralaması komşu öğeleri karşılaştırır ve sırası bozuk olanları takas eder. Her geçişte kalan öğelerin en büyüğü, suyun yüzüne çıkan bir kabarcık gibi sona yerleşir. Java yazımı iki iç içe for döngüsüdür:

import java.util.Arrays;

public class Kabarcik {
    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2};
        int n = a.length;
        for (int gecis = 0; gecis < n - 1; gecis++) {
          for (int j = 0; j < n - 1 - gecis; j++) {
            if (a[j] > a[j + 1]) {
              int gecici = a[j];
              a[j] = a[j + 1];
              a[j + 1] = gecici;
            }
          }
        }
        System.out.println(Arrays.toString(a));
    }
}

[1, 2, 4, 5]

Dış döngü geçişleri sayar: n öğe için n − 1 geçiş yeterlidir, çünkü n − 1 öğe yerine oturunca sonuncusu da kendiliğinden yerindedir. İç döngünün sınırı j < n - 1 - gecis'tir. Bu sınırda iki dizilere özgü ayrıntı vardır. Birincisi “- 1”dir: gövde a[j + 1]'e eriştiği için j en çok n − 2 olabilir. Sınır j < n olsaydı son turda a[n] okunur ve sınır dışı hatası alınırdı. İkincisi “- gecis”tir: her geçiş sondaki bir öğeyi yerine oturttuğu için o bölgeye yeniden bakmaya gerek yoktur.

Toplam karşılaştırma sayısı 3 + 2 + 1 = 6'dır. Genel olarak n öğe için (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 karşılaştırma yapılır; bu O(n²) demektir. Üçüncü geçişte hiç takas olmaz, çünkü dizi ikinci geçişten sonra sıralanmıştır. Bu gözlem bir iyileştirmeye yol açar: bir geçişte takas yapılmazsa döngüden erken çıkılabilir. Bu iyileştirme sunumdaki alıştırmalardan biridir. Sıralama yerinde yapılır; ek bellek yalnızca gecici değişkenidir: O(1).

10.7.5Eklemeli sıralama

Eklemeli sıralama, dizinin solunda sıralı bir bölüm büyütür. Her turda sıralı bölümün hemen sağındaki öğe anahtar olarak alınır. Sıralı bölümde anahtardan büyük olan öğeler birer hücre sağa kaydırılır ve anahtar açılan boşluğa yazılır. Elde iskambil kâğıdı dizmeye benzer.

import java.util.Arrays;

public class Eklemeli {
    public static void main(String[] args) {
        int[] a = {4, 3, 5, 1};
        for (int i = 1; i < a.length; i++) {
          int anahtar = a[i];
          int j = i - 1;
          while (j >= 0 && a[j] > anahtar) {
            a[j + 1] = a[j];
            j--;
          }
          a[j + 1] = anahtar;
        }
        System.out.println(Arrays.toString(a));
    }
}

[1, 3, 4, 5]

Kodda dizilere özgü üç nokta vardır. Birincisi, anahtar int anahtar = a[i]; ile ayrı bir değişkende saklanır. Kaydırma a[i]'nin üzerine yazacağı için bu zorunludur. Üçüncü turun ara adımları bunu açıkça gösterir. Kaydırmalar sırasında dizi [3, 4, 5, 5], [3, 4, 4, 5] ve [3, 3, 4, 5] hâllerinden geçer. Bu sırada 1 değeri yalnızca anahtar'da yaşar. İkincisi, while koşulundaki j >= 0 denetimi önce gelir. && işleci soldan sağa değerlendirilir ve sol taraf yanlışsa sağ tarafa hiç bakmaz. j −1 olduğunda a[j] okunmaz ve sınır dışı hatası önlenir. Koşulların sırası ters yazılsaydı (a[j] > anahtar && j >= 0) anahtar dizinin en küçüğü olduğunda program a[-1]'de dururdu. Üçüncüsü, döngü bitince anahtar a[j + 1]'e yazılır, çünkü j son kaydırılan öğenin bir solunda durur.

En kötü durumda, dizi ters sıralıysa, her anahtar bütün sıralı bölümü kaydırır ve maliyet O(n²) olur. Dizi zaten neredeyse sıralıysa kaydırma çok azdır ve maliyet O(n)'e yaklaşır. Bu yüzden eklemeli sıralama küçük ya da neredeyse sıralı dizilerde iyi bir seçimdir.

10.7.6İkili arama

İkili arama yalnızca sıralı bir dizide çalışır. Arama aralığının ortasındaki öğeye bakılır. Hedef ortadakinden büyükse sol yarı, küçükse sağ yarı elenir. Aralık her adımda yarıya indiği için n öğeli bir dizide en çok yaklaşık log₂ n + 1 tur gerekir. Java yazımında aralık iki indisle tutulur: lo (alt sınır) ve hi (üst sınır).

public class Ikili {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12, 16, 23, 38, 56};
        int hedef = 23, lo = 0, hi = a.length - 1;
        int sonuc = -1;
        while (lo <= hi) {
          int mid = (lo + hi) / 2;
          if (a[mid] == hedef) { sonuc = mid; break; }
          if (a[mid] < hedef) lo = mid + 1;
          else hi = mid - 1;
        }
        System.out.println(sonuc);
    }
}

5

23 iki turda bulunur. Doğrusal arama aynı hedef için altı karşılaştırma yapardı. Küçük dizide fark az görünür. Bir milyon öğeli sıralı dizide ise ikili arama en çok 20 tur ister. Doğrusal arama aynı dizide bir milyona kadar karşılaştırma yapabilir.

Dizilere özgü noktalar şunlardır. Başlangıçta hi = a.length - 1'dir; a.length geçerli bir indis değildir. Döngü koşulu lo <= hi'dir: lo ile hi eşitken aralıkta hâlâ bir öğe vardır ve ona bakılmalıdır. mid = (lo + hi) / 2 tam sayı bölmesidir ve aşağı yuvarlar: (0 + 7) / 2 = 3. Son olarak lo = mid + 1 ve hi = mid - 1 güncellemelerindeki ±1 zorunludur. mid'e zaten bakılmıştır. Güncelleme lo = mid diye yazılırsa aralık bazı durumlarda hiç daralmaz ve döngü sonsuza dek döner.

10.7.7Başarısız ikili arama

Hedef dizide yoksa aralık sonunda boşalır: lo, hi'yi geçer. O anda lo, hedefin sıralı dizide gireceği konumu, yani eklenme noktasını gösterir. Aşağıdaki metot bu bilgiyi Arrays.binarySearch ile aynı kurala göre döndürür:

import java.util.Arrays;

public class IkiliYok {
    static int ara(int[] a, int x) {
      int lo = 0, hi = a.length - 1;
      while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
      }
      return -(lo + 1);
    }

    public static void main(String[] args) {
        System.out.println(ara(new int[]{2, 4, 6, 8}, 5));
        System.out.println(Arrays.binarySearch(new int[]{2, 4, 6, 8}, 5));
        System.out.println(ara(new int[]{2, 4, 6, 8}, 1) + " " + ara(new int[]{2, 4, 6, 8}, 9));
    }
}

-3
-3
-1 -5

Döngü bittiğinde lo = 2'dir ve metot −(2 + 1) = −3 döndürür. Programın ikinci satırı, Arrays.binarySearch'ün aynı dizi ve aynı hedef için de −3 döndürdüğünü gösterir. Negatif sonuç “yok” demektir. Eklenme noktası sonuçtan geri hesaplanır: −(−3) − 1 = 2. Gerçekten de 5, 4 ile 6 arasına, 2 numaralı konuma girerdi. Üçüncü satır iki uç durumu sınar. Dizinin en küçüğünden küçük olan 1 için eklenme noktası 0, dönüş −1'dir. En büyüğünden büyük olan 9 için eklenme noktası 4, dönüş −5'tir.

10.7.8Temel karmaşıklıklar

Bu notta görülen dizi işlemlerinin maliyetleri, dizinin yapısından doğrudan çıkar. Tablo 10.21 bunları bir arada verir.

Şekil 10.17 ortaya eklemenin maliyetini somutlaştırır. Dizinin sonunda boş bir hücre bulunduğu varsayılmıştır. Ekleme noktasından sonraki her öğe bir sağa taşınır; kaydırma sağdan sola yapılır, yoksa öğeler birbirinin üzerine yazılır. Kabarcık ve eklemeli sıralama iki iç içe döngü kullandığı için O(n²) satırına girer. Arrays.sort ise O(n log n) maliyetle bu satırların arasında yer alır.

10.8İki boyutlu diziler

Bir sınıftaki öğrencilerin üç sınavdaki notları, bir resmin piksel renkleri ya da bir oyun tahtasının kareleri satırlar ve sütunlar hâlinde düzenlenir. Bu tür veriler için iki indisli bir yapı daha doğaldır: biri satırı, öteki sütunu seçer.

10.8.1Matris bildirimi ve erişim

Tipi int[][] diye yazılır. İlklendiricide her satır kendi süslü parantezi içinde verilir. Boş bir matris new int[2][3] ile oluşturulur: 2 satır, her satırda 3 sütun, bütün hücreler 0.

public class Matris {
    public static void main(String[] args) {
        int[][] matris = {
            {1, 2, 3},
            {4, 5, 6}
        };
        int deger = matris[1][2]; // 6
        System.out.println(deger + " " + matris.length + " " + matris[0].length);
        int[][] bos = new int[2][3];
        System.out.println(bos[1][2]);
    }
}

6 2 3
0

Erişimde ilk indis satırı, ikinci indis sütunu seçer. matris[1][2], 1 numaralı satırın 2 numaralı sütunudur, yani 6. Okuma soldan sağa yapılır: önce matris[1] ile satır dizisi bulunur, sonra o dizinin 2 numaralı hücresine gidilir.

Şekil 10.18 “dizilerin dizisi” fikrinin bellekteki karşılığını gösterir. Bu yapıdan iki önemli sonuç çıkar:

• matris.length dış dizinin uzunluğudur, yani satır sayısıdır (2). matris[0].length ise 0 numaralı satırın uzunluğudur, yani o satırdaki sütun sayısıdır (3).
• matris[1] tek başına geçerli bir ifadedir ve bir int[], yani bütün bir satırdır. Arrays.toString(matris[1]) o satırı [4, 5, 6] diye yazar.

10.8.2Düzensiz diziler

Satırlar ayrı nesneler olduğu için hepsinin aynı uzunlukta olması gerekmez. Satırları farklı uzunlukta olan iki boyutlu diziye düzensiz dizi (jagged array) denir. Böyle bir dizi oluşturmak için new ifadesinde yalnızca satır sayısı verilir; satırlar sonradan tek tek oluşturulur:

public class Duzensiz {
    public static void main(String[] args) {
        int[][] m = new int[3][];
        m[0] = new int[1];
        m[1] = new int[2];
        m[2] = new int[3];
        for (int i = 0; i < m.length; i++)
            System.out.print(m[i].length + " ");
        System.out.println();
    }
}

1 2 3 

new int[3][] yalnızca dış diziyi oluşturur. Dış dizinin hücreleri referans tuttuğu için varsayılan değerleri null'dır. Satırlar atanana kadar m[1].length gibi bir ifade çalıştırılırsa program NullPointerException ile durur. Çalışma sorularındaki bir soru tam olarak bu durumu sınar; JDK 21'in iletisi şöyledir:

> java Q20
6
Exception in thread "main" java.lang.NullPointerException: Cannot read the array length because "<local1>[1]" is null
	at Q20.main(Q20.java:7)

İleti, “<local1>[1] null olduğu için dizi uzunluğu okunamıyor” der. <local1>, m değişkeninin derlenmiş koddaki adıdır. Kaynak, javac -g seçeneğiyle derlenirse ileti değişkenin gerçek adını gösterir:

> javac -g Q20.java
> java Q20
6
Exception in thread "main" java.lang.NullPointerException: Cannot read the array length because "m[1]" is null
	at Q20.main(Q20.java:7)

Düzensiz diziler üçgen biçimli veriler için bellek kazandırır: Pascal üçgeni ya da bir mesafe tablosunun yarısı gibi.

10.8.3Sığ kopya tuzağı

İki boyutlu bir dizide clone yalnızca dış diziyi kopyalar. Dış dizinin hücrelerinde satırların referansları vardır; kopyalanan da bu referanslardır. Sonuçta iki ayrı dış dizi, aynı satır nesnelerini gösterir.

import java.util.Arrays;

public class Sig {
    public static void main(String[] args) {
        int[][] a = {{1, 2}, {3, 4}};
        int[][] b = a.clone();
        b[0][0] = 99;
        b[1] = new int[]{7, 8};
        System.out.println(Arrays.deepToString(a));
        System.out.println(Arrays.deepToString(b));
    }
}

[[99, 2], [3, 4]]
[[99, 2], [7, 8]]

İki satırın farklı sonuç vermesi tuzağın özüdür. b[0][0] = 99, ortak satır nesnesinin içine yazar; bu yüzden a'dan da görülür. b[1] = new int[]{7, 8} ise bir satırın içine değil, b'nin dış dizisindeki hücreye yazar. O hücre yalnızca b'ye aittir ve a etkilenmez. Gerçek, yani derin bir kopya için her satır ayrıca kopyalanır:

import java.util.Arrays;

public class Derin {
    public static void main(String[] args) {
        int[][] a = {{1, 2}, {3, 4}};
        int[][] b = new int[a.length][];
        for (int i = 0; i < a.length; i++)
            b[i] = a[i].clone();
        b[0][0] = 99;
        System.out.println(Arrays.deepToString(a));
        System.out.println(Arrays.deepToString(b));
    }
}

[[1, 2], [3, 4]]
[[99, 2], [3, 4]]

Bu kez b[0][0] = 99 yalnızca b'nin kendi satırını değiştirir; a [[1, 2], [3, 4]] olarak kalır. Döngüdeki b[i] = a[i].clone() her satır için ayrı bir nesne oluşturur.

10.8.4Matriste satır satır gezinme

Bir matrisin bütün hücrelerini gezmek için iki iç içe döngü kullanılır. Dış döngü satırları, iç döngü o satırın sütunlarını dolaşır:

public class Gezinme {
    public static void main(String[] args) {
        int[][] matris = {{1, 2, 3}, {4, 5, 6}};
        for (int i = 0; i < matris.length; i++) {
          for (int j = 0; j < matris[i].length; j++) {
            System.out.print(matris[i][j] + " ");
          }
          System.out.println();
        }
    }
}

1 2 3 
4 5 6 

İç döngünün sınırı matris[i].length'tir; yani her satır kendi uzunluğu kadar gezilir. Bu yazım düzensiz dizilerde de doğru çalışır. Hücreler print ile aynı satıra, aralarında boşlukla yazılır. Bir satır bittiğinde iç döngüden çıkılır ve println() alt satıra geçer.

Toplam 2 × 3 = 6 hücre gezilir. Genel olarak r satır ve c sütunlu bir matriste maliyet O(r · c)'dir. Kare bir n × n matriste bu O(n²) olur. Satır toplamı, sütun toplamı ya da en büyük hücreyi bulmak gibi işlemlerin hepsi bu iskeletin üzerine kurulur. Örneğin her satırın toplamı için iç döngüden önce int toplam = 0; yazılır ve iç döngü bitince toplam yazdırılır.

10.8.5Matris transpozu

Bir matrisin transpozu, satırların sütun, sütunların satır olduğu matristir. r × c boyutlu bir matrisin transpozu c × r boyutludur ve t[j][i] = matris[i][j] kuralıyla doldurulur.

import java.util.Arrays;

public class Transpoz {
    public static void main(String[] args) {
        int[][] matris = {{1, 2, 3}, {4, 5, 6}};
        int satirSayisi = matris.length;
        int sutunSayisi = matris[0].length;
        int[][] t = new int[sutunSayisi][satirSayisi];
        for (int i = 0; i < satirSayisi; i++)
            for (int j = 0; j < sutunSayisi; j++)
                t[j][i] = matris[i][j];
        System.out.println(Arrays.deepToString(t));
    }
}

[[1, 4], [2, 5], [3, 6]]

Kodda boyutlar baştan okunur: satirSayisi = matris.length (2), sutunSayisi = matris[0].length (3). Hedef dizi ters boyutla oluşturulur: new int[sutunSayisi][satirSayisi], yani 3 × 2. matris[0].length ile sütun sayısını almak, bütün satırların aynı uzunlukta olduğunu varsayar; transpoz zaten yalnızca düzenli matrisler için anlamlıdır. Her hücre bir kez kopyalanır: O(r · c) zaman ve hedef matris için r · c hücrelik ek bellek.

10.8.6Matris çarpımı

İki matrisin çarpımı C = A × B şöyle tanımlanır: C'nin i. satır j. sütunundaki hücresi, A'nın i. satırı ile B'nin j. sütunundaki karşılıklı öğelerin çarpımlarının toplamıdır. A'nın sütun sayısı B'nin satır sayısına eşit olmalıdır.

C[i][j] = A[i][0] · B[0][j] + A[i][1] · B[1][j] + … + A[i][m−1] · B[m−1][j]

import java.util.Arrays;

public class Carpim {
    public static void main(String[] args) {
        int[][] A = {{1, 2}, {3, 4}};
        int[][] B = {{5, 6}, {7, 8}};
        int[][] C = new int[2][2];
        for (int i = 0; i < 2; i++)
          for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
              C[i][j] += A[i][k] * B[k][j];
        System.out.println(Arrays.deepToString(C));
    }
}

[[19, 22], [43, 50]]

Kodda üç iç içe döngü vardır. i ve j hesaplanacak hücreyi seçer; k toplamın terimlerini dolaşır. C[i][j] += A[i][k] * B[k][j] deyimi her terimi hücreye ekler. C new int[2][2] ile oluşturulduğu için hücreler 0 ile başlar; ayrıca sıfırlamaya gerek yoktur. Kare n × n matrislerde her hücre için n çarpma, toplam n² hücre için n³ çarpma yapılır: O(n³). 100 × 100 matrisler için bu bir milyon çarpmadır.

10.9Dizi mi liste mi?

Dizinin uzunluğu sabittir. Öğe sayısı program çalışırken artıp azalıyorsa bu sınır can sıkar: her eklemede yeni ve daha büyük bir dizi oluşturmak, eski öğeleri oraya kopyalamak gerekir. Java'nın koleksiyon kütüphanesindeki ArrayList sınıfı bu işi kendisi yapar.

import java.util.ArrayList;

public class Liste {
    public static void main(String[] args) {
        ArrayList<Integer> liste = new ArrayList<>();
        liste.add(3);
        liste.add(8);
        liste.add(5);
        liste.add(7);
        System.out.println(liste + " " + liste.size() + " " + liste.get(1));
    }
}

[3, 8, 5, 7] 4 8

ArrayList içeride yine bir dizi kullanır. Dizi dolduğunda daha büyük bir dizi açar ve öğeleri oraya taşır (Şekil 10.24). Programcı yalnızca add, get ve size gibi metotları çağırır. Erişim için köşeli parantez yerine liste.get(1), uzunluk için length yerine liste.size() yazılır.

Bu kolaylığın bir bedeli vardır. int[] sayıları hücrelerde doğrudan saklar. ArrayList<Integer> ise yalnızca nesne tutabilir; her sayı bir Integer nesnesinin içine konur ve listede bu nesnelerin referansları durur. Bu, daha fazla bellek ve bir miktar daha yavaş erişim demektir. Seçim için kaba bir kural verilebilir:

• Öğe sayısı baştan belli ve sabitse, örneğin haftanın günleri, bir matrisin hücreleri ya da bir sayaç tablosu, dizi yeterli ve hızlıdır.
• Öğe sayısı çalışma sırasında değişecekse, örneğin kullanıcının girdiği kayıtlar, ArrayList gibi bir koleksiyon daha kullanışlıdır.

Son karar kullanım biçimine, kodun okunabilirliğine ve gerekirse ölçülen performansa göre verilir. Bu notta öğrenilen gezinme, arama ve sıralama yöntemleri listelerde de aynen geçerlidir.

10.10Yaygın hatalar

Dizilerle ilgili hataların çoğu dört gruba girer. Bu kesim her birini çalıştırılmış bir örnekle verir.

public class DuzensizHata {
    public static void main(String[] args) {
        int[][] m = {{1, 2, 3}, {4}};
        int toplam = 0;
        for (int i = 0; i < m.length; i++)
            for (int j = 0; j < m[0].length; j++)
                toplam += m[i][j];
        System.out.println(toplam);
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
	at DuzensizHata.main(DuzensizHata.java:7)

Bu dört hatanın ortak noktası, derleyicinin hiçbirini yakalamamasıdır. Hepsi ya çalışma sırasında bir istisnayla ya da hiç iletisiz yanlış bir sonuçla ortaya çıkar. Bu yüzden dizi kodu yazılırken üç sınır durumu her zaman denenir: boş dizi, tek öğeli dizi ve hedefin ilk ya da son konumda olduğu dizi.

10.11Özet

• Dizi, aynı tipten sabit sayıda öğeyi art arda hücrelerde tutan bir nesnedir. İndisler 0'dan length − 1'e gider; length bir alandır ve oluşturulduktan sonra değişmez.
• Dizi değişkeni yığında durur ve heap'teki dizi nesnesinin referansını tutar. new ile oluşturulan hücreler varsayılan değeri alır: sayılarda 0, boolean'da false, nesnelerde null. İlklendirici {…} uzunluğu değer sayısından çıkarır.
• a[i] okuma ve yazma O(1) zamanda yapılır, çünkü adres başlangıç + i × hücre boyu formülüyle hesaplanır. Geçersiz indis ArrayIndexOutOfBoundsException ile programı durdurur; en yaygın nedeni <= ile yazılan döngü koşuludur.
• Klasik for indis gerektiğinde, gelişmiş for yalnızca okuma yapılacağında kullanılır. Gelişmiş for'daki döngü değişkeni öğenin kopyasıdır; ona yapılan atama diziyi değiştirmez.
• Toplam ve ortalama bir biriktiriciyle, en küçük ve en büyük dizinin ilk öğesiyle başlatılan adaylarla bulunur. Ters çevirme iki işaretçiyle yerinde yapılır. Frekans saymada değer indis olarak kullanılır. Eratosthenes eleği bir boolean dizisiyle asal olmayanları eler.
• b = a yalnızca referansı kopyalar. clone, Arrays.copyOf ve System.arraycopy öğeleri kopyalar, ama sığ kopya yapar. == ve equals referansı, Arrays.equals içeriği karşılaştırır. Metoda giden dizi, çağıranın dizisiyle aynı nesnedir.
• Doğrusal arama O(n), sıralı dizide ikili arama O(log n) zamandadır. Arrays.sort diziyi yerinde sıralar; Arrays.binarySearch bulamazsa -(eklenme noktası) - 1 döndürür. Kabarcık ve eklemeli sıralama O(n²)'dir.
• int[][] dizilerin dizisidir. matris.length satır, matris[i].length o satırın sütun sayısıdır. Satırlar farklı uzunlukta olabilir (düzensiz dizi). clone yalnızca dış diziyi kopyalar. Gezinme iki, matris çarpımı üç iç içe döngüyle yapılır.

10.12Kavram listesi

• dizi array
• öğe element
• hücre cell
• indis index
• uzunluk length
• referans reference
• heap heap
• yığın stack
• varsayılan değer default value
• ilklendirici array initializer
• null null reference
• sınır dışı out of bounds
• istisna exception
• gezinme traversal
• gelişmiş for enhanced for loop
• ters çevirme reversing
• işaretçi pointer
• takas swap
• frekans frequency
• Eratosthenes eleği Sieve of Eratosthenes
• kopya copy
• sığ kopya shallow copy
• doğrusal arama linear search
• ikili arama binary search
• ortanca median
• kabarcık sıralaması bubble sort
• eklemeli sıralama insertion sort
• zaman karmaşıklığı time complexity
• iki boyutlu dizi two-dimensional array
• çok boyutlu dizi multidimensional array
• matris matrix
• düzensiz dizi jagged array

10.13Kendini Dene

1. Aşağıdaki programın çıktısı nedir?

   import java.util.Arrays;
   
   public class KD1 {
       public static void main(String[] args) {
           int[] a = new int[4];
           a[a.length - 1] = a.length;
           a[a[3] - 3] = 9;
           System.out.println(Arrays.toString(a));
       }
   }

   Cevap

   [0, 9, 0, 4]

   Dizi dört sıfırla başlar. a[a.length - 1] = a.length son hücreye, yani a[3]'e 4 yazar. Sonraki satırda iç ifade önce hesaplanır: a[3] - 3 = 4 − 3 = 1. Böylece a[1]'e 9 yazılır.

2. Aşağıdaki programda sifirla metodu çağrıldıktan sonra a ne olur?

   import java.util.Arrays;
   
   public class KD2 {
       static void sifirla(int[] d) {
           d[0] = 0;
           d = new int[]{5, 5, 5};
           d[1] = 0;
       }
   
       public static void main(String[] args) {
           int[] a = {1, 2, 3};
           sifirla(a);
           System.out.println(Arrays.toString(a));
       }
   }

   Cevap

   [0, 2, 3]

   Metoda a'nın referansı gider. d[0] = 0 ortak diziye yazar ve a[0] 0 olur. d = new int[]{5, 5, 5} ise yalnızca metodun yerel değişkenini yeni bir diziye bağlar. Bundan sonraki d[1] = 0 bu yeni diziyi değiştirir; a etkilenmez.

3. Aşağıdaki programın çıktısı nedir? Üç değerin her biri neden öyledir?

   import java.util.Arrays;
   
   public class KD3 {
       public static void main(String[] args) {
           int[] p = {4, 5};
           int[] q = p.clone();
           int[] r = p;
           System.out.println((p == q) + " " + (p == r) + " " + Arrays.equals(p, q));
       }
   }

   Cevap

   false true true

   p == q yanlıştır, çünkü clone yeni bir nesne oluşturur. p == r doğrudur, çünkü r = p aynı referansı kopyalar. Arrays.equals(p, q) doğrudur, çünkü iki dizinin uzunluğu ve öğeleri aynıdır.

4. Arrays.binarySearch önce sıralanmamış, sonra sıralanmış bir dizide 1'i arıyor. Çıktı nedir ve ilk sonuç neden yanlıştır?

   import java.util.Arrays;
   
   public class KD4 {
       public static void main(String[] args) {
           int[] a = {5, 1, 9, 3, 7};
           System.out.println(Arrays.binarySearch(a, 1));
           Arrays.sort(a);
           System.out.println(Arrays.binarySearch(a, 1));
       }
   }

   Cevap

   -1
   0

   İlk aramada aralık 0…4'tür ve ortadaki öğe a[2] = 9'dur. 1 < 9 olduğu için sağ yarı elenir. Sonra a[0] = 5'e bakılır; 1 < 5 olduğu için yine sola gidilir ve aralık boşalır. Metot −1 döndürür, oysa 1 dizide, 1 numaralı konumdadır. Metot dizinin sıralı olduğunu varsaydığı için yanlış yarıyı elemiştir. Sıralamadan sonra dizi [1, 3, 5, 7, 9] olur ve 1 doğru biçimde 0 numaralı konumda bulunur.

5. Aşağıdaki program üçgen biçimli bir düzensiz dizi oluşturuyor. t[3].length ve toplam hücre sayısı kaçtır?

   public class KD5 {
       public static void main(String[] args) {
           int[][] t = new int[4][];
           int hucre = 0;
           for (int i = 0; i < t.length; i++) {
               t[i] = new int[i + 1];
               hucre += t[i].length;
           }
           System.out.println(t[3].length + " " + hucre);
       }
   }

   Cevap

   4 10

   i numaralı satır i + 1 hücrelidir: 1, 2, 3 ve 4. Son satırın uzunluğu 4, toplam hücre sayısı 1 + 2 + 3 + 4 = 10'dur. Düzenli bir 4 × 4 matris 16 hücre isterdi.

6. Ters sıralı {4, 3, 2, 1} dizisi kabarcık sıralamasıyla sıralanıyor. Kaç karşılaştırma ve kaç takas yapılır?

   import java.util.Arrays;
   
   public class KD6 {
       public static void main(String[] args) {
           int[] a = {4, 3, 2, 1};
           int kars = 0, takas = 0;
           for (int gecis = 0; gecis < a.length - 1; gecis++)
               for (int j = 0; j < a.length - 1 - gecis; j++) {
                   kars++;
                   if (a[j] > a[j + 1]) {
                       int g = a[j]; a[j] = a[j + 1]; a[j + 1] = g;
                       takas++;
                   }
               }
           System.out.println(Arrays.toString(a) + " " + kars + " " + takas);
       }
   }

   Cevap

   [1, 2, 3, 4] 6 6

   Karşılaştırma sayısı dizinin içeriğine bağlı değildir: 3 + 2 + 1 = 6. Ters sıralı dizide her karşılaştırma bozuk bir çift bulur ve takasla sonuçlanır; takas sayısı da 6'dır. Bu, n = 4 için en kötü durumdur: n(n − 1)/2 = 6.

7. Aşağıdaki program bir dizide en sık geçen rakamı arıyor. Çıktı nedir? say dizisi neden 10 hücrelidir?

   public class KD7 {
       public static void main(String[] args) {
           int[] a = {2, 7, 7, 3, 7};
           int[] say = new int[10];
           for (int x : a) say[x]++;
           int enCok = 0;
           for (int d = 1; d < say.length; d++)
               if (say[d] > say[enCok]) enCok = d;
           System.out.println(enCok + " " + say[enCok]);
       }
   }

   Cevap

   7 3

   Değerler indis olarak kullanılır: say[x]++. Rakamlar 0…9 arasında olduğu için 10 hücre gerekir. Sayma sonunda say[2] = 1, say[3] = 1, say[7] = 3'tür. İkinci döngü en büyük sayacın indisini arar; 7 üç kez geçtiği için sonuç 7 3'tür.

8. Aşağıdaki program 3 × 3 bir matrisi dolduruyor. m[2][1] ve m[1][2] kaçtır?

   public class KD8 {
       public static void main(String[] args) {
           int[][] m = new int[3][3];
           for (int i = 0; i < 3; i++)
               for (int j = 0; j < 3; j++)
                   m[i][j] = i * 3 + j;
           System.out.println(m[2][1] + " " + m[1][2]);
       }
   }

   Cevap

   7 5

   Her hücreye i * 3 + j yazılır; hücreler satır satır 0'dan 8'e kadar numaralanmış olur. m[2][1] = 2 · 3 + 1 = 7, m[1][2] = 1 · 3 + 2 = 5. İlk indis satır, ikinci indis sütun olduğu için iki ifade farklı hücreleri gösterir.

9. Bir programcı, uzunluğu n olan bir diziyi sondan başa yazdırmak için for (int i = a.length; i >= 0; i--) döngüsünü yazıyor. Hangi hata oluşur ve döngü nasıl düzeltilir?

   Cevap

   İlk turda i = a.length'tir ve a[a.length] okunmaya çalışılır. Üç öğeli bir diziyle çalıştırılan program hiçbir şey yazdırmadan durur:

   Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
   	at KD9.main(KD9.java:5)

   Son geçerli indis a.length - 1 olduğu için doğru başlangıç int i = a.length - 1'dir. Koşul i >= 0 doğrudur, çünkü 0 numaralı hücre de yazdırılmalıdır.

10.14İleri okuma

• Oracle, The Java Tutorials, “Arrays”: dizi bildirimi, oluşturma, çok boyutlu diziler, kopyalama ve java.util.Arrays metotlarını kısa, çalıştırılabilir örneklerle anlatır.
• R. Sedgewick, K. Wayne, Computer Science: An Interdisciplinary Approach (Addison-Wesley, 2016), 1.4 Arrays: deste karıştırma, kupon toplayıcı problemi ve Eratosthenes eleği gibi dizi uygulamalarını içerir; kitabın sitesinde (introcs.cs.princeton.edu) program kodları ve alıştırmalar vardır.
• A. B. Downey, C. Mayfield, Think Java (2. baskı, O'Reilly, 2019), Bölüm 7 “Arrays and References”: referans kavramını, dizilerin metotlara aktarılmasını ve gezinme kalıplarını yeni başlayanlar için sade bir dille anlatır; ücretsiz çevrim içi sürümü vardır.
• Oracle, The Java Language Specification, Java SE 21 Edition, Bölüm 10 “Arrays”: dizi tiplerinin, ilklendiricilerin, varsayılan değerlerin ve clone davranışının kesin tanımını verir.

10.15Kaynaklar

1. P. Deitel, H. Deitel, Java: How to Program, Early Objects, 11. baskı, Pearson, 2018.
2. Y. D. Liang, Introduction to Java Programming and Data Structures, 13. baskı, Pearson, 2024.
3. Oracle, The Java Tutorials: Arrays.
4. Oracle, Java SE 21 API: java.util.Arrays; The Java Language Specification, Java SE 21 Edition: Chapter 10. Arrays.
5. R. Sedgewick, K. Wayne, Computer Science: An Interdisciplinary Approach, Addison-Wesley, 2016: 1.4 Arrays.
6. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
7. A. B. Downey, C. Mayfield, Think Java, 2. baskı, O'Reilly, 2019 (ücretsiz çevrim içi sürüm).

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