Sıralama ve Arama Algoritmaları

Konu Anlatımı

Sıralama ve Arama Algoritmaları

Bir dizideki on iki sayının karışık hâlde durması ile aynı sayıların artan düzende sıralı olması, o sayılar arasında arama yapılırken harcanan işi tamamen değiştirir. Sıralama algoritmaları veriyi istenen düzene getirir; arama algoritmaları ise sıralı ya da sırasız veride istenen değeri bulmaya çalışır. Bu konuda her iki işlem de küçük ölçekli örneklerle ele alınacak ve karşılaştırma sayısı üzerinden hangi yöntemin ne zaman daha verimli olduğu gösterilecektir.

Bu derste ne öğreneceğiz?

Bu konuda üç temel sıralama algoritmasının nasıl çalıştığını adım adım öğreneceğiz. Kabarcık sıralama, seçme sıralama ve eklemeli sıralama için küçük diziler üzerinde elle takip yapıp hangi elemanın ne zaman yer değiştirdiğini göstereceğiz. Ardından sıralı arama ile ikili aramanın farkını inceleyecek, arama için ön koşul olup olmadığını sorgulayacağız. Son olarak karşılaştırma sayısının veri boyutuna nasıl bağlandığını sayısal örneklerle tartışacağız.

Ön bilgi

Ön bilgi olarak dizi kavramı gerekir. Dizi, aynı veri tipinde olan değerlerin sıralı biçimde bellekte tutulduğu yapıdır ve her dizi elemanının bir sıra numarası vardır. Dizi elemanına erişmek, sıra numarasını bilmeyi gerektirir; sıra numarası bilinmiyorsa arama yapılmak zorundadır.

İkinci ön bilgi, döngü içinde koşul kullanımıdır. Sıralama algoritmaları iç içe iki döngü kurar: dış döngü kaçıncı turda olunduğunu, iç döngü hangi eleman çiftinin karşılaştırılacağını belirler. Dizi elemanlarını karşılaştırıp yer değiştirmek için üçüncü bir işlem gerekir; bu işlem geçici bir değişken kullanılarak yapılır.

Sıralama nedir, neden gerekir?

Sıralama, dizi elemanlarını bir ölçüte göre yeniden dizmektir. Ölçüt çoğunlukla sayısal büyüklük ya da alfabetik sıradır. Sıralamanın temel yararı arama hızını artırmasıdır: sıralı bir dizide bir değerin bulunup bulunmadığı ilk bakışta anlaşılabilir, sırasız dizide ise baştan sona taramak gerekir.

İkinci yararı veri okunabilirliğidir. Sıralı bir liste, insan gözünde çok daha hızlı taranır. Üçüncü yararı ise bazı işlemlerde verinin önceden hazırlanmış olmasıdır: en küçük, en büyük, ortanca değerler sıralı dizide bir bakışta bulunur. Bu yüzden sıralama yalnızca bir görsel düzen değil, sonraki adımları hızlandıran bir hazırlıktır.

Kabarcık sıralaması

Kabarcık sıralamada yan yana iki eleman karşılaştırılır; sıralama düzenine aykırı olan küçük eleman sola, büyük eleman sağa geçirilir. Bir tur içinde dizi baştan sona taranır ve bu sırada büyük elemanlar kademeli olarak sağa doğru yerleşir. Her turda en büyük eleman sonuna oturduğu için dış döngüde bir eleman eksik kalmış gibi davranılır.

En kötü durumda n elemanlı dizide dış döngü n eksi bir kez, iç döngü her turda bir azalarak çalışır. Karşılaştırma sayısı toplamı 1'den n eksi 1'e kadar olan sayıların toplamıdır. Dört elemanlı bir dizide bu toplam 4 + 3 + 2 + 1 = 10 karşılaştırmadır. Dizi baştan ters sırada ise bu en kötü durum gerçekleşir; zaten sıralı bir dizide ise ilk turda hiç yer değiştirme olmaz ve algoritma erkenden durdurulabilir.

Seçme sıralaması

Seçme sıralamasında her turda dizinin kalan bölümündeki en küçük eleman bulunur ve o eleman, bölümün başındaki konuma taşınır. Böylece elemanlar yavaş yavaş yerlerine oturur. Karşılaştırma sayısı kabarcık sıralamasıyla aynı toplama dayanır, ancak yer değiştirme sayısı çok daha azdır; çünkü bir turda en fazla bir yer değiştirme yapılır.

Sekiz elemanlı bir dizide en kötü durumdaki toplam karşılaştırma sayısı 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36'dır. Bu toplam, dizi eleman sayısı arttıkça hızla büyür; bu yüzden seçme sıralaması az elemanlı dizilerde anlatımı kolay olduğu için öğretim amaçlı, çok elemanlı gerçek veride ise verimsiz olduğu için tercih edilmez.

Eklemeli sıralaması

Eklemeli sıralamada dizinin başındaki küçük bir bölümün sıralı olduğu varsayılır. Her adımda dizideki bir sonraki eleman alınır ve soldaki sıralı bölümde doğru yeri bulunana kadar geriye doğru kaydırılır. Bu kaydırma işlemi, yelkenli bir gemiyi limana yanaştırırken halatın geriye doğru çekilmesine benzer.

Beş elemana eklemeli sıralama uygulanırsa en kötü durumdaki karşılaştırma toplamı 1 + 2 + 3 + 4 = 10'dur. Veri çoktan sıralıysa her eleman ilk denemede yerine oturur ve toplam karşılaştırma sayısı eleman sayısına yakın kalır. Bu davranış, veri yavaş yavaş gelen bir listede eklemeli sıralamayı pratikte çok verimli kılar.

Sıralı arama ve sırasız arama

Sıralı arama, diziyi baştan sona tarayarak hedefi arar ve dizinin sıralı olup olmadığına bakmaz. Doğru çalışması için ön koşulu yoktur; fakat en kötü durumda hedef sonda ise bütün elemanlar karşılaştırılır. Dizi uzunluğu n ise en kötü durumdaki karşılaştırma sayısı doğrudan n olur.

Ortalama ise daha iyimserdir. Aranan değerin listenin herhangi bir yerinde eşit olasılıkla bulunduğu kabul edilirse, o n elemanlı dizide ortalama 1000 / 2 = 500 karşılaştırma yapılır. Bu ortalama, arama sonucunun her seferinde aynı yerde olmadığını gösterir; belli bir değeri sık arayan bir program için bu ortalama yanıltıcı olabilir.

İkili arama

İkili arama yalnızca sıralı dizilerde çalışır. Dizinin ortasındaki eleman hedefle karşılaştırılır; hedef daha küçükse sol yarı, daha büyükse sağ yarı alınır ve arama yalnızca bu yarı üzerinde sürdürülür. Her adımda arama alanı yarıya iner, bu yüzden çok sayıda eleman bulunsa bile sonuç hızla yaklaşır.

Üç elemanlı bir dizide arama en fazla iki adımda sonuçlanır: ilk adımda ortadaki eleman denenir, gerekirse kalan bölge en çok iki elemandır ve ikinci adımda onlardan biri denenir. Genel olarak n elemanlı dizide en fazla log2 n adım gerekir. Bin elemanlı bir dizide bu sayı on adımdır; oysa sıralı arama aynı işi bin adımda yapabilir.

Karşılaştırma sayısı ve büyüme hızı

Bir algoritmanın kaç adım çalıştığı, veri sayısı arttıkça nasıl büyüdüğüyle tanımlanır. Doğrusal büyüyen algoritmalarda adım sayısı veri sayısıyla, logaritmik büyüyenlerde ise çok daha yavaş artar. Bu ayrım, küçük listede fark edilmezken büyük listede belirleyici hâle gelir.