Yerleştir Sırala (İnsertion Sort) Algoritması
Tekrarlı yapılar kullanan algoritmalardan bazıları da çeşitli sıralamalar yapan algoritmalarıdır. Bu sıralayıcı algoritmalar karışık olarak verilmiş çeşitli yapıları belirli bir düzene sokarlar. Örneğin karışık olarak verilmiş bir sayı dizisini, alfabetik sıraya konması gereken bir sözcük dizisini veya boyları farklı olan birkaç çubuk varsa bunların boyuna göre sıralanması gibi sıralama işlemlerini yaparlar.
Yerleştir sırala algoritmasıyla bir sıralama yapılırken en önemli husus elemanların kendi listeleri içinde sıraya koyuluyor olmasıdır. Burada liste elemanları kendi aralarında yer değiştirir ve başka bir liste oluşturulamaz.
Örnek olarak elimizde sıraları karışmış bir kağıt yığını olduğunu ve bunları tekrar sayfa numaralarına göre düzenlememiz gerektiğini düşünelim.
Önce ilk kağıda bakalım. Elimizde tek kağıt olduğuna göre bu kağıdı sıralı kabul edebiliriz. Sonra ilk iki kağıdı ele alalım.Ve bu iki kağıdı sıraya dizelim. Bu kağıtların yerlerini değiştirmek yeterli olacaktır. Bu durumda ilk iki kağıt sıralı,diğerleri sırasızdır. Sırasız kağıtlardan en baştakini çekip çıkaralım ve bu kağıdı en yerine yerleştirelim. Bu işleme devam ederek elimizdeki kağıtları sıralayabiliriz.
Burada kritik hamleyi yapan en baştaki kağıttır. Bu elemana “pivot eleman” denir. Böylece bu algoritmayı genel bir sıralama algoritması haline getirmiş oluruz. Bunu gerçekleştirmek için aşağıdaki sözde kodları kullanırız.
Pivot elemanı geçici bir yere taşıyarak listede bir boşluk yarat.
While ( boşluğun üstündeki eleman pivot elemandan büyükse ) do
( büyük olan elemanı aşağı kaydır)
oluşan boşluğa pivot elemanı yerleştir.
Şekil 1.
Bu döngü sırasız elemanlar bitinceye kadar tekrarlanır. Pivot eleman ilk başta elimizdeki ikinci elemandır. Döngünün her dönüşünde pivot eleman biraz aşağı kayar ve nihayet pivot eleman sırasız listenin son elemanına ulaşır. Böylece kağıtlar sıralanmış olacaktır.
Yukarıdaki algoritma listede en az iki eleman olduğunu varsaymaktadır. Öte taraftan listede sadece bir eleman varsa bu liste zaten sıralıdır. O halde algoritmamızın başına şöyle bir ifade eklememiz gerekecektir:
Listenin ikinci elemanından son elemanına kadar kağıtların rengini gri yap
repeat
( gri listedeki ilk elemanın rengini beyaza dönüştür ve bu elemana pivot eleman adını ver)
Pivot elemanı geçici bir yere taşıyarak listede bir boşluk yarat.
While ( boşluğun üstündeki eleman pivot elemandan büyükse ) do
( büyük olan elemanı aşağı kaydır)
oluşan boşluğa pivot elemanı yerleştir.
Until (tüm liste beyaz olsun)
Şekil 2.
Kısacası “yerleştir-sırala (insertion sort)” algoritması sırasız listenin ilk elemanını alarak sıralı listedeki yerine yerleştirir. Bu nedenle de bu algoritmaya “yerleştir-sırala algoritması” denir. Dikkat edilirse bu algoritmada iç içe iki döngü mevcuttur. Dışarıdaki döngü denetimin başlamasını sağlar. İçerdeki döngünün denetiminde, başlama aktivitesi, pivot elemanın liste dışına alınarak listede boşluk yaratılmasıdır. Böylece listedeki boşluk yukarıya taşınmış olur. Bitiş koşuluysa listedeki boşluğun pivot elemandan büyük olmayan bir değerin hemen altında yer alması veya boşluğun listenin en tepesine erişmesidir [1].
ÖZYİNELEMELİ YAPILAR
Algoritmaları geliştirirken tekrar eden işlemleri yapabilmek için döngüden başka yapılar da kullanılır. Özyinelemeli yapılarda bunlardan biridir.
İkili arama algoritması:
Özyinelemeli yapıları anlayabilmek için yaygın olarak kullanılan ikili arama algoritmasını inceleyelim. Bu algoritma “böl ve yönet” tekniği ile çalışmaktadır.
Bir önceki bölümde uğraştığımız problemin bir benzerini ele alalım. Elimizde kalın bir sözlük olduğunu düşünelim bu problemi çözmek için önceki bölümde önerdiğimiz ardışık arama algoritması pek verimli olmaz. Bu işlemi elle yapsaydık elimizi aradığımız harfin olduğu yere yakın bir yere koyardık. Sonra da açtığımız sayfaya göre ileri veya geri giderek aradığımız kelimeyi bulurduk.
Şimdi benzer bir yöntemle bilgisayar için bir arama algoritması geliştirelim. Bilgisayar sözcüğün sözlükte tam olarak nerede olduğunu bilemez bu nedenle ortaya yakın bir sayfadan başlayarak aramayı gerçekleştirmeye çalışır.
Orta eleman seçilirken eleman sayısının çift olması durumunda ortanca eleman olarak ikinci yarının ilk elemanı seçilir. Seçilen bu eleman aranan sözcük değilse “ikili arama” ismi verilen yöntem ile listenin ilk veya ikinci yarısında arama yapılır. Aslında ikinci aramada ilk aramadan farklı değildir. Yine aynı yöntemle ikinci yarının orta elamanı bulunur ve kontrol edilir. Bu işlem devam ettikçe aradığımız elemanı bulmak için oluşan alt kümelerin boyutları da azalacaktır. Her seferinde aradığımız elemanı bulmaya bir adım daha yaklaşırız. Bu yöntemin sözde kodları ise şöyledir.
Listedeki orta elemanı test elemanı olarak seç
Aranan değerin test elemanından büyük, küçük yada eşit olması durumuna göre aşağıdaki üç komut grubundan birini yap
İf (aranan değer=test elemanı)
Then (aramayı başarılı olarak belirle)
İf (aranan değer < test elemanı)
Then (arama yordamını kullanarak aranan elemanın listenin test elemanından daha önce yer alıp almadığını bul ve
İf (arama başarılı ise )
Then (aramayı başarılı olarak belirle)
Else (aramayı başarısız olarak belirle))
İf (aranan değer>test elemanı)
Then ((arama yordamını uygulayarak aranan elemanın listenin test elemanından daha sonra yer alıp almadığını bul ve
İf arama başarılı ise
Then (aramayı başarılı olarak belirle)
Else (aramayı başarısız olarak belirle))
Şekil 3.
Yukarıda verilen algoritma orta eleman üzerinden işlem yaptığı için tek elemanlı bir listede çalışmaz çünkü bu durumda ikinci arama boş bir listede gerçekleşir. Bizim dikkat etmemiz gereken nokta programın boş liste içinde doğru çalışmasıdır. Zira çok elemanlı bir listede bölüne bölüne, sonunda boş bir liste halini alacaktır. Bu durumda sözde kodunuzu aşağıdaki gibi düzenlememiz gerekecektir.
if (liste boş)
Then (aramayı başarısız olarak belirle)
Else İf (aranan değer=test elemanı)
Then (aramayı başarılı olarak belirle)
İf (aranan değer < test elemanı)
Then (arama yordamını kullanarak aranan elemanın listenin test elemanından daha önce yer alıp almadığını bul ve
İf (arama başarılı ise )
Then (aramayı başarılı olarak belirle)
Else (aramayı başarısız olarak belirle))
İf (aranan değer>test elemanı)
Then ((arama yordamını uygulayarak aranan elemanın listenin test elemanından daha sonra yer alıp almadığını bul ve
İf arama başarılı ise
Then (aramayı başarılı olarak belirle)
Else (aramayı başarısız olarak belirle))
Şekil 4.
Algoritmada arama yordamını uygula komutuna her gelindiğinde orijinal yordam öncekinden daha küçük bir listeye uygulanmış olur. Herhangi bir aşamada aramada başarılı olursa aramayı başarılı olarak belirlemiş oluruz. İkincil aramalar başarısız olduğu sürece orijinal aramada başarısız olur.