Sıralama Algoritmaları Ve Performansları

Sıralama algoritmaları, bilgisayar bilimlerinde ya da matematikte kullanılan, verilen bir listenin elemanlarını belirli bir sıraya sokan algoritmadır. En çok kullanılan sıralama türleri, sayı büyüklüğüne göre sıralama ve alfabetik sıralamadır. Sıralama işleminin verimli yapılması, arama ve birleştirme algoritmaları gibi çalışması için sıralanmış dizilere gereksinim duyan algoritmaların başarımının yüksek olması için önemlidir. Sıralama algoritmaları bilgisayarlarda tutulan verilerin düzenlenmesini ve insan kullanıcı tarafından daha rahat algılanmasını da sağlar. Ayrıca sıralama algoritmalarının performansları da birbirlerinden farklılık göstermektedir. Bu yazımızda sıralama algoritmaları nelerdir ve bu sıralama algoritmalarının performansları nasıldır bunları inceleyeceğiz.

Sıralama algoritmaları bazı kriterlere göre sınıflandırılabilir:

1. Bellek Kullanımı: Çalışırken ek belek ihtiyacı duyan algoritmalarda kullanılabilecek bir ölçüttür.Ayrıcada sıralama işleminin yapılması sırasında hafızanın kullanımına göre de sıralama algoritmaları;Harici sıralama (External Sort) ve Dahili Sıralama (Internal Sort).

2. Hesaplama Karmaşıklığı: Oluşturulmuş olan algoritmanın yaptığı işlem sayısının genel bir yapı ile ifade edilmesidir. Temel üç grup ölçek kullanılır. Bunlar en iyi(best),ortalama(average) ve en kötü(worst) durumu olarak belirtilir. Örnek verilecek olursa Big O belirteci algoritma karmaşıklığının üst sınırını belirmek adına oluşturulmuştur. İşlem yoğunluğu zaman işleyişiyle paralel olduğundan(ne kadar çok işlem yapılırsa o kadar uzun süre geçer) algoritmanın işleyiş süresini de etkiler.

3. Yerdeğiştirmenin Karmaşıklığı: İçerisinde ek bellek kullanmayan(in place) algoritmalarda kullanılan karşılaştırılabilmesi için önemli bir ölçüttür.

4. Durağanlık (Stability): Algoritmanın uygulanması sırasında sıralanmış bir verinin tekrar sıralamaya tabi tutulup tutulmadığını belirten ölçektir.

5. Rekürsiflik: İç içe kendi kendini çağıran algoritmalarda kullanılan bir ölçüttür.Burada en önemli kriter stack dediğimiz maksimum iç içe çağırım kapasitesine dikkat edilmesi ve bu kapasitenin kullanılma sıklığıdır.

Fakat en önemli kriter Hafıza Verimliliği (Memory efficiency) ve Zaman Verimliliği (Time efficiency)’dir. Kısaca algoritma analizindeki iki önemli kriteri bunlardır. Bir algoritmanın hızlı çalışması demek daha çok hafızaya ihtiyaç duyması demektir. Tersi durumda da bir algoritmanın daha az yere ihtiyaç duyması daha yavaş çalışması demektir. Ancak bir algoritma hem zaman hem de hafıza olarak verimliyse bu durumda diğer algoritmalardan başarılı sayılabilir.

Dizideki en küçük elemanı bul, bu elemanı dizinin son (yer olarak) elemanıyla yer değiştir. Daha sonra ikinci en küçük elemanı bul ve bu elemanı dizinin ikinci elemanıyla yer değiştir. Bu işlemi dizinin tüm elemanları sıralanıncaya kadar sonraki elemanlarla tekrar et. Elemanların seçilerek uygun yerlerine konulması ile gerçekleştirilen bir sıralamadır :

Yerleştirerek sıralama işlevi belirli bir anda dizinin belirli bir kısmını sıralı tutarak ve bu kısmı her adımda biraz daha genişleterek çalışmaktadır. Sıralı kısım işlev son bulunca dizinin tamamına ulaşmaktadır. Elemanların sırasına uygun olarak listeye tek tek eklenmesi ile gerçekleştirilen sıralamadır :

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe sıralanacak olan diziyi ikişer elemanı kalan parçalara inene kadar sürekli olarak ikiye böler. Sonra bu parçaları kendi içlerinde sıralayarak birleştirir. Sonuçta elde edilen dizi sıralı dizinin kendisidir. Bu açıdan bir parçala fethet (divide and conquere) yaklaşımıdır. Sıralı iki veri grubunu birleştirerek üçüncü bir sıralı veri grubu elde etmeye dayanır.

Her düğümün çocuk düğümlerinin kendisinden küçük veya eşit olma kuralını esas alır. Sıralama yapısı; dizinin ilk elamanı her zaman en büyük olacaktır. Dizi üzerinde i. elemanla, çocukları 2i. ve (2i.+1) karşılaştırılıp büyük olan elemanlar yer değiştirilecektir. Dizinin son elamanları dizinin ortasındaki elamanların çocuk düğümü olacağından bu işlem dizinin yarısına kadar yapılır. Elde edilen diziyi sıralamak için ise dizinin ilk elamanı en büyük olduğu bilindiğinden dizinin son elamanıyla ilk elemanı yer değiştirilerek büyük elaman sona atılır. Bozulan diziye yukarıdaki işlemler tekrar uygulanır. Dizi boyutu 1 oluncaya kadar işleme devam edilir. Bu algoritmanın çalışma zamanı, O(nlogn)’dir. En kötü durumda en iyi performansı garanti eder. Fakat karşılaştırma döngülerinden dolayı yavaş çalışacaktır

Algoritma performansı O(n2)’dir. Sıralama işlemi için öncelikle bir atlama miktarı belirlenir. Atlama miktarının belirlenmesi için çok çeşitli yollar bulunmasına karşılık en basit yöntem elimizdeki sayıların yarısından başlamaktır. Yani aşağıdaki örnekte elimizde 7 sayı olduğuna göre 3 atlama miktarı ile başlanabilir. Sırasıyla her sayı kendinden 3 sonraki sayı ile karşılaştırılır ve bu sayılar kendi aralarında sıralanır. Bu sıralamayı daha rahat göstermek için aşağıdaki kolon gösterimi kullanılabilir:

Şu ana kadar bilinen en gözde ev hızlı algoritmadır. Uygulama adımları şu şekilde sıralanabilir:

• Diziden herhangi bir eleman al(pivot elaman)
• Pivot elemanından küçük olanları bir diziye, büyükleri bir diziye topla.
• Bu alt dizilerden yukarıdaki gibi pivot elemanları seçip aynı işlemi uygula. İç içe en küçük parçalara ulaşana kadar bu yöntemi sürdür.
• Oluşan dizicikleri birleştir

Hane sıralaması, radiks sıralaması veya kök sıralaması isimleri de verilebilen sıralama algoritmasına göre sıralanacak olan değerler hanelerine (digits) göre sıralanır. En değersiz haneden (Least significant digit) en değerli haneye (most significant digit) doğru sıralama işlemi yapılır. Yani örneğin en fazla 4 haneli sayıların bulunduğu bir sayı kümesinde en değersiz hane 1’ler hanesi en değerli hane ise binler (1000) hanesidir.

Kova Sıralaması (ya da sepet sıralaması), sıralanacak bir diziyi parçalara ayırarak sınırlı sayıdaki kovalara (ya da sepetlere) atan bir sıralama algoritmasıdır. Ayrışma işleminin ardından her kova kendi içinde ya farklı bir algoritma kullanılarak ya da kova sıralamasını özyinelemeli olarak çağırarak sıralanır. Kova sıralaması aşağıdaki biçimde çalışır:

1. Başlangıçta boş olan bir “kovalar” dizisi oluştur.
2. Asıl dizinin üzerinden geçerek her öğeyi ilgili aralığa denk gelen kovaya at.
3. Boş olmayan bütün kovaları sırala.
4. Boş olmayan kovalardaki bütün öğeleri yeniden diziye al.

Kova sıralaması doğrusal zamanda çalışır. Girişin düzgün dağılımlı olduğu kabul edilir. Random olarak [0,1) aralığında oluşturulmuş giriş bilgileri olduğu kabul edilir. Temel olarak [0, 1) aralığını n eşit alt aralığa böler ve girişi bu aralıklara dağıtır. Aralıklardaki değerleri insert sort ile sıralar. Aralıkları bir biri
ardına ekleyerek sıralanmış diziyi elde eder.

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe sıralanacak olan dizideki her sayının kaç tane olduğunu farklı bir dizide sayar. Daha sonra bu sayıların bulunduğu dizinin üzerinde bir işlemle sıralanmış olan diziyi elde eder.

Veri sıralama için kullanılan ve kabarcık sıralamasının (bubble sort) neredeyse aynısı olan sıralama algoritmasıdır (sort algorithm). Kabarcık sıralamasından tek farkı, kabarcık sıralaması tek yönlü olarak kabarcığı hareket ettirirken, sallayıcı sıralaması bir sağdan bir soldan iki yönden de sıralamaktadır. Bu sebeple çift yönlü kabarcık sıralaması (bidirectional bubble sort) ismi de verilmektedir.

Bu algoritma basitçe bir dizinin sıralı olana kadar rastgele dizilmesi olarak ifade edilebilir. Bu algoritmanın gerçek hayatta kullanılabilirliği işlem süresinin uzunluğundan dolayı yoktur. Ancak eğitim amaçlı olarak literatürde geçmektedir. Algoritmanın en iyi ihtimali O(n) olarak düşünülebilir çünkü şayet verilen dizi sıralıysa sadece dizinin sıralı olduğunu kontrol etmek için n tane elemanın üzerinden bir kere geçilmesi yeterlidir. Buna karşılık en kötü ihtimalle sonsuza kadar
çalışabilecek bir algoritmadır.

Sadece teorik olarak literatürde geçen bir sıralama algoritmasıdır (sorting algorithm). Buna göre sıralanacak olan dizi şanslı bir şekilde zaten sıralı verilmiştir. Dolayısıyla dizinin sıralanmasına gerek yoktur. Hatta bu kabulü yaptığımız için dizinin sıralı olup olmadığını kontrol etmemize de gerek yoktur(ne de olsa şanslıyız) dolayısıyla giriş dizisi her zaman sıralı olan sıralama algoritmasıdır. Anlaşılacağı üzere hiçbir işe yaramaz. Sadece teorik olarak O(0) zamanda sıralama yaptığının bilinmesi ve bu durumun hem en iyi hem de en kötü zaman olduğunun anlaşılması yeterlidir.

Bilgisayar bilimlerinde kullanılan ve tek boyutlu bir veri yapısı üzerinde (örneğin dizi (array) ) sıralama yapmaya yarayan bir algoritmadır. Algoritmanın çalışması birleştirme sıralaması (merge sort) veya hızlı sıralama (quick sort) algoritmalarına benzetilebilir. Bunun sebebi algoritmanın, sıralamak istenen sayıları 2/3 oranında iki parçaya bölmesi ve kalan sayıları kendi aralarında sıralamasıdır.
Algoritmanın açıklaması ve kodlanması
Bu anlamda algoritmanın çalışması aşağıdaki adımlarla izah edilebilir:

• Dizinin sonundaki sayı, başındaki sayıdan küçükse bu sayıların yerini değiştir (swap)
• Şayet işlem yapılan elaman sayısı 3 veya daha fazlaysa
  • Elemanların ilk 2/3’ünü serseri sıralamasına ver
  • Elamanların kalan 1/3’ünü serseri sıralamasına ver
  • Elamanların ilk 2/3’ünü tekrar serseri sıralamasına ver

Bora sıralamasında amaç, bir veri kümesinin bilinen bir dağılıma uygun olması durumunda bu özelliğini sıralama algoritmasında kullanmaktır. Yani şayet elimizde olan ve sıralamak istediğimiz sayılar gauss dağılımına (guassian distribution) uygunsa bu sıralama algoritması tarafından bir avantaj olarak kullanılabilir.  Parçalı sıralama algoritmaları (partial sort algorithm) dağılımdan gelen bu özelliği kullanarak sıralamadan önce bir aşamada sayıları mümkün olduğunca sonuçta olacakları yere yaklaştırmayı hedefler. Ardından herhangi bir sıralama algoritması ile işlem tamamlanır.

Bilgisayar bilimlerinde kullanılan araya sokmalı sıralamaya benzer bir sıralama algoritmasıdır. Ara sokmalı sıralamadan farkı kabarcık sıralaması yönteminde olduğu gibi, bir elemanın sıralanan dizideki yerine birçok yer değiştirme yoluyla gelmesidir. Cüce sıralama algoritmasının çalışma mantığı; İlk elemanı seçer sonrakiyle karşılaştırır (küçük veya büyüğe) sıralamaya göre yer değiştirir. Sonra ondan önceki eleman varsa bir öncekiyle karşılaştırır. Yer değiştirmezse tekrar kaldığı elemandan aynı şekilde devam eder.

Verilen sayı dizisinin rastgele karıştırılması ile olası bütün ihtimalleri değerlendiren bir sıralama algoritmasıdır. Algoritma aslında oldukça basit bir yapıya sahiptir. Basitçe bir sayı dizisinin bütün permütasyonları sırasıyla denenir ve bunlardan birisinin sıralı olarak bulunması halinde algoritma sona erer.

Strand algoritması sıralı alt listeleri, sıralanacak şekilde listeden çıkarılarak ve sonuç dizisiyle birleştirerek tekrar tekrar çalışır. Sıralanmamış listeden her yineleme, zaten sıralanmış olan bir dizi eleman çeker ve bu serileri birleştirir. Strand sıralama algoritması, ortalama durumda O (“n” log “n”) ‘dir. En iyi durumda (önceden sıralanmış bir liste) algoritma doğrusaldır veya O (“n”). En kötü durumda (ters sırada sıralanan bir liste) algoritma O (“n” 2) ‘dir.
Strand sıralama, verilerin sık sık eklenmesi ve kaldırılması nedeniyle bağlantılı bir listede saklanan veriler için en yararlıdır. Bir dizi gibi başka bir veri yapısını kullanmak, uzun ekleme ve delesyonlardan dolayı algoritmanın çalışma süresini ve karmaşıklığını büyük ölçüde artıracaktır. Sıralı sıralama, büyük miktarlarda sıralanmış verilere sahip veriler için de yararlıdır, çünkü bu veriler tek bir dizide kaldırılabilir.

İŞLEM ADIMLARI

• Sıralanmamış Listeyi bir kez artırın, artan (sıralı) sayıları alın.
• The (sıralanmış) Alt liste, ilk iterasyon için boş sıralanmış listeye itilir.
• Yeniden Sıralanmamış Listeyi tekrar, göreceli olarak sıralanan numaraları alarak tekrar.
• Sevimli Listenin doldurulduğu zaman, Alt Listeyi Sorted List’e birleştirin.
• Sıralanmamış Liste ve Alt Listenin ikisi de boşalana kadar 3-4 arasındaki adımları tekrarlayın.

Youtube kanalımızdan bizleri takip edebilirsiniz.

TEKNOKODİ