Algoritmalar

4.1Problem çözme

Programlamaya yeni başlayan biri, bir ödevi okur okumaz bilgisayarın başına geçip kod yazmaya başlamak ister. Kısa ödevlerde bu yol bazen işe yarar. Problem biraz büyüdüğünde ise kod denemelerle şişer, bir hatayı düzeltmek başka bir hatayı doğurur ve programın neden çalıştığı ya da neden çalışmadığı anlaşılmaz hâle gelir. Deneyimli programcılar tersini yapar: önce problemi anlar, sonra çözümü kâğıt üzerinde kurar, en son kodu yazar. Problem çözme (problem solving) bu düzenli yaklaşımın adıdır.

4.1.1Önce algoritma, sonra kod

Kod, bir çözüm fikrinin belirli bir programlama dilindeki yazılışıdır. Aynı fikir Java ile de, Python ile de, C ile de yazılabilir; değişen yalnızca yazım kurallarıdır. Fikrin kendisi, yani problemi çözen adımlar dizisi, dilden bağımsızdır. Bu adımlar dizisine algoritma denir. Algoritma kurulmadan yazılan kod iki sıkıntı doğurur. Birincisi, programcı ne yapacağını yazarken düşündüğü için gereksiz denemeler yapar. İkincisi, bazı durumlar hiç düşünülmediği için gizli hatalar oluşur: program örnek girdide doğru çalışır, başka bir girdide yanlış sonuç verir.

Şekil 4.1 bu sırayı “en büyük sayıyı bul” problemi üzerinde gösterir. İlk adım problemi anlamaktır: liste boş olabilir mi, sayılar negatif olabilir mi, aynı sayı birden çok kez geçebilir mi? İkinci adımda küçük bir örnek elle çözülür. 3, 8, 5 listesinde en büyük sayı 8'dir. Bunu bulurken insan farkında olmadan bir yöntem izler: sayılara soldan sağa bakar ve o ana kadar gördüğü en büyük değeri aklında tutar. Üçüncü adımda bu yöntem açıkça yazılır: “En büyük değer başta listenin ilk öğesidir; sıradaki öğe daha büyükse en büyük değeri güncelle.” Dördüncü adım kodlamadır; yöntem artık bellidir, geriye seçilen dilin yazım kurallarını uygulamak kalır.

İkinci adım çoğu zaman atlanır ama en öğretici adımdır. Elle çözülen örnek, algoritmanın taslağını verir. Örneği çözerken yapılan her işlem algoritmanın bir adımına, akılda tutulan her bilgi ise bir değişkene dönüşür. En büyük sayı örneğinde akılda tutulan bilgi “şimdiye kadarki en büyük değer”dir; programda bu, enBuyuk adlı bir değişken olur.

4.1.2Problem tanımı

Bir problemi anlamak, onu birkaç soruya cevap verecek biçimde yazmak demektir. Bu sorulara verilen cevapların bütününe problem tanımı (problem definition) denir.

Bu altı öğenin her biri, kod yazılırken verilecek bir kararı önceden verir. Amaç, programın ne zaman “bitmiş” sayılacağını belirler. Girdi ve çıktı, programın dış dünyayla nasıl konuşacağını söyler. Kısıt, programın hangi değerler için doğru çalışmak zorunda olduğunu sınırlar. Örnek, program yazıldıktan sonra yapılacak ilk denetimi hazırlar. Hata durumu ise en çok unutulan öğedir: kullanıcı beklenmeyen bir değer girdiğinde programın çökmesi yerine anlamlı bir mesaj vermesi bu kararla sağlanır.

4.2Algoritma

4.2.1Algoritma nedir?

Günlük hayat algoritmalarla doludur. Bir yemek tarifi, bir mobilyanın kurulum kılavuzu, bir bankamatikten para çekme talimatı birer algoritma sayılabilir. Hepsinde belirli bir sonuca ulaşmak için sırayla uygulanacak adımlar vardır. Bilgisayar biliminde algoritma kavramı daha kesin tanımlanır, çünkü adımları uygulayacak olan bir insan değil, kendi başına yorum yapamayan bir makinedir.

Tanımdaki “sıfır ya da daha fazla girdi” ifadesi ilk bakışta tuhaf görünebilir. Hiç girdi almayan bir algoritma da vardır: “1'den 100'e kadar olan sayıları yaz” işi dışarıdan hiçbir bilgi istemez. Buna karşılık çıktısı olmayan bir algoritma işe yaramaz; sonucu hiçbir yere yansımayan bir hesap, yapılmamış bir hesaptan farksızdır. Çıktı ekrana yazılan bir sayı olabileceği gibi bir dosyaya kaydedilen veri ya da bir motoru çalıştıran bir sinyal de olabilir.

4.2.2İyi algoritmanın özellikleri

Her adımlar dizisi iyi bir algoritma değildir. “Sayıları uygun biçimde düzenle” cümlesi bir adım gibi görünür ama “uygun” sözcüğü ne yapılacağını söylemez. Bir algoritmanın bilgisayarda güvenle çalışması için adımlarının bazı özellikleri taşıması gerekir.

Tablo 4.1 altı özelliği ve her biri bozulduğunda görülen belirtiyi listeler. Bunlardan kesinlik (definiteness) ve sonluluk (finiteness) en sık gözden kaçanlardır. Sonluluğun ne kadar ince bir koşula bağlı olabileceğini küçük bir örnek gösterir.

Şekil 4.3 iki döngüyü karşılaştırır. İkisinde de sayaç 1'den başlar ve her turda 2 artar. Üstteki döngü “i, 10'a eşit olmadığı sürece devam et” der. Sayaç 1, 3, 5, 7, 9, 11, 13 … diye ilerler ve 10'u atlar. Koşul hiçbir zaman yanlış olmadığından döngü sonsuza dek sürer. Alttaki döngü “i, 10'dan küçük ya da 10'a eşit olduğu sürece devam et” der. Sayaç 11 olduğunda 11 ≤ 10 yanlış olur ve döngü biter. İki koşul arasındaki fark tek bir simgedir ama birinde algoritma vardır, ötekinde yoktur.

Doğruluk (correctness) ile verimlilik ayrı özelliklerdir. Doğru bir algoritma yavaş olabilir, hızlı bir algoritma bazı girdilerde yanlış sonuç verebilir. Önce doğruluk sağlanır; hızlı ama yanlış bir sonucun hiçbir değeri yoktur. Verimlilik ise girdi büyüdükçe önem kazanır.

4.2.3Algoritma tasarlama döngüsü

İyi bir algoritma nadiren ilk denemede ortaya çıkar. Tasarım, birkaç kez tekrarlanan bir döngüdür. Her turda algoritma biraz daha netleşir ve gözden kaçan durumlar yakalanır.

Şekil 4.4'teki beş adım şöyle işler:

1. Örneği çöz. Problemin küçük bir örneği elle çözülür. Faktöriyel için 4! = 1 × 2 × 3 × 4 = 24 hesaplanır.
2. Genel kuralı bul. Elle yapılan işlemlerdeki tekrar fark edilir: her adımda o ana kadarki çarpım bir sonraki sayıyla çarpılıyor. Kural “çarpımı 1 ile başlat, 2'den n'e kadar her sayıyla çarp” biçiminde yazılır.
3. Sözde kod yaz. Kural, programlama diline yakın ama ona bağlı olmayan açık adımlara dönüştürülür.
4. Elle izle. Sözde kod birkaç girdiyle, bilgisayar gibi satır satır çalıştırılır; her değişkenin değeri bir tabloya yazılır.
5. Düzelt. İzlemede beklenen sonuçla bulunan sonuç ayrışırsa hata bulunur ve sözde kod düzeltilir. Sonra döngü yeniden döner: düzeltilmiş sözde kod yeniden izlenir.

Döngü, elle izlemede artık hata çıkmayınca biter ve kodlamaya geçilir. Aynı problem için birden fazla çözüm bulunmuşsa bu aşamada doğruluk, okunabilirlik ve verimlilik bakımından karşılaştırılır. Okunabilirlik küçümsenmemelidir: bir algoritmayı en çok okuyan kişi, birkaç ay sonra onu değiştirmek zorunda kalan programcının kendisidir.

4.2.4Sözde kod

Algoritmayı yazmanın birkaç yolu vardır. Günlük dille yazılan adımlar kolay anlaşılır ama belirsizliğe açıktır. Programlama diliyle yazılan adımlar kesindir ama yazım kurallarıyla doludur; noktalı virgüller ve parantezler düşüncenin önüne geçer. Sözde kod bu iki ucun arasında durur.

Sözde kodun herkesçe kabul edilmiş tek bir yazım kuralı yoktur. Önemli olan, bir algoritma içinde aynı ifadenin hep aynı anlamda kullanılmasıdır. Bu notta kullanılan ifadeler şunlardır: oku bir girdiyi alır, yaz bir çıktı üretir, = sağdaki değeri soldaki değişkene atar, eğer … ise bir koşulu denetler, … iken koşul doğru olduğu sürece altındaki satırları tekrarlar, … kadar tekrarla belirli sayıda tekrar yapar. Girinti (indentation), yani satır başındaki boşluk, bir koşulun ya da döngünün hangi satırları kapsadığını gösterir.

En basit örnek, iki sayının toplamını yazan algoritmadır:

BAŞLA
  A değerini oku
  B değerini oku
  TOPLAM = A + B
  TOPLAM değerini yaz
BİTİR

Aynı algoritma bir akış diyagramıyla da çizilebilir. Şekil 4.5 her sözde kod satırının diyagramdaki karşılığını gösterir: başlangıç ve bitiş oval, girdi ve çıktı paralelkenar, işlem dikdörtgen kutudur. Oklar adımların sırasını belirtir.

Sözde kodun amacı yazım kurallarına uymak değil, algoritmayı anlaşılır kılmaktır. Bu yüzden sözde kodda “dizi[i] ile dizi[j] yer değiştir” gibi bir satır rahatlıkla yazılabilir. Java'da aynı iş üç atama ister ama algoritmanın mantığı açısından tek bir adımdır. Sözde kod hazır olunca koda çevirmek çoğu zaman satır satır bir iştir: eğer … ise satırı if'e, … iken satırı while'a dönüşür.

4.3Örnek algoritmalar

Algoritma kurmayı öğrenmenin en iyi yolu, küçük ve iyi bilinen problemleri çözmektir. Bu kesimdeki beş örnek giderek zorlaşır. İlki yalnızca bir koşul ve üç atama içerir. Faktöriyel ve Fibonacci örnekleri döngü ve biriktirme fikrini getirir. Palindrom ve asal sayı örneklerinde ise döngü, sonuç belli olur olmaz erken biter. Her örnekte önce sözde kod verilir, sonra algoritma bir girdi için adım adım izlenir.

4.3.1İki sayıyı sıralama ve takas

Problem şudur: iki sayı okunacak ve küçük olan önce yazılacak. a = 7, b = 3 girilirse çıktı “3 7” olmalıdır; a = 2, b = 9 girilirse “2 9”. Çözüm fikri basittir. a, b'den büyükse iki değişkenin değerleri yer değiştirir; değilse zaten doğru sıradadır. İki değişkenin değerlerini yer değiştirmeye takas (swap) denir.

oku a, b
eğer a > b ise
    gecici = a
    a = b
    b = gecici
yaz a, b

Algoritmanın 2. satırı koşulu denetler. Koşul doğruysa girintili üç satır çalışır, yanlışsa atlanır. Eşit değerlerde (a = b) koşul yanlıştır ve takas yapılmaz; zaten gerekmez. Son satır her iki durumda da çalışır ve a ≤ b koşulunu sağlayan çıktıyı yazar.

Takasın neden üç atama gerektirdiği, algoritmanın en öğretici yanıdır. Bir değişken aynı anda yalnızca bir değer tutabilir. a = b atamasıyla a'ya yeni değer yazıldığı anda eski değeri silinir. Eski değer önceden bir yere kopyalanmamışsa bir daha geri getirilemez. Bu yüzden önce a'nın değeri geçici değişkene (temporary variable) kopyalanır.

Şekil 4.6 üç atamayı oklarla gösterir. Atamalar bir döngü oluşturur: a'dan gecici'ye, b'den a'ya, gecici'den b'ye. Algoritmanın a = 7, b = 3 için adım adım çalışması Tablo 4.2'de verilmiştir.

Tablonun 4. satırında a ve b'nin ikisi de 3'tür. Algoritmanın en kırılgan anı budur: 7 değeri yalnızca gecici'de yaşar. 5. satırda gecici'deki 7, b'ye kopyalanır ve takas tamamlanır. a = 2, b = 9 girilseydi 2. satırdaki 2 > 9 koşulu yanlış olur, 3–5. satırlar hiç çalışmaz ve doğrudan “2 9” yazılırdı.

İki sayıyı sıralama fikri, daha fazla sayıya genişletilebilir. Üç sayı için iki sayıyı sıralama adımı üç kez uygulanır: önce a ile b, sonra b ile c, en son yeniden a ile b karşılaştırılır.

oku a, b, c
eğer a > b ise a ile b yer değiştir
eğer b > c ise b ile c yer değiştir
eğer a > b ise a ile b yer değiştir
yaz a, b, c

4.3.2Faktöriyel

n'nin faktöriyeli (factorial), 1'den n'e kadar olan tam sayıların çarpımıdır ve n! diye yazılır. 3! = 1 × 2 × 3 = 6, 5! = 120'dir. 0! tanım gereği 1'dir. Faktöriyelin problem tanımı 4.1.2'de yazılmıştı; algoritma bu tanımı adım adım izler.

oku n
eğer n < 0 ise "hata" yaz ve dur
sonuc = 1
i = 2
i ≤ n iken
    sonuc = sonuc × i
    i = i + 1
yaz sonuc

Satırlar şu işleri yapar:

1. oku n: faktöriyeli hesaplanacak sayı okunur.
2. eğer n < 0 ise "hata" yaz ve dur: negatif sayıların faktöriyeli tanımlı değildir. Bu satır problem tanımındaki hata durumunu karşılar.
3. sonuc = 1: çarpımın başlangıç değeri 1'dir. Değişken çarpımı adım adım biriktirir.
4. i = 2: sayaç 2'den başlar. 1 ile çarpmak değeri değiştirmediği için 1'den başlamaya gerek yoktur.
5. i ≤ n iken: i, n'i geçmediği sürece altındaki iki satır tekrarlanır.
6. sonuc = sonuc × i: o ana kadarki çarpım i ile çarpılır.
7. i = i + 1: sayaç bir artar; sonra 5. satıra dönülür ve koşul yeniden denetlenir.
8. yaz sonuc: döngü bittiğinde sonuç yazılır.

3. satırdaki gibi, bir döngü boyunca bir sonucu adım adım biriktiren değişkene biriktirici (accumulator) denir. Biriktiricinin başlangıç değeri yapılan işleme göre seçilir. Toplama için 0 seçilir, çünkü 0 eklemek toplamı değiştirmez. Çarpma için 1 seçilir, çünkü 1 ile çarpmak çarpımı değiştirmez.

Şekil 4.8 çarpımın nasıl büyüdüğünü gösterir. Algoritmanın n = 5 için tam izlemesi Tablo 4.3'te verilmiştir.

Tabloda döngünün 4 kez döndüğü görülür: i, 2, 3, 4 ve 5 değerlerini alır. Genel olarak n ≥ 2 için döngü n − 1 kez döner. i = 6 olduğunda 6 ≤ 5 koşulu yanlıştır ve döngü biter; 120 yazılır.

Tablonun sonuc sütununda bir düzen göze çarpar. Her turun başında sonuc, i'nin bir eksiğinin faktöriyeline eşittir: i = 2 iken 1 = 1!, i = 3 iken 2 = 2!, i = 4 iken 6 = 3!. Döngünün her turunda doğru kalan böyle bir ifadeye döngü değişmezi denir.

Döngü değişmezi, algoritmanın neden doğru olduğunu gösterir. Döngü ilk kez başlarken i = 2 ve sonuc = 1 = 1!'dir; ifade doğrudur. Bir turda sonuc i ile çarpılır ve i bir artar. Turdan önce sonuc = (i − 1)! ise turdan sonra sonuc = (i − 1)! × i = i! olur. Yeni i, eski i'nin bir fazlası olduğundan ifade yeniden doğrudur. Döngü i = n + 1 iken biter; bu anda sonuc = n!'dir. Tam istenen sonuç budur.

Algoritmanın küçük girdilerdeki davranışı da değişmezle açıklanır. n = 0 ya da n = 1 için ilk denetimde 2 ≤ n koşulu yanlıştır. Döngü hiç dönmez ve sonuc = 1 kalır; 0! ve 1! zaten 1'dir. Algoritma bu iki durum için ayrı bir satıra ihtiyaç duymaz.

Biriktirici fikri yalnızca faktöriyelde değil, toplam, sayaç ve ortalama gerektiren her problemde kullanılır. Aşağıdaki örnek, aynı kalıbı toplama için uygular.

oku n
toplam = 0
i = 2
i ≤ n iken
    toplam = toplam + i
    i = i + 2
yaz toplam

4.3.3Fibonacci dizisi

Fibonacci dizisi 0 ve 1 ile başlar; sonraki her terim, kendinden önceki iki terimin toplamıdır: 0, 1, 1, 2, 3, 5, 8, 13, 21, … Problem, dizinin ilk n terimini yazmaktır. Faktöriyelde her turda tek bir değeri hatırlamak yetiyordu. Burada yeni terimi hesaplamak için iki önceki değerin birlikte saklanması gerekir.

oku n
a = 0, b = 1
0'dan n-1'e kadar tekrarla
    yaz a
    sonraki = a + b
    a = b
    b = sonraki

a ve b, dizinin art arda gelen iki terimini tutar. Her turda a yazılır, sonra a ile b toplanarak bir sonraki terim bulunur. Ardından iki değişken birer terim ilerler: a, b'nin değerini; b, yeni terimin değerini alır. a ile b, dizinin üzerinde her turda bir sağa kayan iki hücrelik bir pencere gibidir. Bu yönteme kayan pencere (sliding window) denir.

Şekil 4.9 üçüncü turdaki durumu gösterir. Algoritmanın n = 8 için bütün turları Tablo 4.4'te izlenmiştir.

Çıktı, “Yazılan a” sütununun sırasıdır: 0 1 1 2 3 5 8 13. Son turda sonraki = 34 hesaplanır ama yazılmaz; döngü 8 turdan sonra biter. Bu küçük israf algoritmanın sadeliği için ödenen bedeldir. Algoritma n = 0 için hiçbir şey yazmaz, n = 1 için yalnızca 0 yazar; ikisi de beklenen sonuçtur.

Son iki atamanın sırası, takastaki sorunun benzerini taşır. Şekil 4.10'daki gibi önce a = b, sonra b = sonraki yapılır. Sıra ters çevrilirse b = sonraki ataması b'nin eski değerini siler. Ardından a = b, a'ya eski b'yi değil yeni terimi yazar. a ile b eşit olur ve her tur yeni terim a + a = 2a diye hesaplanır. Dizi 0, 1, 2, 4, 8 diye ikiye katlanarak ilerler.

4.3.4Palindrom

Tersten okunuşu düz okunuşuyla aynı olan sözcük ya da cümleye palindrom (palindrome) denir. “kayak”, “ses”, “kazak” birer palindromdur; “kayık” değildir. Problem, verilen bir metnin palindrom olup olmadığını doğru ya da yanlış diye bildirmektir.

İlk akla gelen çözüm, metni ters çevirip kendisiyle karşılaştırmaktır. Bu çözüm doğrudur ama metnin bir kopyasını oluşturur. Daha az iş yapan çözüm, metnin iki ucundan başlayıp ortaya doğru ilerlemektir. İlk harf son harfle, ikinci harf sondan ikinci harfle karşılaştırılır. Farklı bir çift bulunursa metin palindrom değildir ve hemen yanlış döndürülür. Uçlar ortada buluşana kadar farklı çift çıkmazsa metin palindromdur.

metni oku
metni kurala göre temizle
sol = 0, sag = uzunluk - 1
sol < sag iken
    karakterler farklıysa yanlış döndür
    sol = sol + 1, sag = sag - 1
doğru döndür

İkinci satırdaki “kurala göre temizle” adımı problem tanımının bir parçasıdır. “Kayak” sözcüğünde ilk harf büyük K'dir; harfler olduğu gibi karşılaştırılırsa K ≠ k sanılır ve doğru cevap kaçırılır. Bu yüzden algoritmadan önce bir kural belirlenir. Örnekteki kural şudur: bütün harfler küçük harfe çevrilir, boşluklar ve noktalama işaretleri atılır. “Kayak” böylece “kayak” olur.

Şekil 4.11 karşılaştırılan çiftleri yaylarla gösterir. sol ve sag, karşılaştırılacak iki harfin indisidir, yani metindeki sıra numarasıdır. İndisler 0'dan başlar: “kayak” sözcüğünde metin[0] = 'k', metin[4] = 'k'dir. Algoritmanın izlemesi Tablo 4.5'dedir.

Üçüncü denetimde sol ve sag ikisi de 2'dir; ortadaki harfe gelinmiştir. 2 < 2 yanlış olduğu için döngü biter ve doğru döndürülür. Uzunluğu n olan bir metin için döngü en fazla ⌊n / 2⌋ kez döner. ⌊ ⌋ işareti sayının aşağı yuvarlandığını gösterir: ⌊5 / 2⌋ = ⌊2,5⌋ = 2. Çift uzunluktaki bir metinde, örneğin “abba” sözcüğünde, sol ve sag ortada birbirini geçer: 2 karşılaştırmadan sonra sol = 2, sag = 1 olur ve döngü yine biter.

Algoritma palindrom olmayan metinlerde daha da erken durur. “Kayık” için ilk karşılaştırmada k ile k aynıdır. İkinci karşılaştırmada a ile ı farklıdır ve yanlış döndürülür; ortadaki y'ye hiç bakılmaz.

4.3.5Asal sayı

1'den büyük olup 1'den ve kendisinden başka pozitif böleni (divisor) olmayan sayıya asal sayı (prime number) denir. 2, 3, 5, 7, 11, 13 asaldır; 9 = 3 × 3 ve 21 = 3 × 7 asal değildir. Problem, verilen bir n sayısının asal olup olmadığını yazmaktır.

Tanım doğrudan bir algoritma verir: 2'den n − 1'e kadar her sayıyla n bölünmeye çalışılır. Kalansız bölen bir sayı bulunursa n asal değildir. Kalan, % işlemiyle hesaplanır. 29 % 5 = 4'tür, çünkü 29 = 5 × 5 + 4'tür. n % i = 0 ise i, n'i tam böler. Bu yöntem doğrudur ama gereğinden fazla çalışır. Sunumdaki algoritma aynı soruyu çok daha az denemeyle cevaplar.

oku n
eğer n < 2 ise "asal değil" yaz ve dur
i = 2
i × i ≤ n iken
    eğer n % i == 0 ise "asal değil" yaz ve dur
    i = i + 1
"asal" yaz

Algoritmanın iki önemli özelliği vardır. Birincisi, bir bölen bulununca arama hemen durur; geri kalan adaylara bakmaya gerek yoktur. İkincisi, döngü i × i ≤ n koşulu sağlandığı sürece, yani i, √n'i geçmediği sürece döner. Bu karekök sınırının nedeni şudur: n, a × b diye iki çarpana ayrılıyorsa a ile b'nin ikisi birden √n'den büyük olamaz. İkisi de büyük olsaydı çarpımları n'den büyük çıkardı. Öyleyse n'in 1'den büyük bir böleni varsa, √n'den küçük ya da ona eşit bir böleni de vardır.

Şekil 4.12 bu gözlemi 36 için gösterir. Her yay bir bölen çiftini bağlar. Yayların sol uçları hep yeşil bölgede, yani 6'nın solunda ya da üstündedir. Koşulun karekök yerine i × i ≤ n diye yazılması bilinçli bir seçimdir: kesirli karekök hesabı yerine tam sayı çarpması kullanılır ve yuvarlama hatası olmaz.

Tablo 4.6 ve Şekil 4.13 aynı çalışmayı iki biçimde gösterir. 29, dört adayın hiçbirine tam bölünmez. i = 6 olduğunda 36 ≤ 29 yanlıştır ve döngü biter. Bölen bulunmadığı için “asal” yazılır. Tanımdan gelen yöntem 2'den 28'e kadar 27 aday denerdi; karekök sınırı bu sayıyı 4'e indirir. n = 21 olsaydı i = 3'te 21 % 3 = 0 bulunur, “asal değil” yazılır ve algoritma iki denemede biterdi.

4.4Algoritmayı doğrulama

Bir algoritmanın yazılmış olması doğru çalıştığını göstermez. Doğruluk iki yolla sınanır. Birincisi algoritmayı küçük girdilerle, bilgisayarın yapacağı gibi satır satır çalıştırmaktır. İkincisi, algoritmanın davranışını farklı türden girdilerle denemektir. İki yöntem birbirini tamamlar.

4.4.1Elle izleme ve izleme tablosu

Algoritmayı kâğıt üzerinde, her satırı sırayla uygulayarak çalıştırmaya elle izleme (hand tracing) denir. İzleme sırasında değişkenlerin değerleri akılda tutulmaz, bir tabloya yazılır. Satırlar zamanı, sütunlar değişkenleri gösterir. Böyle bir tabloya izleme tablosu (trace table) denir. Önceki kesimdeki bütün tablolar birer izleme tablosudur.

İzleme tablosu hazırlanırken en önemli karar, bir satırın neyi temsil ettiğidir. Değişkenin turun başındaki değeri mi yazılıyor, sonundaki değeri mi? İkisi karıştırılırsa tablo yanıltıcı olur. Bu yüzden tablonun başlığında ya da altında bu karar açıkça belirtilir.

İzleme tablosu yalnızca doğruluğu göstermek için değil, hata bulmak için de kullanılır. Algoritma yanlış sonuç verdiğinde beklenen ve gerçek değerler satır satır karşılaştırılır. İki değerin ilk ayrıldığı satır, hatanın yerini gösterir. Örneğin faktöriyel algoritmasında koşul yanlışlıkla i < n yazılmışsa n = 4 için tablo tur 2'ye kadar doğru ilerler. i = 4 olduğunda koşul yanlış çıkar ve tur 3 hiç yapılmaz. Hatanın yeri döngü koşuludur.

4.4.2Test durumları

İzleme tablosu algoritmanın bir girdi için doğru çalıştığını gösterir. Tek bir başarılı deneme ise algoritmanın her girdi için doğru olduğunu kanıtlamaz. Faktöriyel algoritmasındaki sınır hatası n = 1 ile denendiğinde görünmez; algoritma doğru cevap olan 1'i verir. Bu yüzden algoritma, özenle seçilmiş birkaç girdiyle sınanır. Bir girdi ile o girdi için beklenen çıktının ikilisine test durumu (test case) denir.

Test durumunda beklenen çıktı, algoritma çalıştırılmadan önce yazılır. Önce algoritmayı çalıştırıp çıkan sonucu “beklenen” sütununa yazmak, testi anlamsız kılar. Beklenen değer problem tanımından ve elle yapılan hesaptan gelmelidir.

Şekil 4.14 faktöriyel girdisinin bölgelerini gösterir. Her bölgeden en az bir test seçilir; bölgelerin sınırları ayrıca denenir, çünkü hatalar çoğunlukla sınırlarda saklanır. Tablo 4.7 böyle bir test kümesini verir.

Tablodaki son satır özel bir durumu gösterir. 21! değerinin kendisi doğrudur ama Java'nın 64 bitlik long tipi en çok 9.223.372.036.854.775.807 değerini tutabilir. 21! bu sınırı yaklaşık 5,5 kat aşar. Sınırı aşan bir hesapta Java hata vermez; sonuç sessizce başa sarar. Algoritma Java'da long ile çalıştırıldığında 21! için −4.249.290.049.419.214.848 gibi negatif ve anlamsız bir sayı çıkar. Bir değerin, tutulduğu veri tipinin sınırını aşmasına taşma (overflow) denir.

Bu test, algoritmada bir eksiklik olduğunu gösterir: kısıtın üst sınırı hiç denetlenmiyordur. Problem tanımında yazılan “0 ≤ n ≤ 20” kısıtı algoritmaya da yansıtılmalıdır. Düzeltilmiş algoritma, girdiyi işlemeye başlamadan önce iki sınırı birlikte denetler:

oku n
eğer n < 0 veya n > 20 ise "hata" yaz ve dur
sonuc = 1
i = 2
i ≤ n iken
    sonuc = sonuc × i
    i = i + 1
yaz sonuc

Bu sürümde n = 21 girildiğinde döngüye hiç girilmez ve “hata” yazılır. Görüldüğü gibi test, yalnızca hatayı bulmakla kalmaz, algoritmanın kendisini de iyileştirir.

4.5Algoritma analizi

Bir problem için çoğu zaman birden fazla doğru algoritma vardır. Bunlar arasında seçim yapmak için algoritmaların ne kadar iş yaptığını ölçmek gerekir. Bu ölçmeye algoritma analizi denir. Analizde amaç, saniye cinsinden süre ölçmek değildir; o süre bilgisayara, programlama diline ve o anda çalışan başka programlara göre değişir. Amaç, yapılan işin girdinin büyüklüğüyle nasıl değiştiğini bulmaktır.

4.5.1Aynı problem, iki algoritma

Problem, 1'den n'e kadar olan tam sayıların toplamını bulmaktır: 1 + 2 + … + n. İlk akla gelen algoritma (A), bir döngüyle sayıları tek tek toplar:

toplam = 0
i = 1
while i <= n
    toplam = toplam + i
    i = i + 1

İkinci algoritma (B), Gauss'a atfedilen bir formülü kullanır ve sonucu tek adımda bulur:

toplam = n * (n + 1) / 2

Formülün nereden geldiği kısa bir hesapla görülür. Toplam iki kez yazılır; biri baştan sona, öteki sondan başa:

Alt alta gelen sayılar toplanırsa her çift n + 1 eder: 1 + n, 2 + (n − 1), … Toplam n çift vardır. Öyleyse 2T = n × (n + 1), yani T = n × (n + 1) / 2'dir. n = 10 için 10 × 11 / 2 = 55 bulunur; döngüyle hesaplanan 1 + 2 + … + 10 da 55'tir.

Şekil 4.15 ve Tablo 4.8 iki algoritmanın da doğru olduğunu, ama yaptıkları işin çok farklı büyüdüğünü gösterir. A'da döngü n kez döner; her turda bir toplama ve bir sayaç artırma yapılır. n bin katına çıkınca A'nın işi de bin katına çıkar. B ise n ne olursa olsun bir toplama (n + 1), bir çarpma ve bir bölme yapar. Bir milyon sayının toplamı için A bir milyon tur döner; B yine üç işlemle biter.

4.5.2Doğruluk ve verimlilik

Toplama örneği, algoritmaları değerlendirirken iki ayrı ölçüt kullanıldığını gösterir. Doğruluk, algoritmanın beklenen sonucu üretmesidir. Verimlilik ise algoritmanın bu sonuca ulaşırken ne kadar kaynak kullandığıdır. En önemli iki kaynak zaman ve bellektir.

Girdi boyutu, genellikle n harfiyle gösterilir ve problemin doğasına göre seçilir. Bir dizide arama ya da sıralama yapan algoritmada n, dizinin öğe sayısıdır. Faktöriyel ya da toplam hesaplayan algoritmada n, girilen sayının kendisidir. Temel işlem de probleme göre seçilir. Arama ve sıralama algoritmalarında genellikle iki öğenin karşılaştırma sayısı sayılır, çünkü işin büyük kısmını karşılaştırmalar oluşturur.

Aynı girdi boyutundaki farklı girdiler, farklı miktarda iş gerektirebilir. Bir dizide aranan değer ilk öğe ise arama hemen biter; son öğe ise bütün diziye bakılır. Bu yüzden üç durum ayrı ayrı ele alınır. En iyi durum (best case), algoritmanın en az iş yaptığı girdidir. En kötü durum (worst case), en çok iş yaptığı girdidir. Ortalama durum ise rastgele girdilerde beklenen iş miktarıdır. Uygulamada en çok en kötü durum kullanılır: algoritmanın hiçbir girdide bu sınırdan daha yavaş olmayacağı güvencesini verir.

4.5.3Büyük O gösterimi

İşlem sayısını tam olarak saymak çoğu zaman gereksizdir. 3n + 2 işlem yapan algoritma ile 5n işlem yapan algoritma aynı biçimde büyür: n iki katına çıkınca ikisinin işi de yaklaşık iki katına çıkar. Önemli olan katsayılar değil, büyümenin biçimidir. Büyük O gösterimi bu biçimi kısaca yazmanın yoludur.

Bu notta en sık karşılaşılan karmaşıklıklar şunlardır. O(1), sabit zamandır: Gauss formülü n ne olursa olsun üç işlem yapar. O(log n), logaritmik zamandır: her adımda problem yarıya iner; ikili arama böyle çalışır. O(n), doğrusal zamandır: her öğeye bir kez bakılır; döngüyle toplama ve doğrusal arama böyledir. O(n log n), birleştirme sıralamasının karmaşıklığıdır. O(n²), karesel zamandır: her öğe öteki öğelerin çoğuyla karşılaştırılır; seçimli, kabarcık ve eklemeli sıralama en kötü durumda böyledir.

log₂ n ifadesi, “2'yi kaçıncı kuvvete yükseltince n bulunur?” sorusunun cevabıdır. 2¹⁰ = 1.024 olduğu için log₂ 1.024 = 10'dur. Daha sezgisel bir okuma da vardır: log₂ n, n'i 1'e inene kadar kaç kez ikiye bölmek gerektiğini söyler. 1.000.000 sayısı 20 kez ikiye bölününce 1'in altına iner. Bu yüzden logaritmik algoritmalar çok büyük girdilerde bile az iş yapar.

Tablo 4.9 farkı sayılarla gösterir. n = 10'da üç sütun arasındaki fark küçüktür; hangi yöntemin seçildiği pek önemli değildir. n = 1.000.000'da ikili arama 20 turda biter, doğrusal arama bir milyon karşılaştırma yapar. Seçimli sıralama ise yaklaşık beş yüz milyar karşılaştırma yapar. Saniyede bir milyar karşılaştırma yapan bir bilgisayar, ikili aramayı bir saniyenin milyonda birinden kısa sürede, seçimli sıralamayı ise yaklaşık sekiz dakikada bitirir.

Verimlilik her zaman tek ölçüt değildir. Küçük veride en hızlı görünen yöntem her zaman en anlaşılır yöntem olmayabilir. On öğelik bir listeyi sıralamak için karmaşık bir algoritma yazmak yerine anlaşılması ve doğrulanması kolay basit bir yöntem seçmek çoğu zaman daha akıllıcadır. Girdi büyüdükçe denge verimlilik lehine döner.

4.6Arama

Bir veri topluluğunda belirli bir değerin olup olmadığını ve varsa nerede olduğunu bulma işine arama (search) denir. Rehberde bir telefon numarasını, bir öğrenci listesinde bir numarayı, bir sözlükte bir kelimeyi bulmak birer aramadır. Aranan değere hedef (target) denir. Buradaki algoritmalar bir tam sayı dizisinde hedefi arar. Hedef bulunursa onun indisini, bulunamazsa −1 döndürür. −1 hiçbir zaman geçerli bir indis olmadığı için “yok” anlamına gelen güvenli bir işarettir.

Arama algoritmaları Java ile yazılmıştır. Java'da int[] dizi bir tam sayı dizisidir; dizi[i], i numaralı öğedir ve dizi.length öğe sayısını verir. İndisler 0'dan başlar; n öğeli bir dizinin son indisi n − 1'dir. return deyimi metodu hemen bitirir ve yanındaki değeri, metodu çağıran yere geri gönderir.

4.6.1Doğrusal arama

En basit arama yöntemi, öğelere baştan sona sırayla bakmaktır. Her öğe hedefle karşılaştırılır; eşleşme bulunursa arama biter. Kitaplıkta sırasız dizilmiş kitaplar arasında bir kitabı bulmak için rafları tek tek taramak bu yönteme benzer.

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

Metot iki parametre alır: aranacak dizi ve hedef. for döngüsü i'yi 0'dan dizi.length − 1'e kadar artırır. Her turda dizi[i] == hedef karşılaştırması yapılır. Eşitse return i metodu hemen bitirir; döngünün geri kalanı çalışmaz. Döngü hiç eşleşme bulmadan biterse son satıra gelinir ve −1 döndürülür.

Doğrusal aramanın iki önemli özelliği vardır. Birincisi, dizinin sıralı (sorted) olması gerekmez; öğeler hangi düzende olursa olsun hepsine bakılır. İkincisi, ilk eşleşmede durur. Hedef dizide birden çok kez geçiyorsa en küçük indis döndürülür.

Tablo 4.10'da görüldüğü gibi 5, dördüncü öğede bulunur ve metot 3 döndürür; 4 karşılaştırma yapılmıştır. Hedef 4 olsaydı beş öğenin hepsi denenir, beşinin de eşleşmediği görülür ve 5 karşılaştırmadan sonra −1 döndürülürdü. JDK 21 ile derlenip çalıştırılan metot da ara(dizi, 5) için 3, ara(dizi, 4) için −1 verir.

Doğrusal aramanın maliyeti hedefin yerine bağlıdır. En iyi durumda hedef ilk öğedir ve tek karşılaştırma yeter. En kötü durumda hedef son öğedir ya da dizide hiç yoktur; n karşılaştırma yapılır. Bu yüzden doğrusal aramanın zaman karmaşıklığı O(n)'dir. Ek bellek olarak yalnızca i değişkeni kullanılır; alan karmaşıklığı O(1)'dir.

4.6.2İkili arama

Telefon rehberinde bir isim aranırken rehber ilk sayfadan başlanıp tek tek çevrilmez. Ortalarda bir sayfa açılır. Aranan isim o sayfadakinden alfabede önce geliyorsa ön yarıya, sonra geliyorsa arka yarıya geçilir. Her bakışta rehberin yarısı elenir. Bu yöntem rehberin alfabetik sırada olmasına dayanır. Bilgisayardaki karşılığı ikili aramadır.

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

Metodun satırları şöyle çalışır:

1. int sol = 0, sag = dizi.length - 1;: arama aralığı başta bütün dizidir. sol aralığın ilk, sag son indisidir.
2. while (sol <= sag): aralıkta en az bir öğe kaldığı sürece döngü sürer. sol, sag'ı geçerse aralık boştur.
3. int orta = sol + (sag - sol) / 2;: aralığın ortasındaki indis hesaplanır. Java'da iki tam sayının bölümü tam sayıdır; kesirli kısım atılır: 7 / 2 = 3.
4. if (dizi[orta] == hedef) return orta;: ortadaki öğe hedefse arama biter.
5. if (dizi[orta] < hedef) sol = orta + 1;: ortadaki öğe hedeften küçükse, dizi sıralı olduğu için ortanın solundaki bütün öğeler de hedeften küçüktür. Sol yarı ortayla birlikte elenir.
6. else sag = orta - 1;: aksi hâlde ortadaki öğe hedeften büyüktür; sağ yarı ortayla birlikte elenir.
7. return -1;: aralık boşaldıysa hedef dizide yoktur.

5. ve 6. satırdaki eleme kararı, algoritmanın kalbidir ve tamamen sıralılığa dayanır. Sıralı bir dizide dizi[orta] < hedef ise dizi[0], …, dizi[orta] öğelerinin hepsi hedeften küçüktür; hiçbiri hedef olamaz. Bu yüzden ortanın kendisi de elenir: sol, orta değil orta + 1 olur.

Orta indisin (sol + sag) / 2 yerine sol + (sag - sol) / 2 diye hesaplanmasının bir nedeni vardır. İki ifade matematikte aynı sonucu verir. Bilgisayarda ise int tipi en çok 2.147.483.647 değerini tutar. Çok büyük bir dizide sol = 1.500.000.000 ve sag = 2.000.000.000 olsaydı sol + sag bu sınırı aşar ve taşma olurdu. JDK 21 ile denendiğinde (sol + sag) / 2 ifadesi −397.483.648 gibi negatif bir indis verir. sol + (sag - sol) / 2 ise doğru sonuç olan 1.750.000.000'u bulur, çünkü önce iki indisin farkı alınır ve fark hiçbir zaman sınırı aşmaz.

Sunumdaki örnekte dizi dokuz öğelidir ve hedef 34'tür. Algoritmanın her turu Tablo 4.11'de ve Şekil 4.17'de gösterilmiştir.

İlk turda ortadaki 21, 34'ten küçüktür; 21 ve solundaki dört öğe elenir. İkinci turda kalan dört öğenin ortası 30'dur ve yine hedeften küçüktür; 30 ve solundaki 25 elenir. Üçüncü turda iki öğe kalmıştır. 7 + (8 − 7) / 2 = 7'dir ve dizi[7] = 34 bulunur. İkili arama hedefi 3 turda bulmuştur. Doğrusal arama aynı dizide 34'e ulaşmak için 8 karşılaştırma yapardı.

4.6.3İkili arama: hedef bulunamadığında

İkili aramanın en kolay yanlış anlaşılan yanı, hedef dizide olmadığında nasıl durduğudur. Bunu görmek için sekiz öğeli {3, 8, 12, 17, 21, 25, 30, 40} dizisinde 19 aranır. 19 dizide yoktur; olsaydı 17 ile 21 arasında, 4 numaralı konumda olurdu.

Üçüncü turdan sonra sol = 4, sag = 3'tür. sol ile sag yer değiştirmiş, yani sol, sag'ı geçmiştir. 4 ≤ 3 koşulu yanlış olduğu için döngü biter ve −1 döndürülür. Algoritma 3 turda “yok” cevabını vermiştir; sekiz öğenin hepsine tek tek bakılmamıştır. Döngünün bittiği anda sol'un değeri de anlamlıdır: 4, hedefin dizide olsaydı bulunacağı konumdur.

Java'nın kendi kütüphanesi bu bilgiyi kullanır. java.util.Arrays.binarySearch metodu, hedef bulunamadığında −1 yerine −(ekleme noktası) − 1 değerini döndürür. Aynı dizide 19 için JDK 21'in döndürdüğü değer −5'tir: −4 − 1 = −5. Değer negatif olduğu için “bulunamadı” anlamı korunur; ayrıca hedefin hangi konuma eklenmesi gerektiği de öğrenilir.

İkili aramanın maliyeti tur sayısıyla ölçülür. Her turda aralıktaki öğe sayısı yarıdan biraz daha aza iner, çünkü orta da elenir. n öğeli bir dizide aralık en çok ⌊log₂ n⌋ + 1 turda boşalır. Sekiz öğeli dizide ⌊log₂ 8⌋ + 1 = 3 + 1 = 4 tur sınırı vardır; 19 araması 3 turda bitmiştir. Bir milyon öğeli dizide sınır 20 turdur. Bu yüzden ikili aramanın zaman karmaşıklığı O(log n)'dir. Ek bellek gereksinimi sol, sag ve orta değişkenlerinden ibarettir; alan karmaşıklığı O(1)'dir.

4.6.4Arama yöntemlerinin karşılaştırılması

İki arama yöntemi farklı koşullar için uygundur. Tablo 4.13 farkları özetler.

Tablodaki “yapı” satırı bir ayrıntıya dikkat çeker. İkili arama, her turda dizinin ortasındaki öğeye doğrudan ulaşabilmeye dayanır. Bir öğeye indisiyle, öncekilerden geçmeden tek adımda ulaşmaya rastgele erişim (random access) denir. Diziler rastgele erişimlidir. Bir dosyadan ya da ağdan sırayla gelen veride ise ortadaki öğeye ulaşmak için önceki bütün öğelerin okunması gerekir; bu tür verilerde doğrusal arama tek seçenektir.

Şekil 4.19 iki yöntemin aynı hedef için baktığı öğeleri gösterir. Dizi 16 öğeli ve hedef son öğe olduğunda ikili arama sırasıyla 8., 12., 14., 15. ve 16. öğelere bakar. Bu küçük örnekte bile fark üç kattan fazladır. Fark, dizi büyüdükçe hızla açılır.

Şekil 4.20 farkın nasıl büyüdüğünü çizer. Doğrusal aramanın eğrisi düz bir çizgidir; n iki katına çıkınca karşılaştırma sayısı da iki katına çıkar. İkili aramanın eğrisi ise basamak basamak ve çok yavaş yükselir: n iki katına çıkınca tur sayısı yalnızca bir artar. n = 1.000.000 için doğrusal arama bir milyon, ikili arama yalnızca 20 karşılaştırma yapar.

Bu üstünlüğün bir bedeli vardır: ikili arama sıralı veri ister. Veri sıralı değilse önce sıralanması gerekir. Sıralama, aramanın kendisinden çok daha pahalı bir iştir; en iyi genel amaçlı yöntemler bile O(n log n) zaman alır. Tek bir arama için önce sıralayıp sonra ikili arama yapmak, doğrudan doğrusal arama yapmaktan daha pahalıdır. Aynı veride binlerce arama yapılacaksa ise bir kez sıralamak kendini hızla öder.

4.7Sıralama

Bir veri topluluğunun öğelerini belirli bir düzene, örneğin küçükten büyüğe dizmeye sıralama (sorting) denir. Sıralama, bilgisayarların en çok yaptığı işlerden biridir. Sınav sonuçları puana göre, e-postalar tarihe göre, ürünler fiyata göre sıralanır. Sıralamanın bir başka değeri de sonraki işleri kolaylaştırmasıdır: ikili arama yalnızca sıralı veride çalışır.

Burada dört yöntem karşılaştırılır. İlk üçü, seçimli, kabarcık ve eklemeli sıralama, kolay anlaşılır ve elle izlenebilir. Üçü de en kötü durumda O(n²) karşılaştırma yapar. Dördüncüsü olan birleştirme sıralaması farklı bir fikre dayanır ve büyük dizilerde çok daha hızlıdır. Bütün yöntemler diziyi küçükten büyüğe sıralar. Karşılaştırmalarda ve takaslarda kullanılan iki komşu öğeye kısaca komşu (adjacent) öğeler denir.

4.7.1Seçimli sıralama

Bir kişi elindeki kâğıtları sıralarken önce en küçüğünü bulup en başa koyabilir, sonra kalanlar arasında en küçüğü bulup ikinci sıraya koyabilir. Bu doğal yöntemin adı seçimli sıralamadır.

i = 0'dan n-2'ye kadar
    enK = i
    j = i+1'den n-1'e kadar
        eğer dizi[j] < dizi[enK] ise enK = j
    dizi[i] ile dizi[enK] yer değiştir

Dış döngünün her turuna bir geçiş (pass) denir. i'nci geçişin başında dizinin 0…i − 1 bölümü sıralıdır ve en küçük i öğeyi tutar; i…n − 1 bölümü sıralanmamıştır. enK değişkeni, o ana kadar bulunan en küçük öğenin indisidir. Başta sıralanmamış bölümün ilk öğesi en küçük kabul edilir. İç döngü bölümün geri kalan öğelerini tek tek enK'deki öğeyle karşılaştırır; daha küçüğü bulununca enK güncellenir. İç döngü bitince en küçük öğe, i konumundaki öğeyle yer değiştirir ve sıralı bölüm bir öğe büyür.

Sunumdaki örnek dizi {29, 10, 14, 37, 13}'tür. Her geçişin sonucu Tablo 4.14'te verilmiştir.

Tablonun satırları şöyle okunur. i = 0'da aday en küçük 29'dur. dizi[1] = 10 daha küçüktür ve enK = 1 olur; 14, 37 ve 13, 10'dan küçük değildir. 10 başa taşınır. i = 1'de aday 29'dur. Önce 14 bulunur (enK = 2), sonra 13 daha da küçüktür (enK = 4). 13 ile 29 yer değiştirir. i = 2'de aday 14'tür ve kalan 37 ile 29'dan küçüktür; en küçük zaten yerindedir. Algoritma bu geçişte dizi[2]'yi kendisiyle “yer değiştirir”; işlem etkisizdir. i = 3'te 29 ile 37 yer değiştirir ve dizi sıralanır.

Karşılaştırma sayısı dizinin içeriğine hiç bağlı değildir. i = 0'da iç döngü n − 1, i = 1'de n − 2, …, son geçişte 1 karşılaştırma yapar. Toplam:

Bu, Gauss formülünün n yerine n − 1 konmuş hâlidir. n = 5 için 4 + 3 + 2 + 1 = 10 karşılaştırma eder; sunumdaki izlemede de 10 karşılaştırma sayılmıştır. Dizi zaten sıralı olsa bile algoritma her geçişte en küçüğü yeniden arar ve yine 10 karşılaştırma yapar. Bu yüzden seçimli sıralama en iyi durumda da en kötü durumda da O(n²)'dir. Buna karşılık takas sayısı azdır: her geçişte en çok bir takas yapılır, toplam en çok n − 1. Yalnızca birkaç yardımcı değişken gerekir; alan karmaşıklığı O(1)'dir.

4.7.2Kabarcık sıralaması

Kabarcık sıralaması yalnızca yan yana duran öğeleri karşılaştırır. Bir geçişte dizi soldan sağa taranır ve sırası yanlış olan her komşu çift yer değiştirir. Büyük değerler, sudaki kabarcıklar gibi her geçişte sağa doğru yükselir.

tur = 0
tekrarla
    degisti = yanlış
    j = 0'dan n-2-tur'a kadar
        eğer dizi[j] > dizi[j+1] ise
            dizi[j] ile dizi[j+1] yer değiştir
            degisti = doğru
    tur = tur + 1
degisti yanlış olana kadar

Bir geçişin sonunda, kalan öğelerin en büyüğü kesinlikle en sağa ulaşmıştır. Bunun nedeni şudur: en büyük öğe hangi konumda olursa olsun, sağındaki komşusuyla her karşılaştırmada kazanır ve bir sağa kayar. Bu yüzden her geçiş bir öncekinden bir öğe kısadır. tur değişkeni tamamlanan geçiş sayısını tutar ve iç döngünün sınırını n − 2 − tur olarak kısaltır.

degisti değişkeni algoritmanın erken durma özelliğini sağlar. Her geçişin başında yanlış yapılır; geçişte bir takas olursa doğru olur. Bir geçişte hiç takas olmamışsa bütün komşu çiftler doğru sıradadır, yani dizi sıralıdır. Bu durumda geçiş sürdürülmez, algoritma durur. Döngünün “tekrarla … olana kadar” biçiminde yazılması, koşulun gövdeden sonra denetlendiğini gösterir: gövde en az bir kez çalışır.

Tablo 4.15 sunumdaki {5, 1, 4, 2, 8} dizisinin üç geçişini gösterir. 1. geçişte 5, sırasıyla 1, 4 ve 2 ile yer değiştirerek 3 numaralı konuma ilerler. 8 ile karşılaştırıldığında sıra doğrudur; 8 zaten en büyüktür ve en sağdadır. Geçiş sonunda 8 kesin yerindedir. 2. geçişte yalnızca 4 ile 2 yer değiştirir ve dizi sıralanır. Bunu algoritma henüz bilmez: degisti doğrudur, bir geçiş daha yapılır. 3. geçişte hiç takas olmaz; degisti yanlış kalır ve algoritma durur. Toplam 4 + 3 + 2 = 9 karşılaştırma yapılmıştır.

Kabarcık sıralamasının maliyeti girdiye bağlıdır. En kötü durumda, dizi ters sıralıyken, her geçişte bütün çiftler yer değiştirir ve n − 1 geçiş gerekir. Karşılaştırma sayısı seçimli sıralamadaki gibi n(n − 1)/2'dir; zaman karmaşıklığı O(n²)'dir. En iyi durumda dizi zaten sıralıdır. İlk geçişte n − 1 karşılaştırma yapılır, hiç takas olmaz ve algoritma durur: O(n). Erken durma olmasaydı algoritma sıralı dizide de bütün geçişleri boşuna yapardı. Ek bellek O(1)'dir.

4.7.3Eklemeli sıralama

Kâğıt oyunlarında oyuncular eldeki kâğıtları genellikle şöyle dizer: yeni bir kâğıt alındığında, elde zaten sıralı duran kâğıtların arasında doğru yer bulunur ve kâğıt oraya sokulur. Eklemeli sıralama bu yöntemin aynısıdır.

i = 1'den n-1'e kadar
    anahtar = dizi[i]
    j = i - 1
    j >= 0 ve dizi[j] > anahtar iken
        dizi[j+1] = dizi[j]
        j = j - 1
    dizi[j+1] = anahtar

Dış döngü i'yi 1'den başlatır, çünkü tek öğeli bir bölüm (0…0) zaten sıralıdır. Her turda anahtar, dizi[i]'den alınır; anahtarın yeri artık “boşluk” sayılabilir. j, anahtarın solundaki öğeden başlar. İç döngü iki koşulla sürer: j dizinin içinde olmalı (j ≥ 0) ve dizi[j] anahtardan büyük olmalıdır. Koşul sağlandıkça dizi[j] bir sağa kaydırılır ve j bir azalır; boşluk sola doğru ilerler. Döngü durduğunda boşluk j + 1 konumundadır ve anahtar oraya yazılır.

Koşuldaki j >= 0 denetiminin önce yazılması önemlidir. j = −1 olduğunda bu koşul yanlıştır. “ve” bağlacı, ilk koşul yanlışsa ikinciye hiç bakmaz; dizi[−1] okunmaya çalışılmaz. İki koşulun sırası değiştirilirse anahtar en başa yerleşeceği zaman dizi[−1] okunur ve program hata verir.

Tablo 4.16 sunumdaki {4, 3, 5, 1} dizisinin izlemesidir. i = 1'de anahtar 3'tür; 4 > 3 olduğu için 4 sağa kayar, j = −1 olur ve döngü sol uca geldiği için durur. 3, 0 konumuna yerleşir. i = 2'de anahtar 5'tir; solundaki 4 ondan küçüktür ve tek karşılaştırmayla yeri bulunur, hiç kaydırma yapılmaz. i = 3'te anahtar 1 bütün öğelerden küçüktür. 5, 4 ve 3 sırayla sağa kayar ve 1 en başa yerleşir. Toplam 1 + 1 + 3 = 5 karşılaştırma yapılmıştır.

Eklemeli sıralamanın maliyeti, öğelerin ne kadar “yanlış yerde” olduğuna bağlıdır. En kötü durumda dizi ters sıralıdır; her anahtar sıralı bölümün en başına kadar kaydırılır ve n(n − 1)/2 karşılaştırma yapılır: O(n²). En iyi durumda dizi zaten sıralıdır; her anahtar için tek karşılaştırma yapılır ve hiç kaydırma olmaz. Toplam n − 1 karşılaştırma: O(n). Ek bellek yalnızca anahtar ve j değişkenleridir: O(1).

Bu özellik eklemeli sıralamayı uygulamada değerli kılar. Az sayıda öğe içeren ya da neredeyse sıralı olan dizilerde çok hızlı çalışır. Sıralı bir listeye arada bir yeni kayıt eklenen durumlarda, örneğin her gün birkaç öğrencinin eklendiği alfabetik bir listede, eklemeli sıralama doğal bir seçimdir.

4.7.4Birleştirme sıralaması

Önceki üç yöntem öğeleri tek tek yerine koyar ve O(n²) karşılaştırma yapar. Birleştirme sıralaması (merge sort) başka bir fikre dayanır: iki sıralı diziyi tek bir sıralı dizide birleştirmek çok ucuzdur. İki sıralı dizinin en küçük öğesi, ikisinin ilk öğelerinden küçük olanıdır. O öğe alınır ve aynı karşılaştırma kalan öğeler için tekrarlanır. Her karşılaştırma sonuca bir öğe ekler; toplam öğe sayısı m ise en çok m − 1 karşılaştırma yeter.

Algoritma bu birleştirme işlemini şöyle kullanır. Dizi ortadan iki yarıya bölünür. Her yarı aynı yöntemle ayrı ayrı sıralanır. Sonra sıralı iki yarı birleştirilir. Yarılar da bölüne bölüne sonunda tek öğeli dizilere iner; tek öğeli bir dizi zaten sıralıdır. Bir problemi aynı türden küçük problemlere bölüp onların çözümlerini birleştirmeye böl ve fethet (divide and conquer) yaklaşımı denir.

birleştir(A, B):
    C = boş dizi
    i = 0, j = 0
    i < A.uzunluk ve j < B.uzunluk iken
        eğer A[i] ≤ B[j] ise C'nin sonuna A[i] ekle, i = i + 1
        değilse C'nin sonuna B[j] ekle, j = j + 1
    A ve B'de kalan öğeleri sırasıyla C'nin sonuna ekle
    C'yi döndür

sirala(dizi):
    eğer dizi en çok 1 öğeliyse diziyi döndür
    diziyi ortadan iki yarıya böl: sol ve sag
    birleştir(sirala(sol), sirala(sag)) sonucunu döndür

sirala işlemi kendini daha küçük diziler için yeniden çağırır. Kendi tanımında yeniden kullanılan böyle bir işleme özyinelemeli işlem denir. Özyinelemeyi ayrıntısıyla anlamak bu not için gerekli değildir; önemli olan, bölme işinin tek öğeli dizilere inince durması ve her düzeydeki birleştirmenin sonucu bir üst düzeye iletmesidir.

Birleştirme sıralamasının maliyeti düzey sayısından gelir. Dizi her düzeyde ikiye bölündüğü için log₂ n düzey vardır; 8 öğede 3 düzey. Her düzeyde bütün öğeler bir kez birleştirmeye girer ve en çok n karşılaştırma yapılır. Toplam karşılaştırma yaklaşık n × log₂ n'dir; zaman karmaşıklığı en iyi, ortalama ve en kötü durumda O(n log n)'dir. Bedeli bellektir: birleştirme sonucu ayrı bir dizide oluşturulur. Bu yüzden ek bellek O(n)'dir.

4.7.5Sıralama yöntemlerinin karşılaştırılması

Tablo 4.17 dört yöntemi karmaşıklık açısından özetler. Büyük O değerleri aynı olan yöntemler bile gerçekte farklı sayıda karşılaştırma yapar. Tablo 4.18 üç basit yöntemi aynı beş öğeli dizilerde çalıştırarak sayar.

Tablo, karmaşıklık tablosundaki “en iyi” sütununu sayılarla doğrular. Sıralı dizide seçimli sıralama yine 10 karşılaştırma yapar; kabarcık ve eklemeli sıralama 4 karşılaştırmayla işi bitirir. Ters sıralı dizide üç yöntem de 10 karşılaştırma yapar, ama seçimli sıralama yalnızca 2 takasla yetinir. Seçimli sıralamanın az takas yapması, yazma işleminin pahalı olduğu durumlarda bir üstünlüktür.

Şekil 4.26 rastgele dizilerdeki ortalama davranışı gösterir. Seçimli ve kabarcık sıralaması yaklaşık n² / 2 karşılaştırma yapar; n = 60 için seçimli tam 60 × 59 / 2 = 1.770'tir. Eklemeli sıralama ortalamada bunun yaklaşık yarısını, n² / 4 civarını yapar. Bunun nedeni, rastgele bir dizide her anahtarın sıralı bölümün ortalama yarısını geçmesidir. Birleştirme sıralaması ise n log₂ n civarında kalır ve n büyüdükçe fark hızla açılır. Bu notun hesabında 2.000 rastgele diziyle yapılan ortalama, n = 60 için kabarcıkta yaklaşık 1.730, eklemelide 939, birleştirmede 281 çıkmıştır; sunumdaki 20 dizilik ortalamalar bu değerlere yakındır.

Uygulamada hazır kütüphane yöntemleri kullanılır. Java'daki java.util.Arrays.sort metodu O(n log n) zamanlı gelişmiş yöntemler kullanır. Nesne dizilerinde kullanılan yöntem (Timsort), birleştirme ve eklemeli sıralamanın fikirlerini birleştirir. int gibi temel tip dizilerinde çift pivotlu hızlı sıralama kullanılır. İki yöntem de küçük dizi parçalarında eklemeli sıralamaya geçer, çünkü eklemeli sıralama küçük ve neredeyse sıralı veride hızlıdır. Basit yöntemleri öğrenmenin değeri, bu tasarım kararlarının nedenini anlamayı sağlamasıdır.

Sıralama algoritmalarının nasıl çalıştığını gözle görmek, izleme tablolarını tamamlar. Sıralama algoritmaları görselleştiricisi, dört yöntemi rastgele, sıralı, ters sıralı ve neredeyse sıralı dizilerde adım adım çalıştırır ve karşılaştırma sayılarını gösterir.

4.8Özet

• Problem çözme kodla başlamaz: problem anlaşılır, küçük bir örnek elle çözülür, yöntem yazılır, en son kodlanır. Problem tanımı amaç, girdi, çıktı, kısıt, örnek ve hata durumundan oluşur.
• Algoritma, bir problemi çözmek için tanımlanmış sonlu adımlar dizisidir; sıfır ya da daha fazla girdi alır, en az bir çıktı üretir. İyi bir algoritmanın adımları kesin, sıralı ve uygulanabilirdir; algoritma sonlu adımda durur, geçerli her girdi için doğru sonuç verir ve kaynakları verimli kullanır.
• Algoritma tasarımı bir döngüdür: örneği çöz, genel kuralı bul, sözde kod yaz, elle izle, düzelt. Sözde kod, algoritmayı belirli bir dile bağlı kalmadan yazar; girinti, koşul ve döngülerin kapsamını gösterir.
• İki değişkenin takası üç atama ve bir geçici değişken ister. Fibonacci'deki atama sırası da aynı nedenle önemlidir: üzerine yazılacak bir değer önce kullanılır ya da saklanır.
• Bir sonucu adım adım biriktiren biriktiricinin başlangıç değeri işleme göre seçilir: toplam için 0, çarpım için 1. Faktöriyel algoritmasının döngü değişmezi “her tur başında sonuc = (i − 1)!” ifadesidir ve algoritmanın neden doğru olduğunu açıklar.
• Palindrom denetimi iki uçtan ortaya ilerler ve en çok ⌊n / 2⌋ karşılaştırma yapar. Asal sayı denetimi bölenleri yalnızca √n'e kadar arar (i × i ≤ n). İki algoritma da sonuç belli olunca erken durur.
• Elle izleme ve izleme tablosu, algoritmanın bir girdi için doğru çalıştığını gösterir. Test durumları normal, sınır, geçersiz ve büyük girdileri kapsar. Tek bir başarılı test, algoritmanın her girdi için doğru olduğunu kanıtlamaz; 21! testi taşmayı ve eksik kısıt denetimini ortaya çıkarır.
• Zaman karmaşıklığı işlem sayısının, alan karmaşıklığı ek belleğin girdi boyutuyla nasıl büyüdüğünü anlatır ve büyük O gösterimiyle yazılır: O(1), O(log n), O(n), O(n log n), O(n²). 1 + 2 + … + n toplamı döngüyle O(n), Gauss formülüyle O(1) zamanda bulunur.
• Doğrusal arama sıralama istemez ve en kötü durumda n karşılaştırma yapar: O(n). İkili arama yalnızca sıralı veride çalışır, her turda aralığı yarılar ve en çok ⌊log₂ n⌋ + 1 tur yapar: O(log n). n = 1.000.000'da fark 1.000.000'a karşı 20'dir.
• Seçimli sıralama her geçişte en küçüğü seçer; her zaman n(n − 1)/2 karşılaştırma yapar ama en çok n − 1 takas yapar. Kabarcık sıralaması komşuları değiştirir ve değişim olmayan geçişte durur. Eklemeli sıralama anahtarı sıralı bölüme sokar; neredeyse sıralı veride çok hızlıdır. Üçü de en kötü durumda O(n²), ek alanda O(1)'dir.
• Birleştirme sıralaması diziyi ikiye böler, yarıları sıralar ve birleştirir; her durumda O(n log n) zaman, O(n) ek bellek kullanır.

4.9Kavram listesi

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

• problem çözme problem solving
• problem tanımı problem definition
• kısıt constraint
• algoritma algorithm
• kesinlik definiteness
• sonluluk finiteness
• doğruluk correctness
• sözde kod pseudocode
• girinti indentation
• takas swap
• geçici değişken temporary variable
• faktöriyel factorial
• biriktirici accumulator
• döngü değişmezi loop invariant
• sınır hatası off-by-one error
• kayan pencere sliding window
• palindrom palindrome
• asal sayı prime number
• bölen divisor
• kalan remainder
• elle izleme hand tracing
• izleme tablosu trace table
• test durumu test case
• geçersiz girdi invalid input
• taşma overflow
• zaman karmaşıklığı time complexity
• alan karmaşıklığı space complexity
• girdi boyutu input size
• büyük O gösterimi Big O notation
• en iyi durum best case
• en kötü durum worst case
• arama search
• hedef target
• doğrusal arama linear search
• ikili arama binary search
• arama aralığı search range
• rastgele erişim random access
• sıralama sorting
• sıralı sorted
• komşu adjacent
• geçiş pass
• seçimli sıralama selection sort
• kabarcık sıralaması bubble sort
• eklemeli sıralama insertion sort
• anahtar key
• birleştirme sıralaması merge sort

4.10Kendini Dene

1. Üç sayıyı sıralayan algoritma (önce a–b, sonra b–c, en son yeniden a–b karşılaştırması) a = 4, b = 9, c = 2 için çalıştırılıyor. Her karşılaştırmadan sonra a, b, c ne olur? Kaç takas yapılır?

   Cevap

   1. karşılaştırma: 4 > 9 yanlış; değişiklik yok (4, 9, 2). 2. karşılaştırma: 9 > 2 doğru; b ile c yer değiştirir (4, 2, 9). 3. karşılaştırma: 4 > 2 doğru; a ile b yer değiştirir (2, 4, 9). Çıktı “2 4 9”dur; iki takas yapılmıştır.

2. Çift sayıların toplamını bulan algoritmada i = 2 yerine yanlışlıkla i = 1 yazılmış; artış yine i = i + 2'dir. n = 10 için ne yazılır? Hata hangi testle yakalanır?

   Cevap

   Sayaç 1, 3, 5, 7, 9 değerlerini alır ve tek sayılar toplanır: 1 + 3 + 5 + 7 + 9 = 25. Doğru cevap 30'dur. n = 1 testi de hatayı gösterir: beklenen 0, bulunan 1'dir. n = 0 testi ise hatayı göstermez, çünkü iki sürümde de döngü hiç dönmez ve 0 yazılır.

3. Asal sayı algoritması n = 97 için çalıştırılıyor. Hangi i değerleri denenir, kaç kez % işlemi yapılır, sonuç nedir?

   Cevap

   i = 2'den 9'a kadar 8 değer denenir, çünkü 9 × 9 = 81 ≤ 97, ama 10 × 10 = 100 > 97'dir. Kalanlar sırasıyla 1, 1, 1, 2, 1, 6, 1, 7'dir; hiçbiri 0 değildir. 8 kez % işlemi yapılır ve “asal” yazılır.

4. Palindrom algoritması “Kalem” ve “Kepek” metinleri için çalıştırılıyor. Her birinde kaç karşılaştırma yapılır ve sonuç ne olur?

   Cevap

   “Kalem” küçültülünce “kalem” olur. İlk karşılaştırmada metin[0] = 'k' ile metin[4] = 'm' farklıdır; 1 karşılaştırmadan sonra yanlış döndürülür. “Kepek” için k ile k, sonra e ile e aynıdır; sol = sag = 2 olunca döngü biter. 2 karşılaştırmayla doğru döndürülür.

5. {4, 8, 15, 16, 23, 42} dizisinde 16 önce doğrusal aramayla, sonra ikili aramayla aranıyor. Her yöntem kaç karşılaştırma ya da tur yapar? İkili aramada her turda sol, sag ve orta nedir?

   Cevap

   Doğrusal arama 4, 8, 15 ve 16'ya bakar; 4 karşılaştırmadan sonra 3 döndürür. İkili arama: 1. tur sol = 0, sag = 5, orta = 2, dizi[2] = 15 < 16 → sol = 3. 2. tur sol = 3, sag = 5, orta = 4, dizi[4] = 23 > 16 → sag = 3. 3. tur sol = sag = 3, orta = 3, dizi[3] = 16 → 3 döndürülür. İkili arama 3 turda bulur.

6. 4.000 öğeli sıralı bir dizide bulunmayan bir değer aranıyor. İkili arama en çok kaç tur yapar? Dizi 8.000 öğeye çıkarsa doğrusal aramanın ve ikili aramanın en kötü durumdaki işi nasıl değişir?

   Cevap

   2¹¹ = 2.048 ≤ 4.000 < 4.096 = 2¹² olduğu için ⌊log₂ 4.000⌋ = 11'dir; ikili arama en çok 11 + 1 = 12 tur yapar. Dizi iki katına çıkınca doğrusal aramanın işi de iki katına çıkar (4.000'den 8.000 karşılaştırmaya). İkili aramanın tur sayısı yalnızca bir artar ve 13 olur.

7. [3, 1, 2, 4] dizisi seçimli, erken durmalı kabarcık ve eklemeli sıralamayla sıralanıyor. Her yöntem kaç karşılaştırma yapar? Kabarcık sıralaması kaç geçiş yapar?

   Cevap

   Seçimli: 3 + 2 + 1 = 6 karşılaştırma; dizinin içeriği sonucu değiştirmez. Kabarcık: 1. geçişte (3, 1) ve (3, 2) yer değiştirir, (3, 4) doğru sıradadır; 3 karşılaştırma, dizi [1, 2, 3, 4] olur. 2. geçişte 2 karşılaştırma yapılır, hiç takas olmaz ve algoritma durur. Toplam 2 geçiş, 5 karşılaştırma. Eklemeli: anahtar 1 için 1 karşılaştırma (3 > 1, sonra j = −1), anahtar 2 için 2 karşılaştırma (3 > 2, 1 > 2 değil), anahtar 4 için 1 karşılaştırma; toplam 4. Dizi neredeyse sıralı olduğu için eklemeli sıralama en az karşılaştırmayı yapar.

8. Palindrom algoritması için en az beş test durumu ve her biri için beklenen sonuç nedir? Her test hangi olası hatayı yakalar?

   Cevap

   Örnek bir test kümesi: boş metin → doğru (döngü hiç dönmez; algoritma çökmemelidir). Tek harf, “a” → doğru. Çift uzunlukta palindrom, “abba” → doğru (sol ile sag ortada birbirini geçer). Büyük harfli palindrom, “Kayak” → doğru (temizleme kuralı uygulanmazsa yanlış çıkar). Türkçe I içeren metin, “Iı” → doğru (I, i'ye çevrilirse yanlış çıkar). Palindrom olmayan metin, “kayık” → yanlış. Son harfi farklı metin, “kayaz” → yanlış (ilk karşılaştırmada durulmalıdır).

9. Bir algoritma n = 1.000 için 2 saniye sürüyor. n = 2.000 için yaklaşık ne kadar sürmesi beklenir? Algoritma O(n), O(n²) ve O(log n) karmaşıklıkta olsaydı cevap nasıl değişirdi?

   Cevap

   O(n) bir algoritmada iş, n ile orantılı büyür; n iki katına çıkınca süre de yaklaşık iki katına çıkar: 4 saniye. O(n²) bir algoritmada iş, n'in karesiyle büyür; 2² = 4 katına çıkar: yaklaşık 8 saniye. O(log n) bir algoritmada n'in iki katına çıkması log₂ n'i yalnızca 1 artırır (yaklaşık 10'dan 11'e); süre yaklaşık %10 artar ve 2,2 saniye civarında kalır. Bunlar kaba tahminlerdir; büyük O katsayıları ve küçük terimleri yok sayar.

4.11İleri okuma

• R. Sedgewick, K. Wayne, Computer Science: An Interdisciplinary Approach (Addison-Wesley, 2016), 4.1 Performance ve 4.2 Sorting and Searching: işlem sayısını deneyle ölçmeyi, ikili aramayı ve basit sıralama yöntemlerini Java örnekleriyle anlatır; kitabın sitesinde (introcs.cs.princeton.edu) bölümlerin özetleri ve kodları vardır.
• R. Sedgewick, K. Wayne, Algorithms (4. baskı, Addison-Wesley, 2011), Bölüm 2: seçimli, eklemeli ve birleştirme sıralamasını görsel izlemelerle karşılaştırır; kitap sitesindeki (algs4.cs.princeton.edu) canlandırmalar bu nottaki izleme tablolarını tamamlar.
• A. Levitin, Introduction to the Design and Analysis of Algorithms (3. baskı, Pearson, 2012), Bölüm 1–3: algoritma kavramını, problem tanımını ve kaba kuvvet yöntemlerini (seçimli ve kabarcık sıralaması, doğrusal arama) sade bir dille ele alır.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4. baskı, MIT Press, 2022), Bölüm 2: eklemeli sıralama üzerinden döngü değişmezi ile doğruluk kanıtını ve birleştirme sıralamasının analizini kesin biçimde verir; konuya ileri düzeyde devam etmek isteyenler içindir.

4.12Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
2. A. Levitin, Introduction to the Design and Analysis of Algorithms, 3. baskı, Pearson, 2012.
3. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011. Kitap sitesi.
4. R. Sedgewick, K. Wayne, Computer Science: An Interdisciplinary Approach, Addison-Wesley, 2016: 4.1 Performance, 4.2 Sorting and Searching.
5. Oracle, Java SE 21 API: java.util.Arrays (sort, binarySearch).

İlgili sayfalar: Algoritmalar sunumu · Çalışma soruları · Sıralama algoritmaları görselleştirici · Akış diyagramı yürütücü · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.