ALGORİTMALAR VE PROGRAMLAMA - Deneme Sınavı - 11

Algoritma incelendiğinde aramanın dizinin son elemanından ilk elemanına doğru yapıldığı anlaşılır. -3 dizinin sondan 5. elemanı ve 0 dizinin sondan 3. elemanı olduğundan 5+3 = 8 karşılaştırma yapmak gerekir.

İkili arama yapılabilmesi için dizilerin sıralı olması gerekmektedir. Dikkatli incelendiğinde II dizisi alfabetik olarak sıralı bir dizidir. III dizisi de sıralı bir dizidir. Ancak I dizisi sıralı değildir. II ve III dizileri ikili arama için uygundur.

İkili arama yöntemi kullanıldığında iki elemanın da dizide olmadığı göz önünde bulundurularak her biri için 3 karşılaştırma yapılması gerektiği anlaşılmaktadır. Toplam 3+3 = 6 karşılaştırma yapmak gerekir.

İkili arama yapılırken 62 arayalım. Önce dizinin ortasındaki sayı yani 45 sayısı ile 62 sayısı karşılaştırılacaktır. 62 45’den büyük olduğu için dizinin sağ tarafındaki sayılar yani 54 58 62 87 100 sayılarının ortasındaki sayı bulunacak bu sayı 62 olunca arama bitirilecektir. Dolayısıyla 2 karşılaştırma yapılmış olacaktır. 45 sayısı da 1 arşılaştırmayla bulunacağından 1 + 2 = 3 karşılaştırmaya ihtiyaç vardır.

Çok yüksek miktarda ikili arama sonucu aranılan elemanlar bazen 1. bazen 2. bazen 3. vb… bazen de 9. karşılaştırmada bulunacaktır. Sonuçta ortalamaya vurulduğu takdirde (1 + 9) / 2 = 5 sonucuna ulaşılmaktadır.(İkili aramada en hızlı cevap 1. karşılaştırmada, en yavaş cevap da log2(512) = 9 karşılaştırmada elde edilecektir.)

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(log(n)) olduğunu söyleyebiliriz. Bu biliglerden de anlaşıldığı gibi doğru cevap C'dir.

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.

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.

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.

Zaman karmaşıklığı (time complexity) algoritmaların sonuca ulaşması için gerekli olan zaman hakkında bilgi veren bir ölçüttür. En kötü durumdaki zaman karmaşıklığı, algoritmanın çalışmasının en uzun

sürebileceği durumu ifade etmek için kullanılır.

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           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(log(n)) olduğunu söyleyebiliriz.

Ardışık arama yapılarak 1’i bulmak için dizide 4 işlem yapılır. 8’i bulmak için ise 7 işlem yapılır. Toplamda 11 işlem yapılır.

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.yukarıdaki diziler ardışıktır ve dolayısıyla hepsi üzerinde ardışık arama algoritması uygulanabilir.

İkili arama algoritmasına yönelik bir C program kodunda main fonksiyonu ile program kodları çalışmaya başlar.

İkili arama algoritmasına yönelik bir C program kodunda ikili_arama fonksiyonuna arama işlemi için parametre gönderilir.

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.

Ardışık arama yapılara 16’yı bulmak için dizide 4 işlem yapılır. 2’yi bulmak için ise 3 işlem yapılır. Toplamda 7 işlem yapılır.

Dizinin sıralı olmasına ihtiyaç duyulmayan algoritma türü ardışık algoritmadır.

ilk olarak 13 sonra 9 sonra 21 sonra 6 bulunur.

5 rakamı dizinin içerisinde olmadığı için sonuç bulunamaz.

Ilk karşılaştırmada 5 bulunur 5’in sağ tarafından devam edilir 7 bulunur 7’nin sol tarafında 6 değerine ulaşılır.