BİL204U-ALGORİTMALAR
Ünite 6: Sıralama ve Arama Algoritmaları
Giriş
Bir veri kümesinde yer alan verilerin sıralanması bilgisayar bilimindeki en önemli konuların başında gelmektedir. Bilgisayar biliminde, ‘sıralama’ kavramı genellikle bir dizi ögeyi iyi tanımlanmış bir sıraya sokmayı ifade etmektedir. Bir sıralama işlemini gerçekleştirebilmek için öncelikle veri seti üzerinde “sıra” kavramını belirlememiz gerekmektedir. Örneğin; sayılar için sayısal sırayı kullanabiliriz ve metinsel veriler için ise sözlükte kullanılan sözlükbilimsel veya alfabetik sırayı kullanabiliriz. Sıralama işlemi veri kümesi nasıl olursa olsun tüm veri kümeleri için ortak ve genel bir işlemdir. Bir başka deyişle, günümüze kadar geliştirilmiş sıralama algoritmalarının büyük bir kısmı tüm veri setleri üzerinde çalışabilir. Sıralı bir veri kümesinde aranan bir ögenin bulunması, sıralanmamış bir veri kümesindekine nazaran çok daha hızlı ve daha kolay gerçekleştirilmektedir. Bu nedenle sıralama işlemi bilgisayar bilimi açısından çok değerlidir.
Bu bölümde, ilk olarak sıralama stratejilerinden bahsettikten sonra farklı sıralama algoritmaları incelenecektir. Burada bahsedilen algoritmalardan bazılarının geliştirilmesi nispeten kolay olmasına karşın düşük performans gösterebilir. Yazması biraz karmaşık olan diğer algoritmalar ise çok daha iyi performans göstermektedir. Farklı durumlar için farklı sıralama algoritmaları kullanılabilir, yani her durum veya her veri seti için tek bir ‘en iyi’ bir sıralama algoritmasından bahsetmek mümkün olmayabilir. Bu nedenle bölüm içerisinde birçok sıralama algoritma algoritmasından bahsedilecektir.
Sıralama Algoritmaları
Günümüzde sıralama problem için geliştirilmiş birçok algoritma bulunmaktadır. Bu algoritmaları kullandıkları stratejilere göre sınıflamak mümkündür:
Değiştirerek Sıralama: Bu sıralama stratejisinde, karşılaştırılan iki veri öncelikle sıraya konulur. Ardından bu işlem tüm veriler sıralanana kadar devam ettirilir.
Seçerek Sıralama: Veriler içerisinde en küçük olanı bulunur ve sıraya yerleştirilir. Ardından kalan veriler arasında en küçük veri bulunur ve tekrar sıraya konulur. Bu işlem veri seti sıralanana kadar devam ettirilir.
Eklemeli Sıralama: Verileri birer birer alarak boş bir veri yapısı içerisine uygun sırada eklenir.
Böl ve Yönet Sıralama: Verinin sıralanması amacı ile bir veya iki veri kalana kadar problem daha küçük parçalara bölünür. Ardından en alt seviyede sıralanan parçalar yukarı seviyelere doğru birleştirilerek tüm verinin sıralanması sağlanır.
Numaralandırmalı Sıralama: Her bir veri diğer tüm verilerle karşılaştırarak ve daha küçük değere sahip veri sayısını bulunur. Ardından veri bu pozisyona yerleştirilir.
Tüm bu stratejiler, ögeleri karşılaştırmaya ve ardından bunları buna göre yeniden düzenlemeye dayanır. Bunlar
karşılaştırmaya dayalı sıralama algoritmaları olarak bilinir. Bunlar dışında karşılaştırma işlemi kullanılmayan sıralama algoritmaları da bulunmaktadır.
Kabarcık Sıralama
Kabarcık sıralama algoritması, değiştirerek sıralama stratejine dayanmaktadır. Temelindeki fikir oldukça basittir. Sırasız rastgele bir liste verildiğinde, her seferinde iki elemanı karşılaştırıp doğru büyüklük sırasına koyarak sıralama gerçekleştirilir. İki ögenin doğru büyüklük sıralamasına koyulması için takas prosedürü kullanılır. Takas prosedürü birçok algoritmada kullanılmaktadır. Bu nedenle algoritmanın detaylarına geçmeden önce kısaca takas prosedüründen bahsedilecektir.
Takas prosedürü, iki bardakta bulunan sıvıların yer değiştirilmesine benzetilebilir. Bu işleme için bir boş bardağa ihtiyaç bulunmaktadır. Benzer şekilde iki verinin yer değiştirilmesi işleminde geçici bir alana ihtiyaç vardır.
Eklemeli (Yerleştirmeli) Sıralama
Tıpkı kabarcık sıralamada olduğu gibi eklemeli sıralama da değiştirerek sıralama stratejisini kullanmaktadır. Eklemeli sıralama algoritmasında, listenin belirli bir bölümünün zaten sıralanmış olduğunu, diğer bölümün ise sıralanmamış kaldığını varsayılmaktadır. Bu varsayımla her seferinde sıralanmamış bölümden bir eleman seçilerek sıralanmış bölümdeki uygun sıraya eklenmektedir. Aşağıdaki şekilde algoritmanın çalışma mantığı anlatılmıştır.
Algoritmanın ilk aşamasında listedeki ilk eleman seçilir ve listenin “sıralanmış elemanlar” bölümünün ilk elemanı olarak kabul edilir. İkinci aşamada “sıralanmamış elemanlar” kısmındaki elemanlardan ilki seçilir ve sıralanmış kısımda uygun yere yerleştirilir. Ardından yeni bir eleman seçilir ve sıralı kısmındaki uygun yerine yerleştirilir. En son aşamaya gelindiğinde ise tüm liste sıralanmış olacaktır. Bu algoritmada da temel işlemler karşılaştırma ve takas işlemleridir.
Seçmeli Sıralama
Bir diğer önemli sıralama algoritması da seçmeli sıralamadır. Bu sıralama algoritmasının anlaşılması oldukça kolay olmasına rağmen tıpkı kabarcık sıralama ve eklemeli sıralama gibi en kötü ve en iyi asimptotik değerleri O(n^2) olduğu için verimsizdir. Bu algoritma, listedeki en küçük elemanı bulur ve bunu listenin en başındaki veri ile değiştirir. Aynı işlem dizinin tüm elemanları için tekrar edilir.
Kabuk Sıralama
Bir diğer sıralama algoritması da kabuk (shell) sıralamadır. İsmini algoritmayı geliştiren Donald Shell’den almaktadır. Bu algoritma temel olarak başka sıralama algoritmalarının verimliliğini artıran bir algoritmadır ve içerisinde başka sıralama algoritmaları çalıştırır.
Ağaç Sıralama
Ağaç sıralama yönteminde veri yapısı olarak ağaç kullanılmaktadır. İlerleyen bölümlerde bahsedileceği gibi
ağaç yapısı düğümlerden oluşmaktadır. İkili arama ağaçlarında ise her bir düğümün en fazla iki çocuk düğümü bulunmaktadır. Ağaç sıralamadaki ana fikir, sıralanacak ögeleri tek tek dengeli bir şekilde bu ağaç yapısı içerisine yerleştirmektir. Tüm elemanlar yerleştiğinde ise tüm ögeler doğru bir sıra ile ağaçtan çekilebilmektedir.
Bu noktada karşılaştırma işleminin sayısını minimumda tutabilmek için ağacın dengeli olması gerekmektedir. Dengeli bir ağaçta karşılaştırma sayısı için karmaşıklık değeri O(log2(n)) olmaktadır. Buradaki en kötü durumda ise O(n)dir. Bu değer esasen ağaca yeni bir veri ekleme karmaşıklığını da vermektedir. Ağaca eklenecek n eleman olduğundan ve her eklemenin zaman karmaşıklığı O(log2(n)) olduğundan, ağaç sıralamanın genel ortalama zaman karmaşıklığı O(n log2(n)) olur. Ancak, elemanlar eklenirken ağaç dengeli tutulmazsa veya ögeler zaten sıralanırsa, ağacın yüksekliği ve ekleme başına karşılaştırma sayısı O(n) olmaktadır. Bu da en kötü durum süresine yol açar. O(n2)’nin karmaşıklığı, daha önce ele aldığımız dizi tabanlı algoritmalardan daha iyi değildir.
Ağaç sıralama, sıralanmış veri yapısı olarak bir dizi yerine bir ağaç döndürdüğü için diğer sıralama algoritmalarıyla karşılaştırmak zor olabilir. Verilerin yine de bir ikili arama ağacında saklanması isteniyorsa bu yöntem seçilmelidir. Bu yöntem genellikle verilerin sık sık eklenmesi veya silinmesi veya aranması durumlarında daha verimli olmaktadır.
Yığın (Heap) Sıralama
Yığın sıralama, veri seti kullanılarak oluşturulan bir yığın ağacının (heap) en üstündeki sayısını alarak sıralama işlemi yapmaktadır. Yığın ağacı, sıralama amacıyla kullanılan bir veri yapısıdır. Bu yapıda üst düğümün daima çocuklarından büyük olduğu ikili bir ağaç yapısıdır.
Yığın ağaç yapısından bahsettikten sonra yığın sıralama yönteminin nasıl çalıştığını inceleyelim. Bahsedildiği üzere yığın ağaçlarında en büyük veri daima kök düğümde yani ilk indiste tutulmaktadır. Buradan hareket ile algoritma temel olarak 4 basamaktan oluşmaktadır:
1. Takas işlemi: Kök elemanı alarak bir diziye yerleştirin yığının son elemanını kök elmanın yerine yerleştirin. 2. Kaldırma işlemi: Yığın boyutunu 1 azaltın. 3. Yeniden yığınlama işlemi (Heapify): Kökteki en yüksek ögeye sahip olmamız için kök ögeyi tekrar yığınlayın. 4. Bu işlemi, listenin tüm ögeleri sıralanana kadar tekrarlayın.
Böl ve Yönet Algoritmaları
Şu ana kadar bahsedilen tüm sıralama algoritmaları veriyi bir bütün olarak alıp sıralama problemine çözüm getirmektedirler. Sıralama algoritmaları arasında farklı yaklaşım gösteren algoritmalar da bulunmaktadır. Bu algoritmalar, sıralama problemini öz yinelemeli olarak daha yönetebilir alt problemlere bölmektedirler. Bu tip
algoritmalar böl ve yönet algoritmaları adı altında sınıflandırılmaktadır. Bu yaklaşımdaki ana fikir, az sayıda elemandan oluşan veri setinin, çok fazla sayıda elemandan oluşan veri setine göre daha kolay sıralanacağıdır. Bu nedenle bu yaklaşımda öncelikler veri seti sıralaması çaba gerektirmeyecek kadar küçük parçalara ayrıldıktan sonra sıralanır, ardından sıralı küçük listeler birleştirilerek ana veri setinin sıralanması tamamlanır. Bunu yapmak için iki ana yaklaşım vardır:
İlk yaklaşımda, n elemanlı veri listesi, 2 eleman kalana kadar ikiye bölünerek yaklaşık n/2 adet alt veri seti elde edilmektedir. Ardından bu iki elemanlı alt veri kümeleri hızlıca sıralanır. Bir sonraki aşamada ise veri setleri sıra göz önünde bulundurularak birleştirilir. Bu yaklaşım birleştirmeli sıralama (merge sort) ismi ile anılmaktadır.
Diğer bir yaklaşım ise veri setinin her aşamada, ilk alt veri setindeki tüm elemanlar ikinci alt veri setindeki tüm elemanlardan daha büyük olmayacak şekilde listeyi ikiye bölme işlemini temel almaktadır. Buradaki bölme işlemi açıkça bir önceki yaklaşıma göre daha karmaşıktır ancak her aşamada parçaları tekrar bir araya getirmek için tek yapmamız gereken ilk sıralanan diziyi ve ardından ikinci sıralanan diziyi almaktır. Bu yaklaşım hızlı sıralama (quick sort) olarak isimlendirilir.
İlk yaklaşımda, bölme işlemi çaba gerektirmez iken ikinci yaklaşımda ise birleştirme işlemi çaba gerektirmemektedir. Bu başlık altında bu iki algoritmanın detayları sunulacaktır.
Hızlı Sıralama
Tony Hoare tarafından 1959’da geliştirilen hızlı sıralama algoritması sıralama problemi için yaygın olarak kullanılan bir algoritmadır. Hızlı sıralama bir karşılaştırmalı sıralamadır, yani bir “küçüktür” ilişkisinin tanımlandığı herhangi bir türdeki ögeleri sıralayabilmektedir. Bu algoritmadaki genel fikir daha önce de bahsedildiği üzere, verilen listeyi, birinci alt dizideki tüm elemanlar ikinci alt dizideki tüm elemanlardan daha küçük olacak şekilde tekrar tekrar bölmek ve ardından tüm alt dizileri birleştirmektir. Diziyi ikiye bölerken uygun bir orta nokta belirlenmesi algoritmanın en önemli noktalarından biridir. Bu seçilen orta noktaya “pivot” adı da verilmektedir
Birleştirmeli Sıralama
Birleştirmeli sıralama (merge sort) algoritması böl ve yönet yaklaşımını kullanan diğer bir algoritmadır. Bu algoritmada özyineleme süreçlerini kullanmaktadır. Hızlı sıralamada olduğu gibi veri listesi ikişer elemanlı alt listelere ulaşıncaya kadar bölünür. Bölme işleminde hızlı sıralamada uygulandığı gibi herhangi bir işlem uygulanmaz. Bu süreçte sadece diziyi ikiye bölme işlemi gerçekleştirilir. Bölme işlemi sonucunda sıralanmış alt dizilere ulaşılmamaktadır. Bu nedenle, birleştirmeli sıralamada, iki sıralı alt diziyi başka bir sıralanmış dizide birleştiren başka bir prosedüre ihtiyaç bulunmaktadır. Birleştirmeli sıralamada algoritmanın yükü bölünme süreçlerinde değil birleştirme süreçlerindedir.
Birleştirmeli sıralama algoritması aşağıdaki adımlardan oluşmaktadır.
1. Bölünme: Bu aşamada liste sürekli 2 alt listeye bölünmekte ve herhangi bir ekstra işlem uygulanmamaktadır. Bu bölünme işlemi alt liste bir veya en fazla 2 elemana düşünceye kadar devam etmektedir. 2. Sıralama: Bu aşamada 2 elemanlı alt liste basit bir karşılaştırma ile sıralanır. 3. Birleştirme: Algoritmanın esasen sıralamayı gerçekleştirdiği bölüm burasıdır. Bu aşamada sıralı iki listenin birleştirilme işlemi yapılmaktadır. Bu birleştirme işlemi için gerekli adımlar şu şekilde listelenebilir: i. Başlangıçta iki listede de ilk elemanı gösteren bir indis işaretçisi belirlenir. ii. İşaretçiye karşılık gelen değerler karşılaştırılır küçük olan ilk eleman olarak listeye eklenir ve o listenin işaretçisi 1 artırılır. Bu işlem listelerden birindeki elemanlar bitene kadar devam ettirilir. iii. Son olarak eleman barındıran veri setindeki tüm elemanlar yeni listeye eklenir.
Radix Sıralama
Radix Sıralama, değerleri küçük veya sınırlı veri setleri üzerinde iyi çalışan, temelde “karşılaştırmaya dayalı olmayan” sıralama algoritmasıdır. Örnek olarak aynı yıl içinde bulunan aylardan oluşan verileri sıralamamız istendiğinde kullanılabilecek bir sırala algoritmasıdır. Bunun için, 12 elemanlı bir liste oluşturmamız ve günleri herhangi bir sıralama işlemine tabi tutmadan doğru alana yerleştirmek yeterli olacaktır. Ardından dolu alanları birleştirerek sonuca ulaşılabilir.
Diğer Sıralama Algoritmaları
Bu bölüm içerisinde bahsedilen sıralama algoritmaları dışında, geliştirilmiş birçok algoritma bulunmaktadır. Bunlar;
• Blok birleştirmeli sıralama (block merge sort), • Değişimli sıralama (Exchange sort), • Döngü sıralama (Cycle sort), • Düzgün sıralama (smoothsort ), • Girişe yönelik sıralama (introspective sort), • Gnome sıralama (Gnome sort), • İplik sıralama (Strand sort), • Kitaplık sıralama veya boşluklu ekleme sıralaması (Library sort veya gapped insertion sort), • Kokteyl sıralama (Cocktail shaker sort), • Küp sıralama (Cube sort), • Sabırlı sıralama (Patience sorting), • Tarak sıralama (Comb sort), • Tek çift sıralama (Odd–even sort), • Tim sıralama (tim sort), • Turnuva sıralaması (Tournament sort)
şeklinde sıralanabilir.
Sıralama Algoritmalarının Karşılaştırılması
Bu bölümde, sıralama problemi için geliştirilmiş birbirinden farklı algoritmalar gösterilmiştir. Karşılaştırma içeren algoritmaların zaman karmaşıklığı genel olarak O(n2) ve O(n l log2(n))dir. Fakat özellikle zaman karmaşıklığı O(n2) olan algoritmalar pratikte birbirinden farklı performanslar göstermektedirler. Bunun için aynı veri seti ve aynı donanım üzerinde algoritmaların çalıştırılarak karşılaştırılması doğru yaklaşım olacaktır. Burada en kötü performans genelde kabarcık sıralama tarafından sergilenmektedir.
Arama Algoritmaları
Bir veri kümesi içerisinde istenilen değerin bulunma işlemi tıpkı sıralama problemi gibi bilgisayar bilimlerinde önemli problemlerin başında gelmektedir. Bir liste içerisinde arama yaparken, dizinin sıra olup olmama durumuna bağlı olarak iki ana teknik bulunmaktadır. Bu başlık altında, doğrusal ve ikili arama algoritmaları hakkında bilgi verilecektir. Temel olarak doğrusal arama algoritması, hem sıralanmış hem de sıralanmamış veriler üzerinde uygulanabilmektedir. İkili arama algoritması ise özellikle sıralanmış verilerle kullanılmaktadır. Fakat doğrusal arama algoritmasının zaman karmaşıklığı, ikili arama algoritmasına kıyasla daha yüksektir.
Doğrusal Arama
Doğrusal arama (linear search) algoritması bir veri setinde aranan değerin setteki tüm elemanların tek tek kontrol ederek aranması mantığına dayanmaktadır. Arama işlemi bir sayı üzerinde olabileceği gibi metinsel verilerde üzerinde de gerçekleştirilebilmektedir. Bu algoritmada verilerin sıralı olması gerekmemektedir. Algoritma n elemanlı bir liste üzerinde temel olarak şu basamaklardan oluşmaktadır.
1. Göstericiyi 0 olarak ayarla (Listelerin ilk elemanının indisi 0 olarak kabul edilmiştir.) 2. Aranan değer ile gösterici indisinin değerini karşılaştır 2.1. Eğer aranan değer bulunduysa sonucu ilan et 2.2. Eğer aranan değer bulunmadıysa 2.2.1. Göstericinin değerini kontrol et. Eğer değer liste eleman sayısına eşitse 2.2.1.1. Aranan değerin bulunamadığını ilan et 2.2.2. Göstericinin değerini bir arttır ve 2 numaralı adıma dön
İkili Arama
İkili arama (binary search) algoritması, doğrusal arama algoritmasından farklı olarak sadece sıralı listeler üzerinde çalışmaktadır. Sıralı listeler üzerinde çalışması bu algoritmanın zaman karmaşıklığı açısından verimini çok fazla arttırmaktadır. Algoritmada tüm veriler tek tek kontrol edilmemektedir. Bunun yerine sıralı listenin tam ortasındaki eleman ile aranan eleman karşılaştırılmaktadır.
İkili Arama Ağaçları
İkili arama ağaçları, veri seti içerisinde aranan elemanın hızlı bir şekilde bulunmasını sağlayan bir veri yapısıdır. Bu veri yapısı üzerinde çalışan algoritma verimlilik açısından ikili aramaya göre daha etkindir. Çünkü ikili aramada aramaya başlamadan önce dizinin sıralanması veya dizinin sürekli sıralı tutulması gerekmektedir. Bu da arama algoritmasının maliyetini artırmaktadır. İkili arama ağaçlarındaki temel fikir, İkili ağaçları kullanarak, sıralanmış bir diziyi sürdürmeye gerek kalmadan depolama ve arama sürecini hızlandırabilmektir. İkili arama ağacı, boş olan veya aşağıdaki koşulları karşılayan bir ikili ağaçtır.
• Sol alt ağaçta meydana gelen tüm değerler kökün değerinden daha küçüktür. • Sağ alt ağaçta meydana gelen tüm değerler kökü değerinden daha büyüktür. • Sol ve sağ alt ağaçların kendileri ikili arama ağaçlarıdır.