Ünite 6: Arama Algoritmaları

Giriş

Arama, genel olarak dizilerin veya herhangi bir veri yapısının içerisinde bir elemanın bulunup bulunmadığının tespiti şeklinde ifade edilebilir. Söz konusu elemanın veri yapısı içerisinde bulunduğu tespit edilirse konum bilgisinin elde edilmesi de söz konusu olabilir. Arama algoritmaları, arama işlemini birbirlerinden farklı yöntemlerle gerçekleştirirler.

Geliştirilmiş çeşitli arama algoritmaları bulunmaktadır. Temel arama algoritmaları, ardışık arama (sequential search) ve ikili arama (binary search) algoritmalarıdır. Arama algoritmalarının hepsinin kendine özel çalışma mantıkları bulunmaktadır. Örneğin, bazı algoritmaların doğru çalışması için dizilerin sıralı durumda olması gerektiği bilinmektedir. Sıralı durumda olmayan bir diziye bu türdeki bir arama algoritmasının uygulanması için dizinin öncelikle sıralı hale getirilmesi gerekir. Böyle bir durumda ise sıralama ve arama algoritmalarının peş peşe çalışması söz konusu olur. Bu sebeplerle probleme uygun arama algoritmasının seçilmesi önemlidir.

Ardışık Arama

Ardışık arama, en temel arama algoritmasıdır. Bu algoritmanın çalışması için dizinin sıralı olmasına ihtiyaç bulunmamaktadır. Aranan eleman, sırasıyla dizinin her bir konumundaki eleman ile karşılaştırılır. Aranan elemanın değerinin dizinin elemanlarından birisiyle aynı olduğu görülürse algoritma başarılı bir şekilde sonlandırılır. Eğer aranan eleman dizinin içerisinde mevcut değilse, karşılaştırmalar dizinin ilk elemanından son elemanına kadar sürecektir.

Ardışık arama algoritmasının çalışma mantığına bir örnek olarak, 5 elemanlı bir dizi bulunmakta olup iki farklı elemanın dizinin içerisinde aranması gerçekleştirilmiş olsun. Bu elemanlar sırasıyla 11 ve 8 sayılarıdır. İlk aranan 11 sayısının dizinin 3. elemanı olduğu görülmektedir. Bu sebeple ilk arama 3. adımda başarı ile sonuçlandırılmış ve dizinin geride kalan elemanları kontrol edilmemiştir. Fakat daha sonra aranan 8 sayısı dizide bulunmamaktadır. Bu sebeple dizinin elemanlarının tamamının aranan eleman ile karşılaştırılması söz konusu olmaktadır. Bu durumda 5 elemanlı bir dizi için en kötü ihtimalde 5 adet karşılaştırma yapılması gerekmektedir.

Program kodları, main fonksiyonu ile çalışmaya başlamaktadır. Daha sonra, değerleri önceden belirlenmiş olan 5 elemanlı bir dizi ve aranacak eleman ardisik_arama isimli C fonksiyonuna parametre olarak gönderilmektedir. Algoritma kodları, bir adet for döngüsü içermektedir ve bu döngü karşılaştırma işlemlerinin akışını sağlamaktadır. C kodları verilen ardisik_arama.c uygulaması çalıştırıldığında aşağıdaki ekran görüntüsü elde edilir.

11 sayisi, dizinin 3. konumundadir.

8 sayisi dizide bulunamadi.

İkili Arama

İkili arama, sıralı diziler üzerinde arama yapmak için kullanılan bir algoritmadır. Üzerinde arama yapılacak olan dizi sıralı durumda değilse, bu algoritmanın doğru çalışabilmesi için öncelikle dizinin sıralı hale getirilmesi gerekir. İkili arama algoritması çalışmaya başladığında, ilk olarak dizinin ilk ve son elemanlarının konumları tespit edilir. Bu bilgilerden faydalanılarak orta elemanın konumu hesaplanır. Daha sonra, aranan eleman dizinin orta elemanıyla karşılaştırılır ve ikisinin eşit olup olmadığına bakılır. Aranan eleman orta elemana eşit ise arama başarılı bir şekilde sonlandırılır. Aksi takdirde, aranan elemanın dizinin orta elemanından küçük veya büyük olma durumu incelenir. Aranan eleman orta elemandan büyük ise, aramaya orta eleman ile son eleman arasındaki dizi elemanları ile devam edilir. Tam tersi durum söz konusu ise, aramaya ilk eleman ile dizinin orta elemanı arasındaki dizi elemanları ile devam edilir. Bu işlem her tekrar edildiğinde ilk, orta veya son elemanların konumlarının değişmesi söz konusu olabilir.

Örneğin, ilk ve son elemanın konumlarının 1 ve 3 olduğu durumda orta elemanın konumu bu iki sayının ortalaması olan 2 sayısı olacaktır. Buna karşın, ilk ve son elemanın konumlarının 4 ve 7 olduğu durumda orta elemanın konumu 5 olacaktır. Orta elemanın konumunun tam sayı olması zorunludur. Bu örnek hesaplamada, iki sayının ortalaması olan 5.5 sayısının ondalıklı olan kısmı bu sebeple atılmakta ve bir tam sayı elde edilmektedir. Algoritmanın çalışması tamamlandığında aranan eleman dizide bulunamamışsa, arama işlemi başarısız bir şekilde sonlandırılır.

İkili arama algoritmasının çalışma mantığının anlatıldığı bir örnekte 7 elemanlı bir dizi bulunmaktadır. Söz konusu dizi içerisinde 14 sayısının aranması söz konusudur. Algoritma çalışmaya başladığında ilk, orta ve son elemanların konumları belirlenmiştir. Şekilden de görüleceği üzere dizinin 4. konumundaki 12 sayısı orta elemandır. Daha sonra, aranan eleman olan 14 sayısının orta elemana eşit, küçük veya büyük olması durumuna bakılmaktadır. Bu sayı, orta elemandan büyük olduğu için aramaya dizinin ortası ile sonu arasındaki elemanlardan devam edilir. Bu sebeple, ilk elemanın konum bilgisi güncellenmiştir ve bu güncelleme sonrasında orta elemanın konumu yeniden hesaplanmıştır. Daha sonra, aranan eleman olan 14 sayısının yeni durumdaki orta eleman olan 20 sayısına eşit, küçük veya büyük olması durumuna bakılmaktadır. 14 sayısının orta eleman olan 20’den küçük olduğu anlaşıldığından aramaya dizinin ilk ve orta elemanı arasındaki elemanlardan devam edilir. Bu noktada da son elemanın bilgisi, bir önceki orta eleman olan 20 sayısından hemen önce gelen eleman olarak güncellenmiştir. Bu durumda, ilk ve son eleman dizinin 5. konumunda yer alan 14 sayısıdır. İlk ve son elemanın konumlarının aynı olması sebebiyle tekrar orta elemanın konumu hesaplanmıştır. Bu hesaplama sonucu ilk, orta ve son elemanın konumlarının aynı duruma geldiği şekilde de görülmektedir. Orta eleman olarak belirlenen dizinin 5.konumundaki sayının 14’e eşit olması sonucu, arama işlemi başarılı bir şekilde sonlandırılacaktır. Şekilde de görüleceği üzere 14 sayısının aranması sırasında 3 adet karşılaştırma işlemi yapılmıştır.

İkili arama algoritmasının başarısız olarak sonuçlandığı bir örnek verilmiştir. Bu örnekte, önceki örnekte verilen dizinin üzerinde 5 sayısının aranması söz konusudur. Algoritma çalışmaya başladığında ilk, orta ve son elemanın konumları belirlenmiştir. Dizinin 4. konumundaki 12 sayısı orta elemandır. Öncelikle aranan eleman olan 5 sayısının orta elemana eşit, küçük veya büyük olma durumuna bakılmaktadır. Bu sayı orta elemandan küçük olduğu için aramaya dizinin ilk ve orta elemanları arasındaki sayılardan devam edilecektir. Bu sebeple, son elemanın konum bilgisi güncellenmiş ve orta elemanın konumu yeniden hesaplanmıştır. Daha sonra aranan eleman olan 5 sayısının yeni durumdaki orta eleman olan 6 sayısına eşit, küçük veya büyük olma durumuna bakılmaktadır. 5 sayısının orta eleman olan 6’dan küçük olduğu anlaşıldığından aramaya dizinin ilk ve orta elemanı arasındaki elemanlardan devam edilir. Son güncelleme neticesinde ilk, orta ve son elemanın 2’ye eşit olduğu görülmektedir. Aranan eleman olan 5 sayısının 2’ye eşit olmaması sebebiyle, arama algoritması başarısız bir şekilde sonlandırılmıştır. 5 sayısının aranması sırasında 3 adet karşılaştırma işlemi yapılmıştır.

Program, ilk olarak main metodundan başlamaktadır. Yukarıda açıklandığı üzere, 7 elemanlı bir dizinin oluşturulduğu ve 3 farklı sayının bu dizi içerisinde ikili_arama fonksiyonu yardımıyla arandığı görülmektedir. Ayrıca dizinin eleman sayısını tespit eden bir kod satırı yer almaktadır. Arama işlemi için ikili_arama fonksiyonuna 3 adet parametre gönderilmektedir. Bu parametreler, dizinin adresi, boyutu ve aranacak değerdir. Programda görüleceği üzere ilk , orta ve son değişkenlerine başlangıç değerleri atanmaktadır. Öncelikle, algoritmanın akışı gereği aranan sayının orta değişkeninin içerdiği değerden büyük olup olmadığı kontrol edilir. Sayının, orta değişkenine eşit olduğu durumda, algoritma başarılı bir şekilde sonlandırılır. Sayının, orta değişkeninden küçük ya da büyük olması durumunda dizinin ilgili yarısı üzerinde aramalara devam edilir. Döngünün çalışması devam ettiği sürece ilk , orta ve son değişkenlerine yeni ifadeler atanır. Aranan sayı dizi içerisinde bulunduğu takdirde, ekrana bu sayının dizideki konumu yazdırılır. Aranan eleman bulunamadığı durumda ise bununla ilgili bir mesajın ekrana yazdırılması söz konusudur. ikili_arama.c program kodları çalıştırıldığında aşağıdaki ekran görüntüsü ortaya çıkmaktadır:

Ilk arama islemi:

Ilk: 1. eleman, Ortanca: 4. eleman, Son: 7. eleman

Ilk: 5. eleman, Ortanca: 6. eleman, Son: 7. eleman

Ilk: 5. eleman, Ortanca: 5. eleman, Son: 5. eleman

14 sayisi, dizinin 5. konumunda

Ikinci arama islemi:

Ilk: 1. eleman, Ortanca: 4. eleman, Son: 7. eleman

Ilk: 1. eleman, Ortanca: 2. eleman, Son: 3. eleman

6 sayisi, dizinin 2. konumunda

Ucuncu arama islemi:

Ilk: 1. eleman, Ortanca: 4. eleman, Son: 7. eleman

Ilk: 1. eleman, Ortanca: 2. eleman, Son: 3. eleman

Ilk: 1. eleman, Ortanca: 1. eleman, Son: 1. eleman

5 sayisi, dizide bulunamadı.

Ayrıca, ikili arama algoritmasının özyinelemeli (recursive) fonksiyon kullanılarak gerçekleşmesi de mümkündür. ikili_arama_ozyinelemeli.c program kodları çalıştırıldığında önceki ekran görüntüsünün aynısı ortaya çıkmaktadır.

Arama Algoritmalarının Karşılaştırılması

Ardışık arama algoritması, içerisinde arama yapılacak olan dizinin sıralı olmasına ihtiyaç duymaz. Ancak ikili arama algoritmasının doğru çalışabilmesi için dizinin sıralı olması gereklidir. Yalnızca bu açıdan değerlendirildiğinde, ardışık arama algoritması ikili arama algoritmasına göre daha üstün görünebilir. Ancak iki algoritmanın zaman karmaşıklığı (time complexity) ele alındığında, ikili arama algoritmasının daha hızlı çalışabildiği görülecektir.

Ardışık arama algoritmasının gerçeklenmesi sırasında, n elemanlı bir dizi için en fazla n adet karşılaştırma yapılması gerekmektedir. Dolayısıyla ardışık aramanın en kötü durumdaki zaman karmaşıklığının O( n ) olduğunu söyleyebiliriz. İkili arama algoritması ise n elemanlı bir dizi için en kötü durumda log ₂ ( n ) adet karşılaştırma yapmaya ihtiyaç duymaktadır. Dolayısıyla ikili arama algoritmasının en kötü durumdaki zaman karmaşıklığının O(l og ( n )) olduğunu söyleyebiliriz. Bu karşılaştırmadan görüleceği üzere, ikili arama algoritması ardışık aramaya kıyasla çok daha hızlı çalışan bir algoritmadır.

Örnek olarak, 16 elemanlı bir dizinin içerisinde arama yapılacağını ve aranan elemanın bu dizide yer almadığını varsayalım. Bu durumda, ardışık arama 16 adet karşılaştırma işlemi yaptıktan sonra sonuca ulaşacaktır. Buna karşın, ikili arama algoritması 4 adet karşılaştırma işlemi yaparak sonuca ulaşabilir. Böyle küçük bir dizi üzerinde bile, yapılacak karşılaştırma işlem sayıları arasında büyük bir fark olduğu görülmektedir. Dolayısıyla, içerisinde arama yapılacak olan dizi sıralı ise, işlem hızı açısından değerlendirildiğinde ikili arama algoritması tercih edilmelidir.