Bölüm 1.3: Algoritmalar

1.3.1Problem çözme

Programlamaya yeni başlayan biri çoğu zaman problemi okur okumaz kod yazmaya girişir. Küçük problemlerde bu yöntem bir süre işe yarar. Problem biraz büyüdüğünde ise yazılan kod ne yaptığı belli olmayan bir yamalar yığınına döner. Hata çıktığında nereden kaynaklandığı da bulunamaz, çünkü ortada “programın ne yapması gerektiğini” söyleyen yazılı bir şey yoktur. Deneyimli programcılar bu yüzden işi aşamalara böler. Her aşamanın çıktısı bir sonrakinin girdisi olur ve her aşama kendi içinde denetlenebilir.

1.3.1.1Önce algoritma, sonra uygulama

Bir problemin bilgisayarla çözülmesi dört adımlı bir döngüdür (Şekil 1.3.1). İlk adım sorunu tanımlamaktır: ne verilecek, ne istenecek? Bu sorunun cevabı belirsiz kaldıkça sonraki adımların hepsi boşa gidebilir. İkinci adım algoritmayı belirlemektir. Algoritma, sorunu çözmek için izlenecek adımların listesidir. Aynı sorun için birden çok algoritma bulunabilir; doğru seçim programın hızını ve bellek kullanımını belirler. Üçüncü adım algoritmanın seçilen programlama dilinde, bu derste Java'da, koda dönüştürülmesidir. Dördüncü adımda program önceden hazırlanmış test senaryolarıyla denenir. Bir test beklenen sonucu vermezse önceki adımlara dönülür. Hata kodlamada olabilir, algoritmada olabilir, hatta sorunun yanlış anlaşılmasından da kaynaklanabilir.

Bu düzenin en önemli kazancı, hataların ucuz oldukları anda yakalanmasıdır. Kâğıt üzerindeki bir algoritmada bulunan yanlış birkaç satırlık düzeltmeyle giderilir. Aynı yanlış yüzlerce satırlık bir programın içine gömüldükten sonra bulunursa hem bulmak hem düzeltmek çok daha pahalıdır. Test senaryolarının kod yazılmadan önce hazırlanması da aynı nedene dayanır. Program yazıldıktan sonra hazırlanan testler, farkında olmadan programın yaptığını “doğru” sayma eğilimindedir.

1.3.1.2Algoritma nedir?

Sözcük, 9. yüzyılda Bağdat'ta yaşamış matematikçi el-Hârizmî'nin adından gelir. Adının Latince yazılışı Algoritmi idi; onun ondalık sayılarla hesap üzerine yazdığı kitabın Latince çevirisi Avrupa'da bu adla tanındı. Zamanla “algoritma” sözcüğü, hesap yapmanın adım adım tarif edilmiş her yöntemi için kullanılır oldu.

Bilgisayar bir algoritmayı doğrudan anlamaz. Algoritma insanın düşünme biçimiyle yazılır; bilgisayar ise yalnız kendi makine dilindeki komutları çalıştırır. Aradaki köprü programlama dilidir: algoritma Java gibi bir dile çevrilir, derleyici bu metni makinenin çalıştırabileceği biçime dönüştürür. Bir algoritmanın birden çok programla yazılabileceği gibi, bir problemin de birden çok algoritması olabilir. Bu algoritmalar genellikle iki ölçüyle karşılaştırılır: ne kadar sürede bittikleri ve ne kadar bellek kullandıkları.

Gündelik hayattan en tanıdık benzetme yemek tarifidir. Malzemeler girdidir, yapılış adımları algoritmadır, ortaya çıkan yemek de çıktıdır. Ancak tarifler insan için yazılır ve “biraz tuz ekle”, “kıvamını bulana dek karıştır” gibi belirsiz adımlar içerir. Deneyimli bir aşçı bu boşlukları kendi bilgisiyle doldurur. Bilgisayar ise “biraz” sözcüğüne bir sayı karşılık getiremez; ona “5 gram tuz ekle” demek gerekir. Bir yönergeler listesinin algoritma sayılması için beş özelliği taşıması beklenir (Tablo 1.3.1).

Girdi özelliğinin “sıfır ya da daha fazla” diye tanımlanması bilinçlidir. Ekrana ilk on asal sayıyı yazan bir algoritmanın hiç girdisi yoktur ama yine de bir algoritmadır. Çıktısı olmayan bir yöntem ise hiçbir şey üretmediği için işe yaramaz; bu yüzden en az bir çıktı istenir. Sonluluk, algoritmanın her girdi için bir noktada durmasıdır. Kullanıcı yanlış değer girdiğinde sonsuza dek dönen bir döngü bu özelliği bozar. Etkinlik ise adımların gerçekten yapılabilir olmasını ister: “bütün asal sayıları listele” adımı açık ve tek anlamlıdır ama sonsuz sayıda asal sayı olduğu için yapılamaz.

1.3.1.3Sorunu tanımlama ve test senaryoları

Sorunu tanımlamak, programın girdilerini ve çıktılarını doğal dille, bu derste Türkçe, açıkça yazmak demektir. “İki sayıyı topla” cümlesi ilk bakışta yeterli görünür. Biraz düşününce sorular çıkar: sayılar tam sayı mı, ondalıklı da olabilir mi? Negatif sayı girilebilir mi? Sonuç ekrana mı yazılacak, başka bir hesapta mı kullanılacak? Bu soruların cevapları tanıma eklendikçe programın ne yapacağı netleşir.

Tanımın ikinci parçası test senaryolarıdır. Test senaryosu (test case), belirli bir girdi için beklenen çıktının önceden yazılmasıdır. Program çalıştırılır, ürettiği çıktı beklenenle karşılaştırılır; ikisi aynıysa test geçer (Şekil 1.3.2). Beklenen çıktı programdan bağımsız olarak, elle ya da başka bir güvenilir yolla bulunmalıdır. Yoksa test, programı kendisiyle karşılaştırmaktan öteye geçmez.

Tablo 1.3.2 iki küçük problem için hazırlanmış test senaryolarını gösterir. Her problemde ilk iki satır sıradan girdilerdir. Üçüncü satırlar ise bilinçli seçilmiş sınır durumlardır (edge case). Sıfır, boş metin, negatif sayı, dizinin ilk ya da son öğesi bu tür uç girdilerdir. Programcılar sıradan girdileri doğal olarak düşünür; uçlar ise kolayca unutulur. Bu yüzden hatalar en çok uçlarda saklanır. Kelime sayan bir program “Merhaba, dünya!” için 2 verirken boş metinde 1 verebilir. Metni boşluklardan bölen basit bir yaklaşım, hiç boşluk olmayan boş metni bile tek parça sayar.

İyi bir test kümesi az sayıda ama birbirinden farklı durumları kapsar. Toplama için 3 + 5, 4 + 6 ve 10 + 20 testleri aynı şeyi üç kez sınar: üçü de pozitif tam sayıdır. Bunların yerine bir pozitif çift, bir negatifli çift ve bir sıfır çifti seçmek, aynı emekle çok daha fazla hata yakalama şansı verir. Bu notun bütün algoritmalarında test senaryoları bu ilkeyle seçilmiştir: her biri için hem sıradan hem uç girdiler vardır.

1.3.1.4Algoritma belirleme ve elle izleme

Sorun tanımlandıktan sonra çözümün adımları sırayla yazılır. İki sayının toplamı için algoritma dört adımdır:

1. İlk sayıyı al.
2. İkinci sayıyı al.
3. İki sayıyı topla.
4. Toplamı ekrana yazdır.

Algoritma yazılınca iş bitmez; kod yazılmadan önce algoritmanın kendisi test edilir. Bunun yolu elle izlemedir (dry run). Bir test senaryosu seçilir ve algoritma kâğıt üzerinde adım adım çalıştırılır. Her adımdan sonra değişkenlerin değeri bir tabloya yazılır. Bu tabloya izleme tablosu (trace table) denir. Tablonun sütunları değişkenler ve ekran, satırları adımlardır. Bir hücre boş bırakılırsa o değişken o anda henüz bir değer almamıştır.

Bu örnekte izleme çok kolaydır ve gereksiz görünebilir. Ama aynı alışkanlık döngülü algoritmalarda büyük fark yaratır. Döngünün kaç kez döndüğü, bir değişkenin hangi turda hangi değeri aldığı, döngünün bir tur erken mi geç mi bittiği ancak böyle bir tabloyla güvenle görülür. Elle izlemede küçük ama anlamlı test senaryoları seçilir. Faktöriyel için 5 iyi bir seçimdir: beş tur elle izlenebilir ve sonuç (120) ezbere bilinir. 20 ise kötü bir seçimdir; hem tablo uzar hem de sonucu doğrulamak zorlaşır.

1.3.1.5Sözde kod

Algoritma dört biçimde yazılabilir: doğal dille, sözde kodla, akış diyagramıyla ya da doğrudan bir programlama diliyle. Doğal dil herkesin anladığı ama belirsizliğe açık bir araçtır. Programlama dili ise kesindir ama ayrıntı yükü ağırdır: noktalı virgüller, tip bildirimleri, kütüphane adları asıl düşünceyi gölgeler. Sözde kod (pseudocode) bu ikisinin arasında durur.

Sözde kodun iki büyük yararı vardır. Birincisi, mantık hatalarını kod yazmadan önce bulmayı kolaylaştırır: dikkat sözdizimine değil, adımların sırasına ve koşullara yönelir. İkincisi, farklı diller kullanan programcıların aynı algoritma üzerinde konuşmasını sağlar. Java bilen biriyle Python bilen biri aynı sözde kodu okuyup kendi dillerine çevirebilir. Bu notta kullanılan sözde kod anahtar sözcükleri ve Java karşılıkları Tablo 1.3.4'te toplanmıştır.

Tablonun en sinsi satırı eşitlik satırıdır. Sözde kodda ve matematikte = işareti hem atama hem karşılaştırma için kullanılır; anlam bağlamdan çıkarılır. Java'da ise bu iki iş farklı işaretlerle yapılır. Tek eşittir (=) sağdaki değeri soldaki değişkene koyar. Çift eşittir (==) iki değeri karşılaştırır ve true ya da false üretir. Sözde koddan Java'ya çeviri yapılırken her Eğer … = … ise satırındaki işaretin =='ye dönüştürülmesi gerekir.

Mantıksal işleçlerde de benzer bir ayrım vardır. Sözde koddaki “ve” Java'da &&, “veya” ise || ile yazılır. Bu işleçler kısa devre çalışır. a && b ifadesinde a yanlışsa sonuç zaten yanlış olacağı için b hiç hesaplanmaz. a || b ifadesinde a doğruysa b'ye bakılmaz.

1.3.2Koda dönüştürme

Algoritma hazırlanıp elle izlendikten sonraki adım kodlamadır (implementation). Programlama dili, algoritmayı bilgisayarın derleyip çalıştırabileceği biçimde ifade eder. Kod yazılırken program mantıksal parçalara ayrılır: girdi alma, hesaplama ve çıktı verme. Daha büyük programlarda her parça ayrı bir metoda taşınır. Sözde koddaki her satır genellikle bir ya da birkaç Java satırına karşılık gelir.

1.3.2.1Sözde koddan çalışan programa

Bir algoritmanın ekranda sonuç üretmesine kadar dört durak vardır (Şekil 1.3.3). Sözde kod Java kaynak koduna çevrilir ve Toplama.java gibi bir dosyaya yazılır. Java derleyicisi javac bu dosyayı okur. Kodda yazım hatası yoksa Toplama.class adlı bir bayt kodu (bytecode) dosyası üretir. Bayt kodu belirli bir işlemcinin makine dili değildir. Java sanal makinesinin (Java Virtual Machine, JVM) anladığı ara bir dildir. java Toplama komutu JVM'yi başlatır; JVM bayt kodunu çalıştırır ve çıktı ekrana gelir. Aynı .class dosyası Windows'ta, Linux'ta ya da macOS'ta, JVM kurulu her makinede çalışır.

Hatalar iki farklı anda ortaya çıkabilir. Derleme hataları javac çalışırken bulunur: eksik noktalı virgül, yanlış yazılmış anahtar sözcük, tanımlanmamış değişken, uyumsuz tip. Derleme hatası olan bir programdan .class dosyası üretilmez. Çalışma zamanı hataları ise program çalışırken çıkar: dizinin olmayan bir hücresine erişmek, sıfıra bölmek, kullanıcının sayı yerine harf girmesi. Üçüncü ve en tehlikeli tür mantık hatalarıdır. Program derlenir, çalışır, hiçbir ileti vermez ama yanlış sonuç üretir. Bu tür hataları ancak testler yakalar.

Algoritma adımlarıyla Java satırları arasındaki eşleşme Tablo 1.3.5'te görülür. Her adım tek bir satıra dönüşmüştür. Daha karmaşık algoritmalarda bir adım birkaç satır tutabilir; ama eşleşmenin izi her zaman sürülebilir olmalıdır.

Adlandırma konusunda bir not: Java kütüphaneleri İngilizce adlar kullanır (Scanner, nextDouble, println). Bu derste kendi değişken ve metot adlarımız Türkçe seçilir, ama Türkçe karakter kullanılmaz: sayı1 yerine sayi1, üçüncü yerine ucuncu. Java aslında Türkçe harfli adları kabul eder. Yine de kaynak dosya farklı bir karakter kodlamasıyla açıldığında bu harfler bozulabilir ve derleme hatasına yol açabilir. Sözde kodda böyle bir sorun yoktur; orada birinciTamsayı gibi adlar rahatça kullanılır.

1.3.2.2Toplama programı

Toplama algoritmasının tam Java programı aşağıdadır. Sunumda yalnız main gövdesi gösterilen kod burada import satırı ve sınıf tanımıyla birlikte verilmiştir; bu hâliyle Toplama.java adlı bir dosyaya yazılıp derlenebilir.

import java.util.Scanner;

public class Toplama {
    public static void main(String[] args) {
        Scanner tarayici = new Scanner(System.in);
        System.out.print("Birinci sayıyı giriniz: ");
        double sayi1 = tarayici.nextDouble();
        System.out.print("İkinci sayıyı giriniz: ");
        double sayi2 = tarayici.nextDouble();
        double toplam = sayi1 + sayi2;
        System.out.println(sayi1 + " ile " + sayi2
                + " toplamı: " + toplam);
        tarayici.close();
    }
}

İlk satırdaki import java.util.Scanner; derleyiciye Scanner sınıfının nerede bulunacağını söyler. Java'nın standart kütüphanesi paketlere bölünmüştür ve Scanner, java.util paketindedir. System ve String gibi birkaç temel sınıf java.lang paketindedir ve bu paket her programa kendiliğinden eklenir. Geri kalan her sınıf için import gerekir. Satır unutulursa derleyici Scanner adını tanımaz:

Toplama.java:4: error: cannot find symbol
        Scanner tarayici = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Toplama

Aynı satırda Scanner iki kez geçtiği için derleyici bu hatayı iki kez bildirir ve “2 errors” der. Tek bir eksik satır birden çok hata iletisine yol açabilir. Bu yüzden derleme hataları her zaman ilkinden başlanarak okunur.

public class Toplama satırı sınıfı tanımlar. Herkese açık bir sınıfın adı dosya adıyla aynı olmak zorundadır: Toplama sınıfı Toplama.java dosyasında durur. public static void main(String[] args) ise programın başlangıç noktasıdır; JVM çalıştırmaya bu metottan başlar. Sözde koddaki Başla … Bitir çiftinin karşılığı bu metodun süslü parantezleridir.

Scanner tarayici = new Scanner(System.in); klavyeden okuma yapacak bir nesne oluşturur. System.in standart girdi akışıdır, yani klavye. tarayici nesnesinin nextDouble() metodu bir sonraki sayıyı double olarak, nextInt() metodu int olarak, nextLine() metodu ise satırın tamamını metin olarak okur. Program sonundaki tarayici.close(); nesnenin kullandığı kaynağı serbest bırakır.

double toplam = sayi1 + sayi2; satırında önce sağ taraf hesaplanır, sonra sonuç soldaki değişkene konur. Atama işlemi her zaman sağdan sola işler. Bu yüzden toplam = toplam + 1 gibi matematikte saçma görünen bir satır programlamada anlamlıdır: “toplamın şimdiki değerine 1 ekle ve sonucu yine toplama koy”.

1.3.2.3Toplama programının izlenmesi

Kullanıcının 3 ve 5 girdiği bir çalıştırmanın satır satır izlemesi Tablo 1.3.6'dadır. Satır numaraları main gövdesinin satırlarıdır: 1. satır Scanner'ın oluşturulduğu satır, 9. satır close çağrısıdır.

Programın ekrana yazdığı son satır “3.0 ile 5.0 toplamı: 8.0”dır. Test senaryosu 8 bekliyordu; program 8.0 yazdı. Değer aynıdır, yazım biçimi farklıdır. double tipindeki bir sayı metne çevrilirken tam sayı olsa bile ondalık kısmıyla, “8.0” biçiminde yazılır. Test senaryoları yazılırken bu tür biçim farkları da düşünülmelidir. Testi otomatik yapan bir program “8” ile “8.0” metinlerini farklı sayar.

1.3.2.4Okuma ve yazmanın ayrıntıları

print ve println. İki metot da kendisine verilen değeri ekrana yazar. Fark, yazdıktan sonra ne olduğundadır. println (print line) değeri yazıp alt satıra geçer; print geçmez. Kullanıcıdan girdi isterken print kullanılması bu yüzdendir: imleç “Birinci sayıyı giriniz: ” iletisinin hemen yanında bekler ve kullanıcı sayıyı aynı satıra yazar. Bir dizi değeri aynı satıra yan yana yazmak için de print kullanılır; son değerden sonra bir println() satırı tamamlar.

Metin birleştirme ve işlem sırası. + işleci iki sayı arasında toplama, bir metinle herhangi bir değer arasında birleştirme yapar. İfade soldan sağa hesaplanır ve bu, şaşırtıcı sonuçlara yol açabilir. Tablo 1.3.7 JDK 21'de çalıştırılarak elde edilmiş çıktıları gösterir.

Tam sayı bölmesi bu bölümün algoritmalarında sık kullanılır. Asal sayı kontrolündeki sayi / 2, basamak toplamındaki sayi / 10 ve ikili aramadaki (alt + ust) / 2 hep tam sayı bölmesidir ve kesirli kısmı bilerek atar. Kalan işleci % da en az onun kadar önemlidir. sayi % bolen == 0 “tam bölünür” demektir; sayi % 10 son basamağı, sayi % 2 ise çift mi tek mi olduğunu verir.

Ondalık ayırıcı ve yerel ayar. Scanner sayıları okurken bilgisayarın yerel ayarını (locale) kullanır. Türkçe ayarlı bir bilgisayarda ondalık ayırıcı virgüldür. Bu yüzden toplama programına “3,5” yazmak çalışır, “3.5” yazmak ise programı durdurur:

Birinci sayıyı giriniz: 3.5
Exception in thread "main" java.util.InputMismatchException
	at java.base/java.util.Scanner.throwFor(Scanner.java:947)
	at java.base/java.util.Scanner.next(Scanner.java:1602)
	at java.base/java.util.Scanner.nextDouble(Scanner.java:2573)
	at Toplama.main(Toplama.java:7)

İngilizce ayarlı bir bilgisayarda durum tersinedir: “3.5” kabul edilir, “3,5” reddedilir. Programın çıktısı ise her iki ayarda da “3.5” biçimindedir, çünkü double değerin metne çevrilmesi yerel ayara bakmaz. Aynı programın farklı bilgisayarlarda farklı davranması öğrencileri sık şaşırtır. Okumanın her yerde aynı olması isteniyorsa tarayıcı new Scanner(System.in).useLocale(Locale.US) biçiminde oluşturulur. Kullanıcı sayı yerine harf girdiğinde de aynı InputMismatchException fırlatılır. Bu istisnanın yakalanıp kullanıcıya yeniden sorulması daha ileri bir konudur. Bu notun programları kullanıcının geçerli bir sayı girdiğini varsayar.

1.3.3Karar yapısıyla algoritmalar

Bu kesimden başlayarak her algoritma aynı düzenle işlenir. Önce sorun ve test senaryoları tanımlanır, sonra sözde kod yazılır ve değişken tablosuyla elle izlenir. En son Java kodu verilir ve testler çalıştırılır. İlk iki örnek döngü içermez. Algoritmanın izleyeceği yol, girdilerin karşılaştırılmasıyla verilen kararlara bağlıdır.

1.3.3.1İki tam sayıyı sıralı yazdırma

Sorun tanımı. Girdi iki tam sayıdır. Çıktı aynı iki sayıdır, küçük olan önce yazılır. Test senaryoları Tablo 1.3.8'de görülür. Üçüncü test sınır durumdur: iki sayı eşittir.

Sözde kod. Algoritma iki sayıyı okur ve tek bir karşılaştırma yapar. Birinci sayı ikinciden küçükse sayılar okunduğu sırayla, değilse ters sırayla yazılır.

Başla
    Yaz "Birinci tamsayıyı girin: "
    Oku birinciTamsayı
    Yaz "İkinci tamsayıyı girin: "
    Oku ikinciTamsayı
    Eğer birinciTamsayı < ikinciTamsayı ise
        Yaz birinciTamsayı, " ", ikinciTamsayı
    Değilse
        Yaz ikinciTamsayı, " ", birinciTamsayı
    Eğer Sonu
Bitir

Eğer … ise … Değilse … Eğer Sonu yapısı algoritmayı iki kola ayırır. Koşul doğruysa yalnız birinci kol, yanlışsa yalnız ikinci kol çalışır; iki kol hiçbir zaman birlikte çalışmaz. Eğer Sonu satırından sonra iki yol yeniden birleşir.

Elle izleme. Tablo 1.3.9 ilk iki testin izlemesidir. (4, 11) girdisinde koşul doğrudur ve ise kolu çalışır. (13, 11) girdisinde koşul yanlıştır; Değilse kolu önce ikinci sayıyı, yani küçük olanı yazar.

Eşit sayılar testi izlenmeden de sonuçlandırılabilir. (7, 7) için 7 < 7 koşulu yanlıştır ve Değilse kolu çalışır. Bu kol “ikinci, sonra birinci” yazar; iki sayı aynı olduğu için çıktı yine “7 7”dir. Koşulda < yerine ≤ kullanılsaydı eşit sayılarda ise kolu çalışırdı ve sonuç değişmezdi. Sınır durum testi burada bir hata yakalamaz ama algoritmanın eşit sayılarda da doğru olduğunu güvenceye alır.

Java kodu. Sözde kodun Java karşılığı aşağıdadır. Her Yaz bir System.out.print ya da println, her Oku bir nextInt() olmuştur.

import java.util.Scanner;

public class IkiSayiSirala {
    public static void main(String[] args) {
        Scanner tarayici = new Scanner(System.in);
        System.out.print("Birinci tamsayıyı girin: ");
        int birinci = tarayici.nextInt();
        System.out.print("İkinci tamsayıyı girin: ");
        int ikinci = tarayici.nextInt();
        if (birinci < ikinci) {
            System.out.println(birinci + " " + ikinci);
        } else {
            System.out.println(ikinci + " " + birinci);
        }
        tarayici.close();
    }
}

Program JDK 21 ile derlenip üç testle çalıştırıldığında sırasıyla “4 11”, “11 13” ve “7 7” yazar; üç test de geçer. Çıktının başında “Birinci tamsayıyı girin: İkinci tamsayıyı girin: ” iletileri de görünür. Kullanıcı bir terminalde sayıları yazdığında her sayının ardından Enter'a bastığı için bu iletiler ayrı satırlara düşer.

Java'da if ve else kollarının her biri tek bir deyim ya da süslü parantezlerle sarılmış bir bloktur. Yukarıdaki kodda tek satırlık kollar da süslü parantez içine alınmıştır. Bu bir zorunluluk değildir ama iyi bir alışkanlıktır. Parantezsiz bir kola sonradan ikinci bir satır eklenirse o satır koşuldan bağımsız olarak her zaman çalışır ve girintisi bunu gizler.

1.3.3.2Üç tam sayıyı sıralı yazdırma

Sorun tanımı. Girdi üç tam sayıdır; çıktı aynı sayıların küçükten büyüğe yazılmış hâlidir. Bu problem test senaryosu seçimini düşündürür. Üç sayı 3! = 6 farklı sırada gelebilir: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2 ve 3 2 1. Her sıra algoritmada farklı bir yoldan geçer; altı sıranın hepsi denenirse algoritmanın her kolu en az bir kez çalışmış olur. Bunlara eşit sayılı girdiler eklenir: 5 5 2 için beklenen çıktı 2 5 5'tir.

Fikir. Önce üç sayının en küçüğü bulunur ve yazılır. Geriye kalan iki sayı, iki tam sayı algoritmasıyla sıralanıp yazılır. En küçük sayı birinci, ikinci ya da üçüncü olabileceği için algoritmada üç ana kol vardır. Her ana kolun içinde de iki sayılık küçük bir karar bulunur.

Başla
    // İlk tamsayıyı kullanıcıdan al
    Yaz "Birinci tamsayıyı girin: "
    Oku birinciTamsayı
    // İkinci tamsayıyı kullanıcıdan al
    Yaz "İkinci tamsayıyı girin: "
    Oku ikinciTamsayı
    // Üçüncü tamsayıyı kullanıcıdan al
    Yaz "Üçüncü tamsayıyı girin: "
    Oku üçüncüTamsayı
    // Küçükten büyüğe sırala ve yazdır
    Eğer birinciTamsayı ≤ ikinciTamsayı ve
         birinciTamsayı ≤ üçüncüTamsayı ise
        Yaz birinciTamsayı
        Eğer ikinciTamsayı ≤ üçüncüTamsayı ise
            Yaz ikinciTamsayı, " ", üçüncüTamsayı
        Değilse
            Yaz üçüncüTamsayı, " ", ikinciTamsayı
        Eğer Sonu
    Değilse Eğer ikinciTamsayı ≤ birinciTamsayı ve
         ikinciTamsayı ≤ üçüncüTamsayı ise
        Yaz ikinciTamsayı
        Eğer birinciTamsayı ≤ üçüncüTamsayı ise
            Yaz birinciTamsayı, " ", üçüncüTamsayı
        Değilse
            Yaz üçüncüTamsayı, " ", birinciTamsayı
        Eğer Sonu
    Değilse
        Yaz üçüncüTamsayı
        Eğer birinciTamsayı ≤ ikinciTamsayı ise
            Yaz birinciTamsayı, " ", ikinciTamsayı
        Değilse
            Yaz ikinciTamsayı, " ", birinciTamsayı
        Eğer Sonu
    Eğer Sonu
Bitir

İlk koşul, birinci sayının iki sayıdan da küçük ya da onlara eşit olup olmadığını sorar. İki karşılaştırma “ve” bağlacıyla birleştirilmiştir: ikisi birden doğru olmalıdır. Bu kol çalışırsa birinci sayı yazılır, kalan ikinci ve üçüncü sayı iç içe bir kararla sıralanır. İlk koşul yanlışsa ikinci sayının en küçük olup olmadığına bakılır. O da yanlışsa en küçük sayı üçüncü sayıdır ve son kol çalışır. Son kolda ayrıca bir koşul yazılmasına gerek yoktur: ilk ikisi elendiyse geriye tek seçenek kalır.

Karşılaştırmalarda < yerine ≤ kullanılması eşit sayılar için gereklidir. Koşullar katı < ile yazılsın ve girdi 5 5 7 olsun. Birinci sayı için 5 < 5 yanlıştır; ikinci sayı için de 5 < 5 yanlıştır. Algoritma son kola düşer, en küçük sayı diye önce 7'yi yazar ve çıktı “7 5 5” olur. En küçük değer iki sayıda birden bulunduğunda hiçbir sayı “ötekilerden kesin küçük” değildir. ≤ ise “en küçük ya da en küçüklerden biri” anlamını doğrudan ifade eder ve bu girdide birinci kolu çalıştırır. 5 5 2 testi bu hatayı yakalamaz, çünkü orada en küçük sayı tektir. Hatayı ancak en küçük değerin tekrarlandığı 5 5 7 gibi bir test ortaya çıkarır.

Sözde kodun son satırında bir gözlem saklıdır. Aynı “iki sayıyı sırala ve yaz” işi üç ayrı yerde, yalnız değişken adları değiştirilerek tekrarlanmıştır. Tekrarlanan bir iş, bir fonksiyona (Java'da metoda) dönüştürülmeye çok uygundur. ikiSayiYaz(int a, int b) gibi bir metot yazılırsa üç kolun her biri tek satıra iner. Metotlar ayrı bir konudur; burada önemli olan, tekrarı fark etme alışkanlığıdır.

1.3.3.3Üç tam sayının Java kodu ve izlemesi

Sunumdaki tam Java programı aşağıdadır. Sözde koddaki üç ana kol if … else if … else zincirine, iç kararlar da tek satırlık if … else deyimlerine dönüşmüştür. “ve” bağlacı && olmuştur.

import java.util.Scanner;

public class UcSayiSirala {
    public static void main(String[] args) {
        Scanner tarayici = new Scanner(System.in);
        System.out.print("Üç tamsayı girin: ");
        int birinci = tarayici.nextInt();
        int ikinci = tarayici.nextInt();
        int ucuncu = tarayici.nextInt();
        if (birinci <= ikinci && birinci <= ucuncu) {
            System.out.print(birinci + " ");
            if (ikinci <= ucuncu) System.out.println(ikinci + " " + ucuncu);
            else                  System.out.println(ucuncu + " " + ikinci);
        } else if (ikinci <= birinci && ikinci <= ucuncu) {
            System.out.print(ikinci + " ");
            if (birinci <= ucuncu) System.out.println(birinci + " " + ucuncu);
            else                   System.out.println(ucuncu + " " + birinci);
        } else {
            System.out.print(ucuncu + " ");
            if (birinci <= ikinci) System.out.println(birinci + " " + ikinci);
            else                   System.out.println(ikinci + " " + birinci);
        }
        tarayici.close();
    }
}

Bu programda bir ayrıntı daha vardır. System.out.print("Üç tamsayı girin: ") tek bir ileti yazar ve üç nextInt() çağrısı art arda gelir. Scanner sayıları boşlukla ya da satır sonuyla ayrılmış parçalar olarak okur. Kullanıcı “7 3 5” yazıp bir kez Enter'a basabilir ya da her sayıdan sonra Enter'a basabilir; iki durumda da üç sayı doğru okunur.

Kod izleme. Girdi 7, 3, 5 olsun. Tablo 1.3.10 her koşulun değerini ve ekrana yazılanları adım adım verir.

Birinci adımda kısa devre davranışı görülür. birinci <= ikinci yanlış çıktığı anda && ifadesinin tamamı yanlış olacağı kesinleşir; Java birinci <= ucuncu karşılaştırmasını hiç yapmaz. Bu örnekte atlanan karşılaştırma zararsızdır. Ama sağ taraf bir metot çağrısı ya da sıfıra bölme riski taşıyan bir ifade olduğunda kısa devre bilinçli olarak kullanılır. b != 0 && a / b > 2 ifadesi b sıfırken bölmeyi hiç denemez.

Testler. Program altı sıranın her biri için “1 2 3” yazar. 5 5 2 için “2 5 5”, 7 3 5 için “3 5 7” yazar. Bu sonuçlar programın kendisi JDK 21'de çalıştırılarak elde edilmiştir. Ayrıca 5 2 5, 2 5 5, 5 5 7 ve 4 4 4 girdileri de denenmiş, hepsinde doğru sıra bulunmuştur. Aynı program katı < ile yeniden yazılıp denendiğinde 5 5 7 için “7 5 5” yazmıştır.

1.3.4Döngüyle algoritmalar

Karar yapıları algoritmanın hangi yoldan gideceğini belirler. Döngüler ise bir işi tekrar ettirir. Bu kesimdeki faktöriyel, Fibonacci ve üs alma algoritmaları aynı temel kalıba dayanır. Bir ya da iki değişken döngüden önce başlangıç değeri alır. Döngünün her turunda bu değişkenler güncellenir. Döngü bitince sonuç bu değişkenlerdedir. Kalıbın ayrıntıları algoritmadan algoritmaya değişir ve hatalar tam da bu ayrıntılarda çıkar.

1.3.4.1Faktöriyel

0! = 1 kuralı keyfî görünebilir. Ama hiç sayı çarpılmadığında elde kalan değer, çarpmanın etkisiz elemanı olan 1'dir. Hiç sayı toplanmadığında sonucun 0 olması gibi. Faktöriyel, n farklı nesnenin kaç farklı sırada dizilebileceğini verir. Üç sayıyı sıralama probleminde 3! = 6 sıranın denenmesi bu yüzdendir. Tablo 1.3.11 test senaryolarını verir.

Sözde kod.

Başla
    // Bir sayıyı gir
    Oku sayı
    // Sonucu saklamak için bir değişkeni başlat
    faktoriyel = 1
    // Faktöriyel hesabı için döngü
    Döngü i = 1'den başlayarak sayı'ya kadar
        faktoriyel = faktoriyel * i
    Döngü Sonu
    Yaz "Girilen sayının faktöriyeli: ", faktoriyel
Bitir

faktoriyel değişkeni bir biriktiricidir (accumulator). Döngünün her turunda sonucun bir parçası onun üzerine eklenir; burada “eklemek” çarpmak demektir. Biriktiricinin başlangıç değeri, yapılan işlemin etkisiz elemanıdır: çarpma için 1, toplama için 0. Biriktirici 0 ile başlatılsaydı her çarpım 0 olur ve sonuç hep 0 çıkardı.

Elle izleme. sayı = 5 için izleme Tablo 1.3.12'de görülür. Döngü değişkeni i 1'den başlar ve her turda bir artar. i 6 olduğunda 6 ≤ 5 koşulu yanlış çıkar ve döngü biter.

sayı = 0 sınır durumunda döngü koşulu ilk denemede yanlıştır (1 ≤ 0); gövde hiç çalışmaz ve biriktiricinin başlangıç değeri 1 yazılır. Bu, 0! = 1 kuralıyla uyuşur. Algoritmanın 0 için ayrı bir kola ihtiyacı yoktur; doğru başlangıç değeri sınır durumu kendiliğinden çözer.

Java kodu.

import java.util.Scanner;

public class Faktoriyel {
    public static void main(String[] args) {
        Scanner tarayici = new Scanner(System.in);
        System.out.print("Bir sayı girin: ");
        int sayi = tarayici.nextInt();
        long faktoriyel = 1;
        for (int i = 1; i <= sayi; i++) {
            faktoriyel = faktoriyel * i;
        }
        System.out.println("Girilen sayının faktöriyeli: " + faktoriyel);
        tarayici.close();
    }
}

Sözde koddaki Döngü i = 1'den başlayarak sayı'ya kadar satırı Java'da for (int i = 1; i <= sayi; i++) olmuştur. for başlığının üç parçası vardır: başlangıç (int i = 1), devam koşulu (i <= sayi) ve her turun sonunda yapılacak güncelleme (i++). Sözde koddaki “sayı'ya kadar” ifadesi sayının kendisini de kapsar; bu yüzden koşul < değil <= ile yazılır.

Neden long? Faktöriyel çok hızlı büyür. Java'da int 32 bitlik bir tam sayıdır ve en çok 2.147.483.647 değerini tutar. 12! = 479.001.600 bu sınırın altındadır; 13! = 6.227.020.800 ise üstündedir. Biriktirici int tanımlansaydı program 13 için hiçbir hata iletisi vermeden 1.932.053.504 yazardı. Bu sayı 6.227.020.800'den 2³² = 4.294.967.296 çıkarılarak elde edilen değerdir: int sınırı aşıldığında sayı başa sarar. Bu olaya taşma (overflow) denir. Java taşmayı denetlemez ve istisna fırlatmaz. long 64 bitliktir ve en çok 9.223.372.036.854.775.807 değerini tutar; 20! = 2.432.902.008.176.640.000 buna sığar. 21! için long da taşar ve program −4.249.290.049.419.214.848 gibi anlamsız bir negatif sayı yazar. Daha büyük faktöriyeller için java.math.BigInteger sınıfı kullanılır.

1.3.4.2Fibonacci serisi

Problem, kullanıcının girdiği n sayısı kadar terimi yazdırmaktır. Test senaryoları Tablo 1.3.13'te görülür. n = 1 ve n = 2 sınır durumlardır: bu durumlarda döngü hiç çalışmamalı, yalnız ilk terimler yazılmalıdır.

Başla
    // Kaç terim istendiğini gir
    Oku n
    // İlk iki Fibonacci sayısını başlat
    a = 0
    b = 1
    Eğer n ≥ 1 ise Yaz a
    Eğer n ≥ 2 ise Yaz b
    // Kalan terimleri hesapla
    Döngü i = 2'den başlayarak n − 1'e kadar
        sonuc = a + b
        a = b
        b = sonuc
        Yaz sonuc
    Döngü Sonu
Bitir

Algoritma bütün seriyi saklamaz; yalnız son iki terimi tutar. a sondan bir önceki, b son terimdir. Yeni terim sonuc = a + b ile hesaplanır. Ardından iki atama değerleri bir adım kaydırır: a = b eski son terimi “bir önceki” yapar, b = sonuc yeni terimi “son” yapar. İlk iki terim döngüden önce, n'in yeterince büyük olup olmadığı denetlenerek yazılır. Döngü i = 2'den n − 1'e kadar döner, yani n − 2 tur atar. Her tur bir terim yazdığı için toplam terim sayısı 2 + (n − 2) = n olur.

Elle izleme. n = 5 için izleme Tablo 1.3.14'te satır satır verilmiştir.

Kaydırmanın sırası. a = b; ve b = sonuc; satırlarının sırası önemlidir. Sıra değiştirilip önce b = sonuc yazılırsa b'nin eski değeri kaybolur ve a = b satırı a'ya yeni terimi koyar. Bu durumda a ile b eşitlenir ve seri 0 1 1 2 4 8 16 … gibi ikiye katlanan bir diziye döner. Atamalarda değeri ezilecek değişken her zaman en son güncellenir.

Java kodu.

import java.util.Scanner;

public class Fibonacci {
    public static void main(String[] args) {
        Scanner tarayici = new Scanner(System.in);
        System.out.print("Kaç terim? ");
        int n = tarayici.nextInt();
        long a = 0, b = 1, sonuc;
        if (n >= 1) System.out.print(a + " ");
        if (n >= 2) System.out.print(b + " ");
        for (int i = 2; i <= n - 1; i++) {
            sonuc = a + b;
            a = b;
            b = sonuc;
            System.out.print(sonuc + " ");
        }
        System.out.println();
        tarayici.close();
    }
}

Java kodu sözde kodla satır satır örtüşür. Tek fark, terim değişkenlerinin long seçilmesidir. Fibonacci terimleri de üstel hızla büyür. int kullanılırsa F(46) = 1.836.311.903 son doğru terim olur. F(47)'nin gerçek değeri 2.971.215.073'tür ve int sınırını aşar; program bunun yerine −1.323.752.223 yazar. Seriyi 0'dan sayarak F(0) = 0, F(1) = 1 kabul edildiğinde F(47), serinin 48. terimidir. Yani int'li program n = 47'ye kadar doğru çalışır; n = 48 olduğunda yazdığı son terim bozuktur. long ile F(92)'ye kadar doğru değerler elde edilir. Program n = 8 için “0 1 1 2 3 5 8 13”, n = 10 için “0 1 1 2 3 5 8 13 21 34” yazar.

1.3.4.3Üs alma

Bir sayının kuvveti, aynı sayının kendisiyle tekrar tekrar çarpılmasıdır: taban^üs = taban × taban × … × taban (üs kez). Ayrıca taban⁰ = 1'dir. Problem, negatif olmayan bir tam sayı üs için bu değeri hesaplamaktır. Tablo 1.3.15 test senaryolarını verir; üssün 0 olduğu satır sınır durumdur.

Başla
    // Bir sayıyı gir
    Oku taban
    // Bir üssü gir
    Oku üs
    // Sonucu saklamak için bir değişkeni başlat
    sonuc = 1
    // Üssü kullanarak sonucu hesapla
    Döngü i = 1'den başlayarak üs'e kadar
        sonuc = sonuc * taban
    Döngü Sonu
    Yaz "Sonuç: ", sonuc
Bitir

Bu algoritma faktöriyelle aynı kalıbı izler: biriktirici 1 ile başlar ve döngü her turda bir çarpma yapar. Fark, çarpanın her turda aynı olmasıdır. Faktöriyelde çarpan döngü değişkeni i'dir; burada hep taban'dır. i yalnız tur saymak için kullanılır. Üs 0 olduğunda döngü koşulu (1 ≤ 0) baştan yanlıştır, gövde hiç çalışmaz ve sonuç 1 kalır.

Tablo 1.3.16 taban = 3, üs = 4 için dört turu gösterir. Döngü tam üs kadar döner; yani algoritmanın yaptığı çarpma sayısı üsse eşittir. 2¹⁰ için 10 çarpma yapılır ve sonuç 1024'tür.

Java kodu.

import java.util.Scanner;

public class UsAl {
    public static void main(String[] args) {
        Scanner tarayici = new Scanner(System.in);
        System.out.print("Taban: ");
        int taban = tarayici.nextInt();
        System.out.print("Üs: ");
        int us = tarayici.nextInt();
        long sonuc = 1;
        for (int i = 1; i <= us; i++) {
            sonuc = sonuc * taban;
        }
        System.out.println("Sonuç: " + sonuc);
        tarayici.close();
    }
}

Java'da üs işleci yoktur. 2 ^ 10 yazmak derlenir ama üs almaz: ^ bit düzeyinde “özel veya” işlecidir ve 2 ^ 10 ifadesinin değeri 8'dir. Hazır bir yol olarak Math.pow(taban, us) metodu vardır; ancak bu metot double döndürür. Math.pow(3, 4) 81 değil 81.0 verir ve çok büyük tam sayılarda double'ın sınırlı duyarlılığı yüzünden son basamaklar yanlış olabilir. Tam sayı kuvvetleri için yukarıdaki döngü güvenilir bir yoldur. Taşma burada da geçerlidir: sonuc int seçilseydi 2³¹ için −2.147.483.648, 2³² için 0 elde edilirdi. Program long ile 2³¹ için doğru değeri, 2.147.483.648'i yazar.

1.3.5Metin işleme ve bayrak

Bu kesimin iki algoritması yeni araçlar getirir. Palindrom kontrolü sayılarla değil metinle çalışır ve Java'da metinlerin nasıl karşılaştırıldığı sorusunu gündeme getirir. Asal sayı kontrolü ise bir döngünün sonucunu tek bir mantıksal değişkende toplayan bayrak kalıbını ve döngüden erken çıkmayı tanıtır.

1.3.5.1Palindrom kontrolü

Tanımdaki son cümle algoritmaya bir ön işlem ekler. “Ey Edip Adana'da pide ye” cümlesi harf harf tersine çevrildiğinde “ey edip ad'anadA pidE yE” olur ve ilk hâliyle aynı değildir. Büyük harfler, boşluklar ve kesme işareti karşılaştırmayı bozar. Bu yüzden metin önce temizlenir: bütün harfler küçük harfe çevrilir, harf ve rakam dışındaki karakterler atılır. Temizlenmiş metin “eyedipadanadapideye” olur ve bu metin gerçekten tersine eşittir.

“Kayak” testi büyük harfin temizlendiğini, “Kitap” testi palindrom olmayan bir girdinin doğru reddedildiğini, son test de boşluk ve noktalamanın atıldığını sınar (Tablo 1.3.17). Sözde kod üç adımdan oluşur: temizle, ters çevir, karşılaştır.

Başla
    // Bir kelime veya cümlenin girilmesini iste
    Oku girdiMetin
    // Girdiyi temizle: küçük harf, boşluk ve noktalama yok
    temizMetin = Temizle(girdiMetin)
    // Temizlenmiş girdiyi ters çevir
    tersGirdi = TersÇevir(temizMetin)
    // Temizlenmiş girdi ile ters girdiyi karşılaştır
    Eğer temizMetin = tersGirdi ise
        Yaz "Girilen metin bir palindromdur."
    Değilse
        Yaz "Girilen metin bir palindrom değildir."
    Eğer Sonu
Bitir

Temizle ve TersÇevir sözde kodda tek satırlık işlemler olarak yazılmıştır. Her biri aslında kendi başına küçük bir algoritmadır. Sözde kodun bu esnekliği yararlıdır: ana fikir önce kurulur, alt işlerin ayrıntısı sonraya bırakılır.

Elle izleme. “abcba” ve “Kitap” girdileri için izleme Tablo 1.3.18'de görülür.

Java kodu. Aşağıdaki programda temizleme işi temizle adlı ayrı bir metoda taşınmıştır. Ters çevirme için Java'nın hazır StringBuilder sınıfı kullanılır.

import java.util.Locale;
import java.util.Scanner;

public class Palindrom {
    public static void main(String[] args) {
        Scanner tarayici = new Scanner(System.in);
        System.out.print("Bir kelime veya cümle girin: ");
        String girdiMetin = tarayici.nextLine();
        String temizMetin = temizle(girdiMetin);
        String tersGirdi = new StringBuilder(temizMetin).reverse().toString();
        if (temizMetin.equals(tersGirdi)) {
            System.out.println("Girilen metin bir palindromdur.");
        } else {
            System.out.println("Girilen metin bir palindrom değildir.");
        }
        tarayici.close();
    }

    static String temizle(String metin) {
        String kucuk = metin.toLowerCase(Locale.forLanguageTag("tr"));
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < kucuk.length(); i++) {
            char c = kucuk.charAt(i);
            if (Character.isLetterOrDigit(c)) sb.append(c);
        }
        return sb.toString();
    }
}

nextLine() satırın tamamını okur. Burada next() kullanılsaydı yalnız ilk kelime, “Ey”, okunurdu; çünkü next() boşlukta durur. Cümle girilebilecek her yerde nextLine() gerekir.

new StringBuilder(temizMetin).reverse().toString() üç işi zincir hâlinde yapar. Önce metnin değiştirilebilir bir kopyası oluşturulur, sonra bu kopya yerinde ters çevrilir, en son yeniden String'e dönüştürülür. Java'da String nesneleri değiştirilemez; bir metni ters çevirmek, birleştirmek ya da harflerini değiştirmek her zaman yeni bir nesne üretir. StringBuilder ise değiştirilebilir bir karakter dizisidir ve bu tür işler için tasarlanmıştır.

temizle metodu metni küçük harfe çevirir, sonra karakterleri tek tek dolaşır. charAt(i) metodu i. konumdaki karakteri verir; konumlar 0'dan başlar ve length() - 1'de biter. Character.isLetterOrDigit(c) karakterin bir harf ya da rakam olup olmadığını söyler. Türkçe harfler de harf sayılır; boşluk, virgül ve kesme işareti sayılmaz. Uygun karakterler bir StringBuilder'a eklenir ve sonuç döndürülür.

Metin karşılaştırma: equals ve ==. Programın en önemli satırı if (temizMetin.equals(tersGirdi)) satırıdır. Bu satır temizMetin == tersGirdi biçiminde yazılırsa program derlenir, çalışır ama “abcba” için bile “palindrom değildir” der. Sebep, == işlecinin nesneler için ne anlama geldiğidir. int, double, char gibi temel tiplerde == değerleri karşılaştırır. String ise bir nesnedir ve String tipindeki bir değişken nesnenin kendisini değil, bellekteki yerini, yani nesneye bir başvuruyu (reference) tutar. == iki başvurunun aynı nesneyi gösterip göstermediğine bakar. tersGirdi, StringBuilder'ın yeni ürettiği ayrı bir nesnedir; içeriği temizMetin'le aynı olsa da başka bir nesnedir ve == false verir. İçerik karşılaştırması equals metoduyla yapılır.

Bu hata bir de sinsi bir biçimde ortaya çıkar. Kaynak kodda doğrudan yazılmış iki aynı metin, String a = "abc"; String b = "abc";, Java'da tek bir nesne olarak saklanır ve a == b true verir. Programcı küçük bir denemede =='nin çalıştığını görür ve yanlış bir güvene kapılır. Kullanıcıdan okunan ya da çalışma sırasında üretilen metinlerde ise == hemen her zaman false verir. JDK 21'de yapılan denemede iki sabit metin için true, “abcba” ile StringBuilder'ın ürettiği tersi için false elde edilmiştir. Kural basittir: metinler her zaman equals ile karşılaştırılır.

Testler. Program JDK 21'de dört testle çalıştırılmıştır: “abcba”, “Kayak” ve “Ey Edip Adana'da pide ye” için “Girilen metin bir palindromdur.”, “Kitap” için “Girilen metin bir palindrom değildir.” yazar.

1.3.5.2Asal sayı kontrolü

Tanım iki sınır durumu açıkça dışarıda bırakır: 0 ve 1 asal değildir. 2 ise hem en küçük hem tek çift asal sayıdır. Test senaryoları bu durumları ve hem asal hem bileşik sıradan sayıları içerir (Tablo 1.3.19).

Başla
    // Bir sayıyı gir
    Oku sayı
    // Bayrak (flag): 0 ve 1 asal değildir
    Eğer sayı < 2 ise asalMi = False
    Değilse asalMi = True
    // 2'den sayının yarısına kadar bölenleri dene
    Döngü bölen = 2'den başlayarak sayı / 2'ye kadar
        Eğer sayı % bölen = 0 ise
            // Bölünüyorsa sayı asal değildir
            asalMi = False
            Döngüyü Kır
        Eğer Sonu
    Döngü Sonu
    // Bayrağa göre sonucu yazdır
    Eğer asalMi = True ise
        Yaz sayı, " bir asal sayıdır."
    Değilse
        Yaz sayı, " bir asal sayı değildir."
    Eğer Sonu
Bitir

Algoritma üç fikre dayanır.

Bayrak. asalMi değişkeni bir bayraktır (flag): yalnız doğru ya da yanlış değer alan ve bir durumun gerçekleşip gerçekleşmediğini kaydeden değişken. Başta sayının asal olduğu varsayılır ve bayrak kaldırılır. Döngü bir bölen bulursa bayrak indirilir. Döngü bittiğinde bayrağın durumu sonucu söyler. Bayrak kalıbı “hepsi için doğru mu?” türündeki soruların genel çözümüdür: iyimser bir varsayımla başlanır, tek bir karşı örnek varsayımı çürütür.

Kalan ve erken çıkış. sayı % bölen = 0 koşulu bölmenin kalansız olup olmadığını sınar: 21 % 3 = 0 olduğu için 3, 21'i tam böler. Bir bölen bulunduğu anda sayının asal olmadığı kesinleşir; geri kalan bölenleri denemek gereksizdir. Döngüyü Kır (Java'da break) döngüden hemen çıkar.

Döngünün sınırı. Bölenler 2'den sayı / 2'ye kadar denenir. Sayının kendisi hariç hiçbir böleni sayının yarısından büyük olamaz. Bir d böleni sayı / 2'den büyükse sayı / d bölümü 2'den küçük olur, yani 1 olur; bu da d = sayı demektir. sayı / 2 tam sayı bölmesidir: 7 / 2 = 3. 0 ve 1 için sınır 0'dır; döngü hiç çalışmaz ve sonucu ilk satırdaki Eğer sayı < 2 kararı belirler. 2 ve 3 için sınır 1'dir; döngü yine çalışmaz, bayrak doğru kalır ve iki sayı da doğru biçimde asal bulunur.

Elle izleme. Tablo 1.3.20 7 ve 21 için izlemeyi verir.

Java kodu.

import java.util.Scanner;

public class AsalMi {
    public static void main(String[] args) {
        Scanner tarayici = new Scanner(System.in);
        System.out.print("Bir sayı girin: ");
        int sayi = tarayici.nextInt();
        boolean asalMi = true;
        if (sayi < 2) asalMi = false;
        for (int bolen = 2; bolen <= sayi / 2; bolen++) {
            if (sayi % bolen == 0) {
                asalMi = false;
                break;
            }
        }
        if (asalMi) {
            System.out.println(sayi + " bir asal sayıdır.");
        } else {
            System.out.println(sayi + " bir asal sayı değildir.");
        }
        tarayici.close();
    }
}

Java'da bayrak boolean tipinde bir değişkendir ve değerleri true ile false'tur. Sözde koddaki Eğer asalMi = True ise satırı Java'da if (asalMi) biçiminde yazılmıştır. asalMi zaten bir boolean olduğu için onu true ile karşılaştırmaya gerek yoktur. if (asalMi == true) de doğru çalışır ama gereksiz uzundur. if (asalMi = true) ise bir atamadır: derlenir, asalMi'yi true yapar ve her zaman “asal” sonucunu verir. boolean değişkenlerde tek eşittir hatası derleyiciden kaçar.

break deyimi içinde bulunduğu en yakın döngüyü sonlandırır. Program akışı döngüden sonraki ilk satıra, burada if (asalMi) satırına geçer. break kullanılmasaydı sonuç değişmezdi; bayrak bir kez indirildikten sonra yeniden kaldırılmaz. Ama döngü gereksiz yere 4'ten 10'a kadar yedi bölen daha denerdi.

Kaç bölen denenir? Programın denediği bölen sayıları sayaçlı bir kopyayla JDK 21'de ölçülmüştür. 7 için 2 bölen (2, 3) denenir ve sayı asal bulunur. 21 için 2 bölen denenir; 3'te döngü kırılır. 25 için 4 bölen (2, 3, 4, 5) denenir. 49 için 6 bölen denenir ve 7'de bölen bulunur. 97 asaldır; döngü 2'den 48'e kadar 47 bölenin hepsini dener. Asal sayılar algoritmanın en kötü durumudur, çünkü erken çıkış hiç gerçekleşmez.

Daha iyi bir sınır. Sınır sayı / 2 yerine √sayı alınabilir. Bir sayı a × b biçiminde iki çarpana ayrılıyorsa çarpanlardan biri √sayı'dan büyük değildir. Bu yüzden √sayı'ya kadar bölen bulunamazsa sayı asaldır. 97 için bu sınır 9'dur ve 47 yerine 8 bölen denenir. Java'da koşul bolen * bolen <= sayi biçiminde yazılır; böylece karekök almaya ve ondalıklı sayılara gerek kalmaz. Büyük sayılarda fark çarpıcıdır: bir milyar civarındaki bir asal için sayı / 2 sınırı yaklaşık 500 milyon, √sayı sınırı yaklaşık 31.600 deneme demektir.

1.3.6Arama algoritmaları

1.3.6.1Arama problemi

Arama, bir koleksiyonun içinde belirli bir öğenin bulunup bulunmadığını ve bulunuyorsa nerede olduğunu sorgular. Veri işleyen hemen her programın temel işlemlerinden biridir. Kütüphanede bir kitabın yeri, bir web sitesinde belirli bir sayfa, veri tabanında bir kayıt, telefon rehberinde bir isim hep bir aramayla bulunur. Problemi soyut olarak tanımlamak için bir sepet ve bir elma düşünülsün.

İndis döndürmek, true/false döndürmekten daha fazla bilgi verir: öğenin varlığı da konumu da tek bir sayıyla bildirilir. Java dizilerinde geçerli indisler 0'dan length − 1'e kadardır; −1 hiçbir zaman geçerli bir indis olamayacağı için “bulunamadı” anlamında güvenle kullanılır. Bu notta üç arama yöntemi incelenir (Şekil 1.3.11). Rastgele arama her adımda rastgele bir öğeye bakar. Doğrusal arama öğelere baştan sona sırayla bakar. İkili arama ortadaki öğeye bakar ve her adımda arama alanının yarısını eler.

Yöntemleri karşılaştırmanın ölçüsü karşılaştırma sayısıdır: aranan öğenin dizideki bir öğeyle kaç kez karşılaştırıldığı. Bu sayı makineden, dilden ve derleyiciden bağımsızdır. Bir yöntemin bir milyon öğede kaç karşılaştırma yaptığı biliniyorsa hangi bilgisayarda çalışırsa çalışsın ötekilerden ne kadar hızlı olacağı da kestirilebilir.

1.3.6.2Rastgele arama

Rastgele arama (random search) koleksiyondaki öğeleri rastgele bir sırayla kontrol eder. Her adımda rastgele bir öğe seçilir ve aranan öğeyle karşılaştırılır. Eşleşme varsa arama biter; yoksa yeni bir rastgele öğe seçilir. Sözde kod dört adımdır:

1. Rastgele bir öğe seç.
2. Seçilen öğeyi hedefle karşılaştır.
3. Hedef bulunduysa işlemi sonlandır.
4. Bulunamadıysa adımları tekrarla.

Şekil 1.3.12 dokuz öğeli sırasız bir dizide 48'in aranmasını gösterir. Rastgele seçilen öğeler sırasıyla 23, 42, 7 ve 48'dir; arama dördüncü denemede biter. Aynı arama yeniden çalıştırılsa başka öğeler seçilir ve deneme sayısı da değişir.

Java kodu. Aşağıdaki metot java.util.Random sınıfıyla rastgele indisler üretir. Metodun derlenmesi için dosyanın başında import java.util.Random; satırı bulunmalıdır.

static int rastgeleAra(int[] dizi, int hedef, int denemeSiniri) {
    Random rastgele = new Random();
    for (int deneme = 1; deneme <= denemeSiniri; deneme++) {
        int i = rastgele.nextInt(dizi.length);   // 0 … length − 1
        if (dizi[i] == hedef) {
            return i;
        }
    }
    return -1;   // sınır doldu; öğe yok ya da şans yaver gitmedi
}

rastgele.nextInt(dizi.length) 0 ile dizi.length - 1 arasında, iki uç dahil, rastgele bir tam sayı üretir; bu aralık tam olarak dizinin geçerli indisleridir. Metodun üçüncü parametresi denemeSiniri'dir. Rastgele aramanın en büyük zaafı, hedef dizide yoksa durmamasıdır: her deneme başarısız olur ve döngü sonsuza dek döner. Bu, algoritmanın sonluluk özelliğini bozar. Deneme sınırı bu sorunu çözer ama yeni bir belirsizlik getirir. Sınır dolduğunda −1 döner. Bu −1'in “öğe yok” mu, yoksa “öğe var ama şans yaver gitmedi” mi demek olduğu bilinemez.

Kaç deneme gerekir? Dizide n öğe ve tek bir hedef varsa her denemenin başarı olasılığı 1/n'dir. Denemeler birbirinden bağımsız olduğu için ortalama deneme sayısı n'dir. Dokuz öğeli dizide 48'in aranması JDK 21'de 200.000 kez tekrarlanmış ve ortalama 9,02 deneme ölçülmüştür. n denemede hiç bulamama olasılığı (1 − 1/n)ⁿ'dir. n = 9 için bu değer yaklaşık 0,346'dır: her üç aramadan biri, öğe sayısı kadar denemeden sonra hâlâ sonuçsuzdur. Aynı öğe tekrar tekrar seçilebildiği için doğrusal aramanın en kötü durumundan bile daha fazla deneme gerekebilir.

Rastgele aramanın avantajları basitliği ve verinin sırasından bağımsız olmasıdır. Dezavantajları ağırdır: kesin bir sonuç garantisi yoktur, aynı öğeyi defalarca seçebilir ve hedef yoksa ancak bir deneme sınırıyla durdurulabilir. Bu yöntem pratikte tek başına bir arama aracı olarak pek kullanılmaz. Değeri başka bir yerdedir: arama uzayı denenemeyecek kadar büyük olduğunda, örneğin bir optimizasyon probleminde, rastgele örnekleme işe yarar bir başlangıç noktasıdır.

1.3.6.3Doğrusal arama

Doğrusal arama (linear search) bir koleksiyonda öğe aramanın en temel yoludur. Öğeler ilkinden başlanarak sırayla hedefle karşılaştırılır. Eşleşme bulunursa konum döndürülür. Listenin sonuna gelinmişse öğe yoktur. Öğelerin sıralı olması gerekmez.

1. Öğeleri bir diziye koy.
2. İlk öğeden başlayarak sırayla hedef öğeyle karşılaştır.
3. Hedef bulunursa işlemi sonlandır ve konumunu döndür.
4. Bulunmazsa bir sonraki öğeye geç.
5. Listenin sonuna kadar devam et; sona gelindiyse öğe yoktur.

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

Metot dizinin her indisini sırayla dener. dizi[i] == hedef doğru olduğunda return i; hem metodu hem döngüyü anında bitirir; break'e gerek yoktur. Döngü hiçbir eşleşme bulmadan biterse akış son satıra ulaşır ve −1 döner. i < dizi.length koşulu dizinin son geçerli indisi olan length - 1'de durur.

İzleme. [42, 17, 8, 23, 31] dizisinde 23 aranırken 42, 17 ve 8 eşleşmez; dördüncü karşılaştırmada dizi[3] = 23 bulunur ve 3 döner (Şekil 1.3.13). Tablo 1.3.21 aynı dizide başka hedefler için karşılaştırma sayılarını verir. Değerler sayaçlı bir kopya JDK 21'de çalıştırılarak doğrulanmıştır.

Maliyet. n öğeli bir dizide en iyi durum hedefin ilk öğe olmasıdır: 1 karşılaştırma. En kötü durum hedefin son öğe olması ya da hiç olmamasıdır: n karşılaştırma. Hedef dizide varsa ve her konumda bulunma olasılığı eşitse ortalama (1 + 2 + … + n) / n = (n + 1) / 2 karşılaştırma yapılır. İş n ile doğru orantılı büyür: dizi iki katına çıkarsa en kötü durumdaki iş de iki katına çıkar. Algoritmanın adı bu doğrusal büyümeden gelir.

Doğrusal arama basit ve anlaşılırdır, sırasız veride çalışır ve sonucu kesindir: öğe varsa mutlaka bulunur. Küçük koleksiyonlarda en iyi seçimdir. Dezavantajı büyük koleksiyonlarda yavaş kalmasıdır. Bir milyon öğeli bir dizide olmayan bir öğe için bir milyon karşılaştırma gerekir.

1.3.6.4İkili arama

İkili arama (binary search), sıralı veride öğe bulmanın hızlı ve etkili bir yoludur. Fikir, bir sözlükte kelime aramaya benzer. Sözlük ortadan açılır; aranan kelime açılan sayfadan önce geliyorsa sol yarıya, sonra geliyorsa sağ yarıya geçilir. Her adımda bakılacak sayfa sayısı yarıya iner.

1. Ortadaki öğeyi seç ve hedefle karşılaştır.
2. Hedef bulunursa işlemi sonlandır.
3. Hedef ortadakinden küçükse sol yarıya odaklan.
4. Hedef ortadakinden büyükse sağ yarıya odaklan.
5. Hedef bulunana ya da arama alanı tükenene kadar tekrarla.

Üçüncü ve dördüncü adımlar dizinin sıralı olmasına dayanır. Hedef ortadaki öğeden küçükse ve dizi küçükten büyüğe sıralıysa, sağ yarıdaki her öğe ortadakinden büyük ya da ona eşittir; hedef orada olamaz. Bu çıkarım ancak sıralı dizide geçerlidir.

static int ikiliAra(int[] dizi, int hedef) {
    int alt = 0, ust = dizi.length - 1;
    while (alt <= ust) {
        int orta = (alt + ust) / 2;
        if (dizi[orta] == hedef) {
            return orta;
        } else if (hedef < dizi[orta]) {
            ust = orta - 1;
        } else {
            alt = orta + 1;
        }
    }
    return -1;
}

Arama alanı alt ve ust indisleri arasındaki bölgedir, iki uç dahil. Başta bütün dizidir. Her turda orta = (alt + ust) / 2 hesaplanır. Bu tam sayı bölmesidir; alanın öğe sayısı çiftse iki ortadan soldakini seçer. Hedef ortadaki öğeye eşitse indis döner. Küçükse ust = orta - 1 ile sağ yarı ve orta öğe elenir. Büyükse alt = orta + 1 ile sol yarı ve orta öğe elenir. Orta öğe iki durumda da yeniden incelenmez; zaten hedefle karşılaştırılmıştır. Döngü koşulu alt <= ust'tür. alt, ust'ü geçtiğinde arama alanı boşalmıştır ve öğe yoktur.

İzleme. Sıralı [7, 12, 23, 31, 42, 48, 55, 64, 77] dizisinde 48 aransın. Tablo 1.3.22 her turdaki değişkenleri, Şekil 1.3.14 üç anı gösterir.

Aynı dizide 12 için iki karşılaştırma yeter (42 → 12). 77 için dört karşılaştırma gerekir (42 → 55 → 64 → 77). Dokuz öğeli bu dizide hiçbir arama dört karşılaştırmayı aşmaz. Bu sayılar sayaçlı bir kopyanın JDK 21'de çalıştırılmasıyla doğrulanmıştır.

Sırasız dizide ikili arama. İkili aramanın tehlikeli yanı, sıralı olmayan bir dizide hata vermeden yanlış sonuç üretmesidir. [77, 42, 64, 12, 23, 55, 7, 48, 31] dizisinde 77 aransın. İlk ortadaki öğe 23'tür; 77 > 23 olduğu için sağ yarıya geçilir. Sonra 7'ye, 48'e ve 31'e bakılır; 77 hepsinden büyük olduğu için hep sağa gidilir. Sonunda alan boşalır ve −1 döner. Oysa 77 dizinin ilk öğesidir. Metot dizinin sıralı olup olmadığını denetlemez, uyarı da vermez. Bu dizinin dokuz öğesinin her biri ayrı ayrı arandığında yalnız ikisi (23 ve 48) bulunur. Bulunanlar da şans eseri orta konumlara denk gelmiştir. Sıralı olmayan veride sonuç rastlantıya kalır; bu yüzden “sırasız dizide yanlış sonuç verebilir” demek daha doğrudur.

Kaç karşılaştırma? Her tur arama alanını yarıya indirir. n öğeli bir alan bir turdan sonra en çok n/2, iki turdan sonra en çok n/4 öğeye iner. Alan tek öğeye inene kadar yaklaşık log₂ n tur geçer; son öğeye de bir kez bakılır. En kötü durumdaki karşılaştırma sayısı ⌊log₂ n⌋ + 1'dir. 1.000.000 öğe için log₂ 1.000.000 ≈ 19,93; tabanı alınıp bir eklenince 20 karşılaştırma bulunur. Doğrusal arama aynı dizide bir milyon karşılaştırma yapabilir.

Java'nın hazır ikili araması. java.util.Arrays sınıfındaki Arrays.binarySearch(dizi, hedef) metodu aynı algoritmayı uygular. Öğe bulunursa indisini döndürür. Bulunamazsa −1 yerine -(eklemeNoktası) - 1 biçiminde negatif bir sayı döndürür. Ekleme noktası, öğenin sırayı bozmadan diziye gireceği indistir. [7, 12, …, 77] dizisinde 50 için ekleme noktası 6 olduğundan metot −7 döndürür. Sonucun negatif olması “bulunamadı” demektir. Bu metot da dizinin sıralı olduğunu varsayar; belgesi sırasız dizi için sonucun tanımsız olduğunu açıkça yazar.

1.3.6.5Doğrusal ve ikili aramanın karşılaştırması

İki yöntemin farkı küçük dizilerde önemsizdir, büyük dizilerde ise çarpıcıdır (Tablo 1.3.23).

Tablonun en öğretici satır çifti 1.000.000 ile 2.000.000'dur. Dizi iki katına çıkınca doğrusal aramanın işi de iki katına çıkar. İkili aramanın işi ise yalnız bir artar, çünkü fazladan bir tur iki katına çıkan alanı yeniden eski boyutuna indirir.

Bu üstünlüğün bir bedeli vardır: veri sıralı olmalıdır ve sıralamanın da bir maliyeti vardır. Tek bir arama için bir diziyi önce sıralayıp sonra ikili aramak, doğrudan doğrusal aramaktan daha pahalıdır. İkili arama, aynı veri üzerinde çok sayıda arama yapılacaksa, ya da veri zaten sıralı tutuluyorsa kazançlıdır. Telefon rehberi ve sözlük bu yüzden alfabetik sıradadır: bir kez sıralanırlar, milyonlarca kez aranırlar.

1.3.7Sıralama algoritmaları

1.3.7.1Sıralama problemi

Sıralama, bir koleksiyondaki öğeleri belirli bir kurala göre düzenler. Sayılar için kural genellikle küçükten büyüğe (artan) ya da büyükten küçüğe (azalan) sıradır; metinler için alfabetik sıradır. Sıralama, veri analizinin ve aramanın temel bir ön adımıdır. Sıralı bir dizide en küçük ve en büyük öğe uçlardadır, ortanca değer ortadadır, tekrar eden öğeler yan yanadır. En önemlisi, ikili arama yalnız sıralı dizide çalışır.

Bu notta üç basit yöntem incelenir. Rastgele sıralama (karıştırma) öğeleri rastgele bir düzene sokar ve sıralamayı garanti etmez; sıralamanın tersi bir iştir ama aynı takas işlemini kullanır. Seçimli sıralama en küçük öğeyi seçip başa koyar. Kabarcık sıralaması komşu öğeleri karşılaştırıp büyüğü sona taşır. Daha hızlı yöntemler de vardır: birleştirmeli sıralama, hızlı sıralama. Java'nın hazır Arrays.sort metodu bunların geliştirilmiş biçimlerini kullanır.

Üç yöntemin ortak yapı taşı takastır (swap): dizideki iki öğenin yer değiştirmesi. Java'da iki değişkenin değerini doğrudan değiştiren tek bir işlem yoktur; takas geçici bir değişkenle üç adımda yapılır.

int gecici = dizi[i];
dizi[i] = dizi[j];
dizi[j] = gecici;

İlk satır dizi[i]'nin değerini güvenli bir yere kopyalar. İkinci satır dizi[i]'nin üzerine dizi[j]'yi yazar; dizi[i]'nin eski değeri artık yalnız gecici'dedir. Üçüncü satır bu değeri dizi[j]'ye koyar.

1.3.7.2Rastgele sıralama (karıştırma)

Rastgele sıralama ya da karıştırma (shuffle), bir koleksiyonun öğelerini rastgele bir düzene sokar. Kart destesini karıştırmak, sınav sorularının sırasını her öğrenci için değiştirmek, bir program için rastgele test verisi üretmek tipik kullanım alanlarıdır. Bazı algoritmalar da girdiyi önce karıştırarak kötü durumlardan kaçınır. Hızlı sıralama, girdisi önceden karıştırıldığında özel olarak hazırlanmış kötü girdilerden etkilenmez.

Şekil 1.3.16 [42, 17, 8, 23, 31] dizisinin art arda üç kez karıştırılmasının ilk ve son durumunu gösterir. Birinci karıştırma [31, 17, 42, 8, 23], ikincisi [8, 23, 31, 42, 17], üçüncüsü [8, 23, 17, 31, 42] üretmiştir. Son dizi sıraya yaklaşmıştır ama hâlâ sıralı değildir. Karıştırma sıralamayı garanti etmez; amacı da bu değildir.

Doğru karıştırma. Karıştırmanın iyi yapılmış sayılması için her dizilişin eşit olasılıkla çıkması gerekir. n öğenin n! farklı dizilişi vardır; her birinin olasılığı 1/n! olmalıdır. Bu koşulu sağlayan klasik yöntem Fisher–Yates karıştırmasıdır. Dizinin sonundan başlanır. Her i konumu için 0 ile i arasından, iki uç dahil, rastgele bir j seçilir ve dizi[i] ile dizi[j] takas edilir. Sonra bir sola geçilir.

static void karistir(int[] dizi) {
    Random rastgele = new Random();
    for (int i = dizi.length - 1; i > 0; i--) {
        int j = rastgele.nextInt(i + 1);   // 0 … i
        int gecici = dizi[i];
        dizi[i] = dizi[j];
        dizi[j] = gecici;
    }
}

Son konuma yerleşecek öğe n öğenin her birinden eşit olasılıkla seçilir. Sondan ikinci konuma kalan n − 1 öğeden biri gelir ve bu böyle sürer. Toplam seçenek sayısı n × (n − 1) × … × 2 = n!'dir ve her seçim dizisi farklı bir dizilişe karşılık gelir. Yöntem tam n − 1 takas yapar. Kod JDK 21'de [1, 2, 3] dizisiyle 600.000 kez çalıştırılmıştır. Altı dizilişin her biri 99.651 ile 100.509 arasında gözlenmiştir; beklenen değer 100.000'dir. Java'da aynı iş hazır olarak Collections.shuffle(liste) metoduyla yapılır; bu metot da Fisher–Yates yöntemini kullanır.

Karıştırarak sıralamak. “Dizi sıralanana kadar karıştır” diye bir sıralama yöntemi tasarlanabilir. Bu yönteme bogosort denir ve umutsuz derecede yavaştır. 10 öğenin 10! = 3.628.800 farklı dizilişinden yalnız biri sıralıdır. Her karıştırmanın sıralı diziyi üretme olasılığı yaklaşık üç buçuk milyonda birdir. Ortalama olarak 3,6 milyon karıştırma ve her birinden sonra bir sıralılık denetimi gerekir. 20 öğe için bu sayı 2,4 × 10¹⁸'e çıkar.

1.3.7.3Seçimli sıralama

Seçimli sıralama (selection sort) öğeleri karşılaştırarak sıralayan basit bir algoritmadır. Dizinin sıralanmamış kısmındaki en küçük öğe bulunur ve bu kısmın başına taşınır. Sonra sıralanmamış kısım bir öğe kısalır ve işlem tekrarlanır.

1. Koleksiyondaki en küçük öğeyi bul.
2. Bu öğeyi koleksiyonun başına taşı (ilk öğeyle yer değiştir).
3. Geri kalan kısımdaki en küçük öğeyi bul.
4. Onu ikinci konuma taşı.
5. Bu adımları koleksiyonun sonuna kadar tekrarla.

static void secimliSirala(int[] dizi) {
    int n = dizi.length;
    for (int i = 0; i < n - 1; i++) {
        int enKucuk = i;
        for (int j = i + 1; j < n; j++) {
            if (dizi[j] < dizi[enKucuk]) enKucuk = j;
        }
        int gecici = dizi[i];
        dizi[i] = dizi[enKucuk];
        dizi[enKucuk] = gecici;
    }
}

Dış döngünün i değişkeni, en küçük öğenin yerleşeceği konumdur. i'nin solundaki öğeler sıralıdır ve kesin yerlerindedir; i ve sağı henüz sıralanmamıştır. İç döngü i + 1'den dizinin sonuna kadar dolaşır ve şimdiye kadar görülen en küçük öğenin indisini enKucuk'ta tutar. Bu, bir dizide en küçük öğeyi bulmanın klasik kalıbıdır: ilk öğe aday kabul edilir, daha küçük bir öğe görüldükçe aday değiştirilir. İç döngü bitince dizi[i] ile dizi[enKucuk] takas edilir. Dış döngü n - 1'de durur, çünkü son öğe tek başına kaldığında zaten yerindedir.

Adım adım. [64, 25, 12, 22, 11, 36, 48] dizisi sıralansın. Tablo 1.3.25 her dış turu, Şekil 1.3.17 ilk adımın öncesini ve sonrasını ve son durumu gösterir.

Dördüncü adımda en küçük öğe zaten sıralanmamış kısmın başındadır; enKucuk ile i eşittir. Kod bu durumda da takas satırlarını çalıştırır: öğe kendisiyle yer değiştirir ve dizi değişmez. Bu yüzden kodun yaptığı takas sayısı her zaman n − 1'dir; bu örnekte 6. Gerçekten yer değiştiren takasların sayısı ise 5'tir. İstenirse takastan önce if (enKucuk != i) denetimi eklenebilir.

Maliyet. İç döngü birinci turda n − 1, ikinci turda n − 2, son turda 1 karşılaştırma yapar. Toplam karşılaştırma sayısı

(n − 1) + (n − 2) + … + 2 + 1 = n(n − 1)/2

olur. 7 öğe için 7 · 6 / 2 = 21; tablodaki karşılaştırmaların toplamı da 6 + 5 + 4 + 3 + 2 + 1 = 21'dir. Bu sayı dizinin başlangıç düzenine bağlı değildir. Dizi zaten sıralı olsa bile seçimli sıralama 21 karşılaştırma yapar, çünkü en küçüğü bulmak için kalan her öğeye bakmak zorundadır. Algoritmanın dizinin sıralı olduğunu fark etmesinin bir yolu yoktur. Takas sayısı ise en fazla n − 1'dir. Seçimli sıralamanın güçlü yanı budur: yazma işleminin pahalı olduğu durumlarda, örneğin her yazmanın yıprattığı bir bellekte, az takas yapması bir üstünlüktür.

1.3.7.4Kabarcık sıralaması

Kabarcık sıralaması (bubble sort) yan yana duran öğeleri karşılaştırır. Soldaki öğe sağdakinden büyükse ikisi yer değiştirir. Dizinin başından sonuna kadar yapılan böyle bir geçişe tur denir. Bir tur boyunca en büyük öğe, suyun yüzeyine çıkan bir kabarcık gibi adım adım sağa taşınır ve tur sonunda dizinin son konumuna yerleşir.

1. Koleksiyonun başından başla.
2. Yan yana iki öğeyi karşılaştır; gerekiyorsa yer değiştirip büyük olanı sağa taşı.
3. Koleksiyonun sonuna kadar bu adımı tekrarla (bir tur).
4. En büyük öğe sona geldiği için son öğeyi sıralanmış kabul et.
5. İlk dört adımı kalan kısım için tekrarla; bir turda hiç yer değiştirme olmazsa dur.

static void kabarcikSirala(int[] dizi) {
    int n = dizi.length;
    for (int tur = 0; tur < n - 1; tur++) {
        boolean degisti = false;
        for (int j = 0; j < n - 1 - tur; j++) {
            if (dizi[j] > dizi[j + 1]) {
                int gecici = dizi[j];
                dizi[j] = dizi[j + 1];
                dizi[j + 1] = gecici;
                degisti = true;
            }
        }
        if (!degisti) break;
    }
}

Dış döngünün tur değişkeni tamamlanmış tur sayısıdır. Her turdan sonra dizinin sonunda bir öğe daha kesin yerine oturur. Bu yüzden iç döngü j < n - 1 - tur koşuluyla her turda bir öğe daha erken durur; yerine oturmuş öğeleri yeniden karşılaştırmanın anlamı yoktur. İç döngünün sınırında n - 1 kullanılmasının nedeni dizi[j + 1] erişimidir. j en çok n - 2 olabilir; aksi hâlde j + 1 dizinin dışına taşar.

degisti değişkeni yine bir bayraktır. Her turun başında indirilir, bir takas yapıldığında kaldırılır. Tur sonunda bayrak hâlâ inikse turda hiç takas olmamış demektir. Bu da her komşu çiftin zaten doğru sırada olduğunu, yani dizinin sıralı olduğunu gösterir. break kalan turları atlar. Bu erken durma özelliği kabarcık sıralamasını sıralı ya da neredeyse sıralı dizilerde hızlı yapar.

Adım adım. Seçimli sıralamadaki diziyle aynı dizi, [64, 25, 12, 22, 11, 36, 48], kabarcık sıralamasıyla sıralansın. Tablo 1.3.26 her turun sonucunu, Şekil 1.3.18 birinci turun ilk ve son karşılaştırmasıyla son durumu gösterir.

Birinci turda 64 her karşılaştırmayı kazanır ve altı takasla en sona gider. İkinci turda 25 önce 12'yi ve 22'yi, sonra 11'i geçer; 36'ya takılır. Bundan sonra kabarcık 36'dır ama 36 < 48 olduğu için takas olmaz; 48 bu turun sonunda tesadüfen zaten kendi yerindedir. Üçüncü ve dördüncü turlar 11'i adım adım sola taşır: küçük öğeler kabarcık sıralamasında her turda yalnız bir konum sola ilerleyebilir. Dizinin başlarındaki büyük öğeler hızla sona gider, sonlardaki küçük öğeler ise yavaşça başa gelir. Beşinci turda hiç takas olmaz ve algoritma durur. Toplam 20 karşılaştırma ve 11 takas yapılmıştır. Değerler sayaçlı bir kopyanın JDK 21'de çalıştırılmasıyla doğrulanmıştır.

Takas sayısı ve ters çiftler. Kabarcık sıralamasındaki takas sayısının özel bir anlamı vardır. Dizideki her ters çift, yani solda duran büyük öğe ile sağda duran küçük öğeden oluşan çift, tam bir takasla düzelir. Komşu iki öğenin takası tam olarak bir ters çifti ortadan kaldırır. Bu yüzden takas sayısı dizideki ters çift sayısına eşittir. [64, 25, 12, 22, 11, 36, 48] dizisinde 64'ün sağında ondan küçük 6 öğe vardır; 25'in sağında 3 (12, 22, 11), 12'nin sağında 1 (11), 22'nin sağında 1 (11) öğe vardır. Toplam 6 + 3 + 1 + 1 = 11 ters çift ve 11 takas.

Maliyet. En kötü durum dizinin ters sıralı olmasıdır. [64, 48, 36, 25, 22, 12, 11] dizisinde her karşılaştırma bir takasla biter ve erken durma hiç devreye girmez. 6 + 5 + 4 + 3 + 2 + 1 = 21 karşılaştırma ve 21 takas yapılır; genel olarak n(n − 1)/2 karşılaştırma ve aynı sayıda takas. En iyi durum dizinin zaten sıralı olmasıdır. İlk turda n − 1 karşılaştırma yapılır, hiç takas olmaz ve algoritma durur. 7 öğe için 6 karşılaştırma yeter. Seçimli sıralama aynı sıralı dizide yine 21 karşılaştırma yapar.

1.3.7.5Sıralama yöntemlerinin karşılaştırması

Üç yöntemin özellikleri Tablo 1.3.27'de yan yanadır. Son satır aynı yedi öğeli dizi için ölçülen değerleri verir.

Seçimli sıralamanın ve kabarcık sıralamasının işi n² ile büyür. 1.000 öğe için 1000 · 999 / 2 = 499.500, yani yaklaşık 500 bin karşılaştırma yapılır. 1.000.000 öğe için bu sayı yaklaşık 500 milyara çıkar. Saniyede bir milyar karşılaştırma yapan bir bilgisayar bile bu iş için sekiz dakikadan fazla harcar. Büyük veride daha akıllı algoritmalar kullanılır. Birleştirmeli sıralama gibi yöntemlerin işi n · log₂ n ile büyür; bir milyon öğe için yaklaşık 20 milyon karşılaştırma demektir. Fark yaklaşık 25.000 kattır.

Bu tabloda iki gösterim kullanılır: O(n²) ve O(n log n). “Büyük O” gösterimi bir algoritmanın işinin girdi boyutuyla nasıl büyüdüğünü kabaca anlatır. Kesin sayılar yerine büyümenin biçimi verilir. n(n − 1)/2 karşılaştırma yapan bir algoritma O(n²)'dir. n büyüdükçe bu ifadenin değerini belirleyen terim n²/2'dir; 1/2 çarpanı ise büyüme biçimini değiştirmez. Doğrusal arama O(n), ikili arama O(log n)'dir. Bu gösterim algoritmaların karşılaştırılmasında ortak dil olarak kullanılır.

Java'da bir diziyi sıralamak için bu algoritmaları her seferinde yeniden yazmak gerekmez. Arrays.sort(dizi) çağrısı int gibi temel tiplerden oluşan dizileri hızlı sıralamanın geliştirilmiş bir biçimiyle, nesne dizilerini ise birleştirmeli sıralamaya dayanan bir yöntemle sıralar. Basit algoritmaları öğrenmenin amacı onları üretimde kullanmak değildir. Amaç döngü, karşılaştırma, takas ve sayma alışkanlıklarını kazanmak ve bir algoritmanın maliyetini kendi başına hesaplayabilmektir.

1.3.8Sık yapılan hatalar

Bu bölümdeki algoritmalarda en sık görülen hatalar iki gruba ayrılır. Birinci grup algoritmanın kendisindeki hatalardır: dil ne olursa olsun ortaya çıkarlar ve elle izlemeyle bulunurlar (Tablo 1.3.29). İkinci grup Java'ya özgüdür: derleyicinin ya da JVM'nin bir iletisiyle, bazen de hiçbir ileti olmadan kendini gösterir (Tablo 1.3.30).

Tablolardaki hataların önemli bir kısmı hiçbir ileti üretmez. Taşma, metinlerin == ile karşılaştırılması, sırasız dizide ikili arama ve boolean atama hatası programı durdurmaz, yalnız sonucu bozar. Bu hatalara karşı tek güvence, sorun tanımlanırken hazırlanmış ve sınır durumları da içeren test senaryolarıdır. Derleme hatalarında ise ileti çoğu zaman hatanın yerini doğru gösterir; iletiler ilkinden başlanarak okunur, çünkü tek bir eksik çoğu zaman ardından birkaç ileti daha getirir.

1.3.9Özet

• Problem çözme döngüsü: sorunu tanımla, algoritmayı belirle, koda dönüştür, test et; hata varsa geri dön. Test senaryoları kod yazılmadan önce hazırlanır ve sınır durumları (0, boş metin, eşit sayılar, n = 1) içerir.
• Algoritma: sırası belli, açık ve sonlu adımlardan oluşan yönergeler dizisi. Beş özelliği girdi, çıktı, kesinlik, sonluluk ve etkinliktir.
• Sözde kod ve elle izleme: sözde kod dil kurallarından bağımsız, insan için yazılmış bir gösterimdir. İzleme tablosu her adımdaki değişken değerlerini gösterir ve döngü sınırı hatalarını kod yazmadan yakalar.
• Java'ya dönüştürme: Oku → Scanner ile nextInt/nextDouble/nextLine; Yaz → print/println; eşitlik ==, atama =; “ve” &&, “veya” ||; Döngüyü Kır → break. İki int arasında / tam sayı bölmesidir.
• Karar algoritmaları: iki sayıyı sıralamak tek bir if … else ister. Üç sayıda önce en küçük bulunur, kalan ikisi sıralanır; eşitliklerin doğru işlenmesi için <= gerekir; 3! = 6 sıranın hepsi test edilir.
• Döngü algoritmaları: faktöriyel ve üs alma 1 ile başlayan bir biriktiriciyle çalışır; Fibonacci son iki terimi tutar ve her turda kaydırır. int 12!'ye, F(46)'ya ve 2³⁰'a kadar yeter; ötesinde sessizce taşar. long 20!'ye ve F(92)'ye kadar yeter.
• Palindrom ve asal sayı: metin önce temizlenir, ters çevrilir, equals ile karşılaştırılır. Asal kontrolü bayrak ve break kullanır; sınır sayı / 2, daha iyisi bolen * bolen <= sayi'dir.
• Arama: rastgele arama ortalama n deneme yapar ve garanti vermez. Doğrusal arama en kötü n karşılaştırma yapar ve sırasız veride çalışır. İkili arama sıralı veri ister ve en kötü ⌊log₂ n⌋ + 1 karşılaştırma yapar: 1.000.000 öğede 20.
• Sıralama: takas geçici değişkenle yapılır. Fisher–Yates karıştırması her dizilişi eşit olasılıkla üretir. Seçimli sıralama her zaman n(n − 1)/2 karşılaştırma ve en çok n − 1 takas yapar. Kabarcık sıralaması en kötü n(n − 1)/2 karşılaştırma yapar; takas sayısı ters çift sayısına eşittir, erken durmayla sıralı dizide n − 1 karşılaştırmada biter. İkisi de O(n²)'dir.

1.3.10Kavram listesi

• algoritma algorithm
• sözde kod pseudocode
• izleme tablosu trace table
• test senaryosu test case
• sınır durum edge case
• elle izleme dry run
• biriktirici accumulator
• bayrak flag
• taşma overflow
• derleyici compiler
• bayt kodu bytecode
• çalışma zamanı hatası runtime error
• tam sayı bölmesi integer division
• palindrom palindrome
• asal sayı prime number
• doğrusal arama linear search
• ikili arama binary search
• rastgele arama random search
• karıştırma shuffle
• seçimli sıralama selection sort
• kabarcık sıralaması bubble sort
• takas swap
• ters çift inversion

1.3.11Kendini Dene

1. Faktöriyel programı sayi = 6 ile çalıştırılıyor. Döngü kaç tur döner ve sonuç nedir? Döngü koşulu yanlışlıkla i < sayi yazılsaydı ne yazılırdı?

   Cevap

   Döngü i = 1 … 6 için 6 tur döner; faktoriyel sırasıyla 1, 2, 6, 24, 120, 720 olur ve 720 yazılır. i < sayi ile son çarpan 6 atlanır ve 5! = 120 yazılır.

2. Fibonacci programı n = 10 için ne yazar ve döngü kaç tur döner? Döngü gövdesinde a = b; ile b = sonuc; satırlarının yeri değiştirilirse n = 6 için çıktı ne olur?

   Cevap

   0 1 1 2 3 5 8 13 21 34; döngü i = 2 … 9 için n − 2 = 8 tur döner. Satırların yeri değişirse önce b = sonuc olur, ardından a = b ile a da yeni terimi alır ve iki değişken eşitlenir: 0 1 1 2 4 8.

3. Asal sayı programı 49 için kaç bölen dener? Döngü koşulu bolen * bolen <= sayi olarak değiştirilirse 97 için kaç bölen denenir?

   Cevap

   49 için sınır 49 / 2 = 24'tür; 2, 3, 4, 5, 6 bölmez, 7 böler ve döngü kırılır: 6 deneme. Yeni koşulla 97 için b² ≤ 97 olan bölenler 2 … 9'dur; hiçbiri bölmez ve 8 denemeden sonra 97 asal bulunur. Eski koşul 47 deneme yapıyordu.

4. Şu üç satır ne yazar: System.out.println("toplam " + 2 + 3);, System.out.println(2 + 3 + " toplam");, System.out.println(7 / 2 * 2);?

   Cevap

   “toplam 23”, “5 toplam” ve “6”. İlk satırda metin önce geldiği için iki + da birleştirmedir. İkincide önce 2 + 3 = 5 toplanır. Üçüncüde 7 / 2 tam sayı bölmesiyle 3 olur, 3 * 2 = 6.

5. Sıralı {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} dizisinde ikili arama 23 ve 4 için hangi öğelere bakar, ne döndürür?

   Cevap

   23: orta = 4 (16) → sağ, orta = 7 (56) → sol, orta = 5 (23) → bulundu; 3 karşılaştırma, dönen değer 5. 4: 16 → sol, orta = 1 (5) → sol, orta = 0 (2) → sağ; alt = 1, ust = 0 olur ve 3 karşılaştırmadan sonra −1 döner.

6. [9, 4, 7, 1, 3] dizisi seçimli sıralamayla sıralanıyor. Her adımdan sonra dizi nasıldır? Kaç karşılaştırma ve kaç gerçek takas yapılır?

   Cevap

   [1, 4, 7, 9, 3] → [1, 3, 7, 9, 4] → [1, 3, 4, 9, 7] → [1, 3, 4, 7, 9]. Karşılaştırma 4 + 3 + 2 + 1 = 10; her adımda en küçük öğe başka bir konumda olduğu için 4 gerçek takas.

7. Kabarcık sıralaması (erken durmalı) [2, 3, 4, 5, 1] ve [5, 1, 2, 3, 4] dizilerinde kaçar tur, karşılaştırma ve takas yapar? İki dizinin ters çift sayısı aynı olduğu hâlde tur sayıları neden farklıdır?

   Cevap

   [2, 3, 4, 5, 1]: 4 tur, 4 + 3 + 2 + 1 = 10 karşılaştırma, 4 takas. [5, 1, 2, 3, 4]: 2 tur, 4 + 3 = 7 karşılaştırma, 4 takas. İki dizide de 4 ters çift vardır, takas sayısı bu yüzden eşittir. Ama büyük öğe bir turda en sona kadar gidebilirken küçük öğe her turda yalnız bir konum sola ilerler. Sondaki 1'in başa gelmesi dört tur sürer.

8. Sıralı bir dizide en kötü durumda doğrusal ve ikili arama 2.000.000 öğe için kaç karşılaştırma yapar? Öğe sayısı 1.000.000 iken sayılar neydi?

   Cevap

   Doğrusal arama 2.000.000, ikili arama ⌊log₂ 2.000.000⌋ + 1 = 20 + 1 = 21. 1.000.000 öğede sayılar 1.000.000 ve 20'ydi. Dizi iki katına çıkınca doğrusal aramanın işi iki katına çıkar, ikili aramanınki bir artar.

9. Üs alma programında sonuc değişkeni long yerine int tanımlansaydı 2³¹ ve 2³² için ne yazılırdı? Neden hata iletisi çıkmaz?

   Cevap

   −2147483648 ve 0. int en çok 2³¹ − 1 = 2.147.483.647 tutar; bir fazlası başa sararak en küçük int değerine, bir çarpma daha 0'a dönüşür. Java tam sayı taşmasını denetlemez ve istisna fırlatmaz; sonuç sessizce yanlıştır.

1.3.12İleri okuma

• A. B. Downey ve C. Mayfield, Think Java (2. baskı, 2019): koşul, döngü, metin ve dizi bölümleri bu notun Java ayrıntılarını sade bir dille tamamlar. Kitap çevrimiçi ücretsiz okunabilir.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 1.1 ve 2.1: ikili aramayı ve temel sıralama algoritmalarını Java koduyla ve deneysel ölçümlerle işler.
• P. Deitel ve H. Deitel, Java: How to Program (Early Objects) (11. baskı, 2017), Bölüm 4 ve 19: algoritma geliştirmeyi, sözde kodu ve arama-sıralama algoritmalarını çok sayıda tam programla anlatır.
• D. E. Knuth, The Art of Computer Programming, Vol. 2 (3. baskı, 1997), Kesim 3.4.2: Fisher–Yates karıştırmasının ve rastgele dizilişlerin klasik incelemesini içerir.

1.3.13Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
2. P. Deitel, H. Deitel, Java: How to Program (Early Objects), 11. baskı, Pearson, 2017 (Bölüm 4: Algoritmalar ve sözde kod; Bölüm 19: Arama ve sıralama).
3. A. B. Downey, C. Mayfield, Think Java, 2. baskı, O'Reilly, 2019.
4. D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3. baskı, Addison-Wesley, 1997.
5. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2. baskı, Addison-Wesley, 1998.
6. Oracle, The Java Tutorials: Language Basics, docs.oracle.com/javase/tutorial.
7. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011 (Kesim 1.1: ikili arama; 2.1: temel sıralamalar).

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