Sıralama ve Arama Algoritmaları

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.

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.

Harici sıralama algoritmaları genel olarak, veri kümesini, aynı anda ele alınabilecek kadar çok veri içeren alt kümelere böler, sırayla her alt kümeyi sıralar ve ardından sonuçları dikkatlice birleştirerek çalışırlar.

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. Bu işlem 3 adımda gerçekleştirilmektedir.
1. X değişkeninin içeriği temp değişkenine aktarılır.
2. Y değişkeninin içeriği x değişkenine aktarılır.
3. Son olarak temp değişkeninin içeriği y değişkenine aktarılır
Sonuç olarak x ve y değişkeninin içeriği değiştirilmiş olur.

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.

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(n2) 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.

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 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.

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 tekrayın.

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.

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.

Birleştirmeli sıralamanın her bir özyineleme düzeyinde ihtiyaç duyulan toplam karşılaştırma sayısı, O(n)dir. Bir başka deyişle bu, iki sıralı listeyi birleştirme algoritmasının zaman karmaşıklığıdır. Bu işlem her bir bölme adımında gerçekleştirilecektir. Dolayısıyla algoritmadaki toplam karşılaştırma sayısı yani algoritmanın zaman karmaşıklığı O(n log2(n))’dir. Bu karmaşıklık ortalama durum kadar en kötü durum için de geçerlidir. Birleştirmeli sıralamanın dezavantajı alan karmaşıklığının O(n) olmasıdır.

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. Radix sıralama belli sayıda basamak içeren sayılar üzerinde de uygulanabilir.

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.

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 (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 (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ı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.