Sorting Algorithms | Sıralama Algoritmaları | Insertion Sort-Merge Sort
Bir sorunu çözmek veya belirlenmiş bir amaca ulaşmak için tasarlanan yola, takip edilen işlem basamaklarına algoritma denir. Algoritmalar açıkça belirtilmiş bir başlangıcı ve sonu olan işlemler kümesidir. Amaca ulaşmak için işlenecek çözüm yolları ve sıralamaları belirlenir ve algoritma bu sırayı takip ederek en mantıklı çözüme ulaşır.
Temel olarak algoritma analizindeki iki önemli kriter şunlardır :
- Hafıza verimliliği (memory efficiency)
- Zaman verimliliği (Time efficiency)
Bir algoritmanın hızlı çalışması daha çok hafızaya ihtiyaç duyması anlamına gelir. Tersi durumda ise bir algoritmanın daha az yere ihtiyaç duyması daha yavaş çalışması anlamına gelir. Ancak bir algoritma hem zaman hem de hafıza olarak verimliyse bu durumda diğer algoritmalardan daha başarılı sayılabilir.
Genellikle verinin hafızada saklanması sırasında veriyi tutan bir belirleyici özelliğinin 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 eğer belirleyici alan sıralı ise erişimin logaritmik zamanda olması mümkündür. Ancak veri sıralı değilse erişim süresi doğrusal (linear) zamanda olmaktadır.
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. Birçok sıralama algoritması vardır, bu yazıda Insertion Sort ve Merge Sort ele alınmıştır.
Büyük O Notasyonu — Big O Notation
Büyük O (Big-O) gösterimi matematiksel bir gösterim olup işlevlerin (fonksiyonların) asimptotik davranışlarını tarif etmek için kullanılır. Daha açık şekilde anlatmak gerekirse, bir işlevin büyümesinin asimptotik üst sınırını daha basit başka bir işlev cinsinden tanımlanması demektir. İki temel uygulama alanı vardır: matematik alanında genellikle kırpılmış bir sonsuz serinin kalan terimini karakterize etmek için kullanılır; bilgisayar bilimlerinde ise algoritmaların bilgi işlemsel karmaşıklığının çözümlemesi için kullanılır. Büyük O Notasyonu kısaca, algoritmamızın performansını ve karmaşıklığını ölçmek için kullandığımız bir araçtır.
Time Complexity -Zaman Karmaşıklığı
Bilgisayar biliminde time complexity, bir algoritmanın çalışma süresini gösteren ifadedir. Time Complexity bir algoritma analizi yöntemidir. Bir algoritmanın çalışma süresi aldığı girdilere göre farklılık gösterir. Bu nedenle time complexity girdilerin (n) bir fonksiyonu (f(n)) olarak ifade edilir. Time complexity genellikle T(n) ile gösterilir.
Time complexity ‘de gösterilirken kullanılan birim saniye, dakika zaman birimleri değildir.Tam bir sonuç bulmak (doğru f(n)’i bulmak) çok güçtür. Bunun yerine n değeri büyürken f(n) fonksiyonunun davranışını incelemek yani asimptotik analiz yapmak daha uygundur. Bu nedenle zaman karmaşıklığı genellikle Big O Notation ile gösterilir.
INSERTION SORT
Insertion Sort bilgisayar bilimlerinde kullanılan linear bir sıralama algoritmasıdır. Amaç verilen örüntüye ait en küçük elemanı bulup solundaki eleman ile değiştirerek küçükten büyüğe sıralamaktır. Insertion Sortta Time Complexity durumları şunlardır:
- Best Case Complexity O(n)
- Average Case Complexity O(n²)
- Worst Case Complexity O(n²)
Best Case Complexity verilen inputun algoritmamızı en hızlı şekilde çalıştırdığı durumdur. Verilen örüntü,dizi ya da öğedeki elemanlar zaten sıralıysa ortaya çıkar. Algoritma n tane elemanı n kere kontrol eder bu sebeple Big O Notation O(n)’dir.
Average Case Complexity genel olarak beklediğim durumdur. Verilen dizi karışık haldedir yani tam olarak azalan ya da artan olarak sıralanmamış haldedir. Burada inputların geldiği dağılımı bilip ona göre analiz etmek gerekiyor. Average case’i analiz etmek diğerlerine göre çok daha zordur ancak algoritmamızın çalışmasını en iyi yansıtan case’dir. Big O Notation ise O(n²)’dir.
Worst Case Complexity verilen inputun algoritmamızı en yavaş şekilde yani en fazla işlem yapacak şekilde çalıştırdığı durumdur. Her elemanı birbiriyle karşılaştıracağı için her elemanı kontrol edecek bu sebeple Big O Notation O(n²)’dir.
Insertion Sort algoritmasının temel çalışma mantığı şu şekildedir. Verilen dizideki elemanlar 0'dan başlayarak indekslenir. İlk adımda key olarak 1. eleman seçilir ve 1. elemanla başlanır. 1. elemanın solundaki sayı büyükse 1. elemanla yer değiştirir. Eğer solundaki sayı zaten küçükse ya da o sayıya eşitse aynen kalır ve bir dahaki adımda dizinin 2. indeksindeki elemanın solundaki elemanlarla kontrole devam edilir. Küçük olan sola geçerken büyük olan sağa kayar yani bir bakıma yer değiştirirler.
(Örnekler patika.dev sitesindeki Veri Analizi Patikasında verilen ödev sorularıdır. Çözümler bana aittir. Daha fazla örnek için bahsettiğim patikaya bakmanızı öneririm. )
Örnek: [22,27,16,2,18,6]
Öncelikle Time complexity’nin Average case olduğunu söylememiz gerek. Dizi düzgün sıralı değil bu sebeple Best case değil. Aynı şekilde tersine bir sıralama da yok, worst case değil diyebiliriz. Big O Notation O(n²)’dir.
- adım : key = dizi[1] Burada 22<27 olduğu için aynen kalıyor.
2. adım : key = dizi[2] -> [16,22,27,2,18,6]
3. adım : key = dizi[3] -> [2,16,22,27,18,6]
4. adım: key = dizi[4] -> [2,16,18,22,27,6]
5. adım : key = dizi[5] -> [2,6,16,18,22,27]
Örnek 2: [7,3,5,8,2,9,4,15,6]
1. adım : key = dizi[1] -> [3,7,5,8,2,9,4,15,6]
2. adım : key = dizi[2] -> [3,5,7,8,2,9,4,15,6]
3. adım : key = dizi[3] -> [3,5,7,8,2,9,4,15,6]
4. adım : key = dizi[4] -> [2,3,5,7,8,9,4,15,6]
5. adım : key = dizi[5] -> [2,3,5,7,8,9,4,15,6]
6. adım : key = dizi[6] -> [2,3,4,5,7,8,9,15,6]
7. adım : key = dizi[7] -> [2,3,4,5,7,8,9,15,6]
8. adım : key = dizi[8] -> [2,3,4,5,6,7,8,9,15]
MERGE SORT
Merge Sort birleştirme sıralaması olarak bilinen ve “Divide and Conquer” (Böl ve Fethet) mantalitesine dayanan bir sorting algoritmasıdır. Linear değildir. Lineer algoritmalara göre çok daha hızlı olduğu için genellikle çok büyük verilerde kullanılır. Daha hızlı olmasının sebebi Time Complexity’nin Merge Sort’da nlogn olmasıdır. Temel mantığı “en küçük parçalara ayır, birleştirirken sırala” şeklindedir.
Worst case, Best case ve Average case için time complexity O(nlogn)’dir.
Örnek : [16,21,11,8,12,22]
- adım : |16,21,11| |8,12,22|
- adım : |16,21| |11| |8,12| |22|
- adım : |16| |21| |11| |8| |12| |22|
Buraya kadar olan kısım algoritmanın “Divide” bölümünü,devamındaki kısım ise “Conquer” yani birleştirirken sırala kısmını oluşturmaktadır.
4. adım : |16,21| |11| |8,12| |22|
5. adım : |11,16,21| |8,12,22|
6.adım : |8,11,12,16,21,22|
