En popüler kullanılan yazılım algoritmaları neler? Algoritmalar hangi alanlarda kullanılır?
Yazılım başarısına giden yol, yazılım algoritmalarından geçer ????
Programlama dillerinin temelinde algoritma vardır. Herhangi bir programlama dili öğrenmeden önce mutlaka algoritmaların çalışma mantığını anlamalısınız. Geliştirilen projelerde kullanılan dil ve kullanım alanı ne olursa olsun algoritması olmayan bir program yoktur.
Günlük hayatta karşılaşabileceğiniz sorunlar algoritma yapısıyla oldukça kolay şekilde çözülüyor. Hangi durumda neler yapılması gerektiği konusuyla ilgili planlar, algoritma özelliği taşıyor.
Bu blog yazısında ise, algoritmaların hayatımızda neden bu kadar önemli konumda olduğu sorusuna yanıt arayarak yazılımcıların mutlaka bilmesi gereken yazılım algoritmaları listesi oluşturduk.
Algoritma Nedir?
Algoritma; belirli bir problemin ya da sorunun çözümü için ihtiyaç duyulan tüm işlemlerin sıralı ve mantıksal olarak ifade edilme şeklidir.
Algoritmalar açıkça belirtilmiş bir başlangıcı ve sonu olan işlemler kümesidir.
Algoritma; programlama ya da yazılım geliştirmenin yanı sıra, günlük hayattaki aktiviteler, matematik gibi derslerde karşılaşılan sorunları daha kolaylıkla çözme olanağı sağlar. Bizim farkında bile olmadığımız, hayatımızın birçok yerinde algoritma örnekleri mevcut. Programlama mantığında bir algoritmanın başlatılması için dışarıdan gelen girdiler “değişken” olarak tanımlanır. Algoritmadaki döngüler ve işlemler ise bu değişkenler üzerinden gerçekleşir.
Yazılımda Algoritma Mantığı Nedir?
Bilgisayarlar, gerçekleştirdikleri tüm işlemleri programlar sayesinde yapar.
Bir programın bilgisayarı yönlendirmesi aşamasında ne yapması gerektiğini adım adım bilgisayara açıklamak gerekir. Bilgisayarların algoritmaları anlayabilmesi, kullandığınız programlama dili sayesinde gerçekleşir. Aynı zamanda bilgisayarlara programlar aracılığıyla nasıl yapması gerektiğini de açıklamanız gerekir. Bilgisayar algoritmaları ise bu noktada önem kazanır.
En Popüler Yazılım Algoritmaları
Sıralama Algoritmaları
Sıralama algoritmaları, çok sayıda öğeyi yüksekten düşüğe veya tam tersi gibi belirli bir sıraya veya alfabetik sıraya göre yeniden düzenleme yöntemleridir.
Sıralama algoritmaları, genellikle bir problemin karmaşıklığını azaltabildiğinden dolayı çalışma mantığı en kolay anlaşılacak algoritmalarından biridir.
Performans karşılaştırmasını yaptığımız başlıca yöntemlerle birlikte, çok sayıda farklı sıralama algoritması bulunmaktadır.
Bunlar arasında en sık kullanılanları: Quick Sort, Bubble Sort, Merge Sort, Insertion Sort, Selection Sort, Heap Sort, Radix Sort ve Bucket Sort olarak sıralayabiliriz.
Kabarcık Sıralaması ( Bubble Sort ): Kabarcık sıralama algoritmasında, listedeki her bir eleman yanındaki eleman ile karşılaştırılır. Eğer ilk elemanın değeri, ikinci elemanın değerinden büyükse, iki eleman yer değiştirir. Daha sonra ikinci ve üçüncü elemanların değerleri karşılaştırılır. İkinci elemanın değeri üçüncü elemanın değerinden büyükse bu iki eleman yer değiştirir ve bu işlem, tüm liste sıralanana kadar bu şekilde devam eder.
bubble-sort
Seçerek Sıralama ( Selection Sort ): Bu algoritma, küçük boyutlu dizileri sıralarken veya dizinin bir bölümü sıralı ise yer değiştirme işlemi yapılmadığından dolayı tercih edilir. Aksi durumda düşük performans gösterir.
selection-sort
Eklemeli Sıralama ( Insertion Sort ): Bu algoritma, sıralı dizinin her seferinde bir öğe içerecek şekilde oluşturulduğu sıralama algoritmasıdır.
Dizi elemanları sıralı olarak birbirleriyle karşılaştırılır ve daha sonra eşzamanlı olarak belirli bir sırada düzenlenir.
insertion-sort
Yığın Sıralaması ( Heap Sort ): Bu algoritma, bir yığının kök düğümünü kaldırarak ve son yaprak düğümle (altta, sağda) değiştirerek ve ardından yeni kök düğümü aşağı doğru eleyerek gerçekleştirilir.
Heap_sort
Hızlı-Çabuk Sıralama ( Quick Sort ): Bu algoritma, aynı veri türlerine sahip elemanları böl ve yönet metoduna göre çalışır.
Özyineli(recursive) bir algoritma olmasından dolayı kendi kendini tekrar ederek sectiği elemana göre sıralama işlevini yürütmektedir.
quick sort
Birleştirmeli Sıralama ( Merge Sort ): Bu algoritma, en verimli sıralama algoritmalarından biridir. Böl ve Fethet prensibine göre çalışır. Birleştirme sıralaması, her bir alt liste tek bir öğeden oluşana ve bu alt listeleri sıralı bir liste oluşturacak şekilde birleştirene kadar bir listeyi tekrar tekrar birkaç alt listeye böler.
merge sort
Sıralama işlemini uygulamanın çok farklı seçenekleri vardır fakat bilgisayar mühendisliği temel olarak iki performans kriterini dikkate alır: hafıza verimliliği ve zaman verimliliği.
Sıralama Algoritmalarının Zaman Karmaşıklığı:
Algorithm Best Average Worst
Quick Sort Ω(n log(n)) Θ(n log(n)) O(n^2)
Bubble Sort Ω(n) Θ(n^2) O(n^2)
Merge Sort Ω(n log(n)) Θ(n log(n)) O(n log(n))
Insertion Sort Ω(n) Θ(n^2) O(n^2)
Selection Sort Ω(n^2) Θ(n^2) O(n^2)
Heap Sort Ω(n log(n)) Θ(n log(n)) O(n log(n))
Radix Sort Ω(nk) Θ(nk) O(nk)
Bucket Sort Ω(n+k) Θ(n+k) O(n^2)
Search ( Arama ) Algoritmaları
Yazılım algoritmaları listesinde bir diğer algoritma ise: arama algoritmaları.
Arama algoritmaları, bir veri yapısı üzerinde belirli bir verinin aranması için kullanılan algoritmalar bütünüdür.
Belirli durumlara spesifik olarak arama algoritmaları geliştirilmiştir ve kendi aralarında farklı avantajları ve çalışma süreleri vardır.
Bir liste ya da dizi üzerinde arama yapacaksanız iki temel kategori bulunuyor: sequential search ve ınterval search.
Bunların altında da farklı algoritmalar geliştirilmiştir. Bunlardan en basit ve anlaşılır olanlardan ikisi ise: linear search ve binary search’dir.
Sequential Search: Veri yapısında verilerin belli bir sıra ile tutulmadığında kullanılan arama algoritmasıdır. Bunun en güzel örneği de Linear Search algoritmasıdır.
Interval Search ise sıralı veri yapısı üzerinde uygulanan algoritmalar için kullanılır. Bunun altında Binary Search, Jump Search, Exponential Search, Fibonacci Search gibi algoritmalar bulunur.
Linear Search: Linear Search, genellikle yazılımcıların kodlamaya ilk başladığı zamanlarda kullandığı arama metodudur. Bu arama algoritması en basit ve çalışma zamanı olarak en kötü algoritmalardan biridir.
Bu algoritma ile, aranılan elemanı bulmak için aranan eleman bulunana kadar sırayla dizinin tüm elemanlarına bakılır.
Binary Search ise çalışma zamanı olarak Linear Search’den daha iyidir. Aranan elemanın bulunabilmesi amacıyla her defasında dizinin ortasındaki elemana bakılır. Ortadaki eleman ile aranan eleman eşit değilse, aranan elemanın bulunduğu diğer yarı alanda arama işlemi tekrar edilir.
binary-and-linear-search
Dijkstra Algoritması
Dijkstra Algoritması, çok basit bir mantıkla oluşturulmuş ve günümüzde oldukça popüler olan algoritmalardan biridir.
Bu algoritmanın amacı, çıkış noktası olarak belirlediği noktadan farklı düğümler aracılığıyla en kısa yol ile hedefe ulaşmaktır.
Günümüzde de internet trafiğinin yönlendirilmesinde, oyun programlamada oldukça sık kullanılmaktadır. Dijkstra algoritması, bir düğümden diğer bir düğüme geçerken mevcut durumun ‘en mantıklı ve en iyi’ çözüm yöntemini seçer.
Dijkstra algoritmasını kullanmamız için bazı kurallar vardır:
Grafımız ağırlık ve yöne sahip olmalı.
Kenarların ağırlık değeri sıfır ya da sıfırdan büyük bir değer olmalı.
Kenar değerleri sıfırdan küçükse bu durumda Bellamn-Ford algoritması kullanılabilir.
Dijkstra algoritmasını zaman karmaşıklığı O(MlogN)‘dir.
Bilinmesi gereken diğer algoritmalar ve veri yapıları
Ağaçlar
Ağaç yapısı; bir kök, sonlu sayıda düğümler ve onları birbirine bağlayan dallar olarak tanımlanan veri modelidir.
Ağaç terminolojinin tamamı bir soy ağacı kavramından gelmektedir. Ağaçtaki diğer düğümlere göre bir düğümün konumuna bağlı olarak diğer düğümlere ebeveyn, çocuk, kardeş, ata, soy gibi terimler kullanılır.
Binary Tree: Binary/İkili ağaç yapısında bir düğümün en fazla iki çocuğu bulunur. Bu çocuklar sağ ve sol çocuk olarak adlandırılır.
Complete Binary Tree: Her bir yeni derinliğe düğümler soldan sağa doğru eklenerek ilerlenir. Bu aşamada bir derinlik tamamlanmadan bir sonraki derinliğe geçme olasılığı yoktur.
Balanced Binary Tree: Her bir düğümün sol alt ağaç yüksekliği ile sağ alt ağaç yüksekliği arasında en fazla 1 fark olmalıdır.
Ağaç üzerinde nasıl dolaşırım ?
Ağaç üzerindeki gezinme işlemi, tüm düğümleri ziyaret ederek gerçekleştirilir. Ağaçları dolaşmak için kullanılan bir kaç algoritma örneği verirsek;
Pre-order Traversal (root-left-right)
Kökü ziyaret et
Sol alt ağacı dolaş
Sağ alt ağacı dolaş
In-order Traversal (left-root-right)
Sol alt ağacı dolaş
Kökü ziyaret et
Sağ alt ağacı dolaş
Post-order Traversal (left-right-root)
Sol alt ağacı dolaş
Sağ alt ağacı dolaş
Kökü ziyaret et
Graf Veri Yapısı
Bilgisayar dünyasında var olan ve gerçek hayatta çeşitli sebeplerle karşılaşılan yapıları temsil amacıyla kullanılan şekillerden biri de Graph yapısıdır.
Bir grafta yer alan nesneler düğümler ile ifade edilmekte, bu nesneler arasındaki ilişkiler ise graf yapısında bulunan kenarlar ile ifade edilmektedir.
Grafları kenarların yönlü olup olmamasına göre, yönlü graflar ve yönsüz graflar olarak ikiye ayırmak mümkündür. Kenarlarının değer almasına göre değerli graflar ve değersiz graflar isimleri verilir.
Graf yapısında, grafik geçişi çok önemlidir ve hızlı bir şekilde kullanmak isteyeceğiniz iki algoritma vardır: Kapsamlı İlk Arama (BFS) ve İlk Derinlik Arama (DFS).
