Sıralama Algoritmaları (Sorting Algorithms)

Bilgisayar bilimlerinde verilmiş olan bir grup sayının küçükten büyüğe(veya tersi) sıralanması işlemini yapan algoritmalara verilen isimdir. Bu sırlama işlemlerini yapmanın çok farklı yolları vardır ancak bilgisayar mühendisliğinin temel olarak üzerine oturduğu iki performans kriteri buradaki sonuçları değerlendimede önemli rol oynar.

Hafıza Verimliliği(memory efficiency)
Zaman Verimliliği(Time efficiency)

Temel olarak algoritma analizindeki iki önemli kriter 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. Genellikle verinin hafızada saklanması sırasında veriyi tutan bir belirleyici özelliğin olması istenir. Veritabanı teorisinde birincil anahtar (primary key) ismi de verilen bu özellik kullanılarak hafızada
bulunan veriye erişilebilir.Bu erişme sırasında şayet belirleyici alan sıralı ise erişimin logaritmik olmaktadır.

Bilgisayar biliminde, 3 farklı gösterim mevcuttur bunlar Big-O/ Theta/Omega gösterimleridir. En iyi senaryo için Omega kabul edilirken, algoritmik en kötü senaryoları ölçmek için ‘’Big-O’’ gösterimi, kullanılır.

Big-O gösterimin kendisine has bir orjinalliği vardır. Tasarım olarak tam belirli değildir. Bu da bir algoritmanın performansını dakika ve saniyerler cinsinden belirtmek yerine Big-O gösteriminin problemin boyutu ile programın çalışma süresi arasındaki ilişkinin türü hakkında konuşmak için bir yol sunması demektir. Big-O gösterimi ortaya bilinçli bir şekilde ince detaylar döktüğünden sonuçta ortaya çıkan şey, problemleri farklı sınıflara bölmek için bir şemadır.

(n) sayıda misafirin katılacağı bir akşam yemeği verdiğinizi düşünün. Onların gelişinden önce evinizi temizlemek için gerekli olan süre kesinlikle gelecek olan misafirlerinizin sayısana bağlı değildir. Bu durumda problem türleri içinde olabilecek en kolay ve sevimli olanıdır. Buna ‘’ Big-O bir’’ denir ve O(1) şeklinde gösterilir. Buna aynı zamanda ‘sabit zaman’ denir. Sizin de dikkat edeceğiniz gibi Big-O gösterimi temizliğin gerçekte ne kadar süreceğiyle hiç ilgilenmez, o süre her zaman aynıdır ve misafir listesi her ne uzunlukta olursa olsun değişmez. Bir, on, yüz ya da başka bir n sayısında misafirimiz olsa da yaapılacak iş miktarınız aynıdır.

def constant_big_O(liste):
  print(liste[0])

constant_big_O([1,2,3,4,5,6,7,8,9])

Pişirdiğiniz rostoyu masada herkesin alabileceği şekilde dolaştırmak ‘’Big-O (n)’’ olacak ve O(n) şeklinde yazılacaktır. Bu aynı zamanda ‘’lineer(doğrusal) zaman’’ olarak bilinmektedir.Misafir sayınız iki katına çıktığında yemeğin masanın tamamına dolaşması için iki kat fazla beklemek zorunda kalırsınız. Burada da Big-O gösterimi, servis edilen yemek çeşidi ya da bu yemeklerin ikinci defa servis edilmesi gibi durumlarda hiç ilgilenmez. Her durumda zaman, misafir listesinin boyutuna doğrusal bir şekilde bağlıdır.

def linear_big_O(liste)
  for deger in liste:
    print(deger)

liear_big_O([1,2,3])

Misafir sayısı ve bunlara servis için gerekli zamanı gösteren bir grafik çizseniz bu dümdüz bir çizgi olur. Dahası, Big-O gösteriminde herhangi bir doğrusal zaman faktarönün varlığı, diğer tüm sabit zaman faktörlerini yutacaktır. Yani, masada rostoyu bir kez gezdirmek ile yemek odanızı üç ayda yeniden düzenlemek ve sonra rostoyu bir kez masada gezdirmek arasında bir bilgisayar mühendisi için fark yoktur. Eğer bu size çılgınca geldiyse o zaman bilgisayarların rahatlıkla binler, milyonlar ya da milyarlar olabilecek (n) değerleriyle ilgilendiğini hatırlayın.

Peki, misafirler geldikçe her bir misafir yeni geleni kucaklarsa durum ne olur? İlk misafiriniz sizi kucaklıyor, ikincisinin kucaklayacağı iki kişi var, üçüncü misafirinizin ise üç. Toplamda kaç kucaklaşma olacaktır? Bu probleme ‘’Big-O n kare’’ denir, O(n²) şeklinde gösterilir ve ‘kuadratik zaman’ olarak bilinir. Burada da sadece n ve zaman arasındaki temel hatlarla ilgileniriz. Kişi başına iki kucaklama anlamına gelen O(2n²) ya da kucaklaşma ve yemeği masada dolaştırma olan O(n²+n) veya sarılma ve ev temizliği anlamına gelen O(n²+1) diye bir şey yoktur.Sadece ‘kuadratik zaman’ vardır ve bu nedenle O(n²) hepsini kapsar. Buradan itibaren her şey kötüleşir. İlave her misafirin sizin işinizi iki katına çıkardığı ‘üstel zaman’, O(2^n), vardır. Daha da
kötüsü mühendislerin sadece şakalaşırken hakkında konuştukları gerçekten cehennem gibi problemler olan ‘faktoriyel zaman’, O(n!)problemleri de vardır.

Seçerek Sıralama (Selection Sort)
Hızlı Sıralama Algoritması ( Quick Sort Algorithm)
Birleştirme Sıralaması ( Merge Sort)
Yığınlama Sıralaması ( Heap Sort)
Sayarak Sıralama (Counting Sort)
Kabarcık(Baloncuk) Sıralama (Bubble Sort)
Taban Sıralaması (Radix Sort)
Sokma Sıralaması (Insertion Sort)
Sallama Sıralaması (Shaker Sort)
Kabuk Sıralama (Shell Sort)
Rastgele Sıralama (Bogo Sort)
Şanslı Sıralama (Lucky Sort)
Serseri Sıralaması ( Stooge Sort)
Şimşek(Bora) Sıralaması (Flash Sort)
Tarak Sıralaması (Comb Sort)
Gnome Sıralaması (Gnome Sort)
Permütasyon Sıralaması (Permutation Sort)
İplik Sıralaması (Strand Sort)

Yukarıda verilen veya herhangi bir sıralama algoritması genelde küçükten büyüğe doğru(ascending)sıralama yapar. Ancak bunun tam tersine çevirmek(descendin) genelde algoritma için oldukça basittir. Yapılması gereken çoğu zaman sadece kontrol işleminin yönünü değiştirmektir. Ayrıca 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)
Dahili Sıralama(Internal Sort)

Seçerek Sıralama (Selection Sort):
Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe her adımda dizideki en küçük sayının nerede olduğu bulunur. Bu sayı ile dizinin başındaki sayı yer değiştirilerek en küçük sayılar seçilerek başa atılmış olur.

Hızlı Sıralama Algoritması (Quick Sort Algorithm):
Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe sıralanacak olan dizideki orta noktada (mean) bulunan bir sayıyı seçerek diğer bütün sayıları bu orta sayıdan büyük veya küçük diye sınıflayarak sıralama yapmayı hedeflemektedir. Bu açıdan bir parçala fethet (divide and conquere) yaklaşımıdır. Ayrıca bu seçilen orta noktaya eksen (pivot) adı da verilir çünkü bütün diğer sayılar bu sayının ekseninde sıralanacaktır.

Birleştirme Sıralaması (Merge Sort):
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.

Yığınlama Sıralaması ( Heap Sort) :
Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Yığınlama sıralaması, arka planda bir yığın ağacı(heap) oluşturur ve bu ağacın en üstündeki sayıyı alarak sıralama işlemi yapar. (Lütfen yığın ağacındaki en büyük sayının her zaman en üstte duracağını hatırlayınız.)

Sayarak Sıralama (Counting Sort):
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.

Kabarcık(Baloncuk) Sıralama (Bubble Sort):
Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe ardışık duran iki hafıza bloğunun birbirine nispetle sıralanması ve bu işlemin sürekli tekrarlanması sayesinde
sıralar. Ardışık iki hafıza bloğuna bakmasından dolayı baloncuk ismini almıştır. Çünkü bu bakma işlemi bir baloncuğun (buble) hareket etmesi gibi sayıların üzerinde hareket etmektedir.

Taban Sıralaması (Radix Sort):
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.

Sokma Sıralaması (Insertion Sort):
Sokma sıralaması, programlaması oldukça basit ancak performansı bölme sıralaması (merge sort), hızlı sıralama(quick sort) gibi sıralamalara göre nispeten yavaş bir sıralama algoritmasıdır.

Sallama Sıralaması (Shaker Sort):
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.

Kabuk Sıralama (Shell Sort):
Bilgisayar bilimlerinde kullanılan sıralama algoritmalarından birisi de kabuk sıralamadır (shell sort). İsmi Türkçeye kabuk sıralaması olarak çevrilsede aslında Donald Shell isimli algoritmayı ilk bulan kişinin isminden gelmektedir.

Rastgele Sıralama (Bogo Sort):
Bilgisayar bilimlerinde özellikle eğitim amacıyla kullanılan bir sıralama algoritmasıdır. Algoritmanın çalışması oldukça basittir, bogosort, verilen bir diziyi sıralamak için rast gele bir dizilim üretir ve sıralı olup olmadığına
bakar, şayet sıralıysa algoritma sona erer, şayet sıralı değilse rastgele olarak yeni bir dizilim elde eder, ta ki sayılar sıralanana kadar sayıları rastgele dizmeye devam eder.

Şanslı Sıralama (Lucky Sort):
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. Algoritmaya çeşitli kaynaklarda şans sıralaması, lucksort, luckysort şeklinde isimler de verilir.

Serseri Sıralaması (Stooge Sort):
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.

Şimşek(Bora) Sıralaması (Flash Sort):
Bu yazının amacı bora sıralamasını (şimşek sıralaması, flash sort) açıklamaktır. Bu sıralama algoritması yapısal olarak aslında araya ekleme sıralamasının (insertion sort) özel bir hali olarak kabul edilebilir. Sıralama algoritmaları arasında parçalı sıralama özelliği olan diğer sıralama algoritmaları ile aynı sınıfta kabul edilebilir.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.

Tarak Sıralaması (Comb Sort):
Bu yazının amacı, tarak sıralaması (comb sort) olarak bilinen algoritmayı açıklamaktır. Algoritma, çıkışı itibariyle kabarcık sıralaması (bubble sort) ve hızlı sıralama (quick sort) karışımı olarak düşünülebilir.Tarak sıralaması aslında anlaşılması oldukça kolay bir algoritmadır.Kabarcık sıralamasında, sayılar sürekli olarak bir yanındaki sayı ile karşılaştırılır ve istenen sıraya göre yer değiştirme işlemi (swapping) yapılır. Tarak sıralamasında da benzer bir yaklaşım vardır ancak karşılaştırma ve yer değiştirme işlemleri hemen yan yana olan sayılar arasında değil de daha uzaktaki sayılar arasında yapılır. Yani kabarcık sıralaması bu anlamda aslında tarak sıralamasının özel bir örneği
(mesafenin 1 olduğu ) olarak düşünülebilir.Tarak sıralamasında mesafe herhangi bir sayı olabilir.

Gnome Sıralaması (Gnome Sort):
Bu yazının amacı, aptal sıralaması olarak bilinen (stupid sort) ve daha sonraları gnome sıralaması ismiyle anılan sıralama algoritmasını (sort algorithm) anlatmaktır. Algoritma 2000 yılında, Hamid Sarbazi-Azad tarafından bulunmuştur ve bir dizideki sayıları sıralama amacıyla, doğru aralığa taşımayı amaçlar.

Permütasyon Sıralaması (Permutation Sort) :
Bu yazının amacı, permütasyon sıralaması (permutation sort) olarak bilinen sıralama algoritmasını (sorting algorithm) açıklamaktır. Algoritma asılnda 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.

İplik Sıralaması (Strand Sort):
Bu yazının amacı, literatürde iplik sıralaması (strand sort) olarak geçen sıralama algoritmasını (sorting algorithm) açıklamaktır. Sıralama algoritması bağlı listeler (linked list) üzerinde etkili olan bir algoritmadır ve iki sıralı
listenin birleştirilerek yine sıralı bir liste oluşturulabileceği mantığına dayanır.iki liste birleştirilerek tek bir liste haline gelmiş ve liste sıralı sayılardan oluşmuştur.

Harici Sıralama (External Sort):
Bir sıralama algoritmasının tamamının bilgisayarın hafızasına (Memory, RAM) yüklü olmaması durumudur. Yani klasik olarak bir dizi (array) veya bağlı liste (linked list) üzerinde yapılan sıralamaları dahili sıralama
(internal sort) olarak isimlendirmek mümkündür.Harici sıralama klasik sıralamalardan farklı olarak, verinin ancak bir kısmının RAM’de durması durumunda devreye girer. Örneğin hafızamızın 100MB alan ile sınırlı olduğunu ve 100GB veriyi sırlamamız gerektiğini düşünelim. Bu durumda verinin hafızaya sığması mümkün olmayacak ve verinin harici bir alanda (örneğin disk veya ağ üzerindeki bir kaynakta) durması gerekecek.
Harici sıralama algoritmaları verinin bir kısmını sıralayıp sonra hafızadaki verinin yerini değiştirip yeni veriyi sıralamak ve en nihayetinde tüm veriyi doğru sıraya sokmak gibi bir yol izlerler.Örneğin en çok kullanılan harici sırlama algoritmalarından, harici birleştirme sıralaması (external merge sort)
aynen yukarıda anlatıldığı gibi önce verileri parçalara böler, sonra her parçayı kendi içerisinde sıralar ve en sonunda da verileri birleştirir.Elbette verilerin birleşmesi sırasında, verinin tamamının hafızaya sığmaması söz konusudur. Bu durumda verinin parça parça hafızaya yüklenmesi ve sıralanması gerekir.
Bu yöntem ayrıca paralel ve dağıtık sistemlerde de kullanılabilir.