GitHub - zumrudu-anka/Algorithms: :man_technologist: Searching and Sorting Algorithms

Contents(İçindekiler)

Algorithms(Algoritmalar)
1. Searcing Algorithms(Arama Algoritmaları)
2. Sorting Algorithms(Sıralama Algoritmaları)
Kaynakça

Algorithms

Algoritma, istenen çıktıyı elde etmek için belirli bir sırada gerçekleştirilecek bir dizi talimatı adım adım tanımlayan bir prosedürdür. Algoritmalar genellikle altta yatan dillerden bağımsız olarak oluşturulur, yani birden fazla programlama dilinde bir algoritma uygulanabilir.

Searcing Algorithms

Linear Search - Doğrusal arama çok basit bir arama algoritmasıdır. Tüm öğeler üzerinde birer birer sıralı bir arama yapılır. Her değer kontrol edilir ve eğer bir eşleşme bulunursa o zaman o değerin bulunduğu index geri döndürülür, aksi takdirde üzerinde arama yapılan veri dizisinin sonuna kadar arama devam eder. Sıralı ve sıralı olmayan veri dizisi üzerinde olmak üzere 2 farklı şekilde oluşturulabilir:
- For Unordered List : Sıralı olmayan veri dizisinde arama, aranan eleman bulunmadığı takdirde veri setinin sonuna kadar devam eder.
- For Ordered List : Sıralı veri dizisinde ise aranan eleman dizideki her elemanla kıyaslanırken eğer kıyaslandığı elemandan küçük(veri dizisi küçükten büyüğe doğru sıralanmış ise) olduğu bir durum olursa, dizi sıralı olduğu için aranan elemanın ilgili index'ten sonra bulunabilme ihtimali olmayacağı için arama otomatik olarak sonlandırılır. Böylece zaman açısından daha verimli bir sonuç elde edilir.
Jump Search - Atlamalı arama doğrusal aramaya göre daha hızlı, ikili aramaya göre daha yavaş kalan ve sıralı veri setleri üzerinde çalışan bir arama algoritmasıdır. Temel fikir, sabit adımlarla ileriye atlayarak, dizinin tüm elemanlarını aramak yerine bazı elemanları atlayarak doğrusal aramaya göre daha az elemanı kontrol etmektir.
➥ Step Size: Jump search yaparken aradığımız değerin en kötü ihtimalle dizinin sonlarında olduğunu düşünelim. Bu durumda en kötü ihtimalle dizinin n elemanlı ise ve atlama adım büyüklüğümüz m ise (n / m) kadar atlama yapmış oluruz. (n / m) atlama yaptıktan sonra da aradığımız değerin bu son adımımızın içinde olduğunu ve bu adımın içindeki son eleman olduğunu düşünürsek (m - 1) eleman daha kontrol etmiş oluruz. Yani en kötü durumda toplam karşılaştırma sayısı:
(n / m) + (m - 1)
olacaktır. Algoritmanın performansı ve hızı açısından bu eşitliğin minimum değer üretmesini isteriz. Bu yüzden bu ifadenin üretebileceği minimum değeri bulmak için(yerel minimum noktası arıyoruz) denklemin m değerine göre türevini alıp sıfıra eşitleriz:
n / -m² + 1 = 0
ifadesini elde etmiş olduk. Bu ifadeyi de çözümleyecek olursak: n = m²
m = √n
Böylece atlamalı aramada tercih edilecek en iyi atlama adımı uzunluğunu dizinin boyunun karekökü olarak bulmuş olduk. Örneğin aşağıdaki dizi içerisinde 5 değerini atlamalı arama ile bulmaya çalışalım:

Öncelikle step size yani atlama adımı uzunluğumuzu bulalım. Dizi 9 elemanlı olduğu için:
step_size = √9 = 3
olarak bulunmuş olur. Daha sonra ilk elemandan itibaren 3 adım atlayarak bulunduğumuz değeri aradığımız değer ile karşılaştırırız. İlk atlamadaki 4 değeri ile 5 değeri eşleşmediği ve 4 değeri 5 değerinden küçük olduğu için bir adım daha atlarız. İkinci atlamamızda bulunduğumuz indisin 7 olan değeri aradığımız 5 değerinden büyük olduğu için artık ileriye doğru atlama yapmayız ve bu değerimizi bir önceki adımımızda durduğumuz indis ile şu an durduğumuz indis arasında doğrusal arama yaparak ararız. Böylece aradığımız 5 değerini dizinin 4 numaralı indisinde bulmuş oluruz.
Binary Search - İkili arama böl ve yönet prensibi ile çalışan hızlı bir arama algoritmasıdır. Bu algoritma sıralı veri setleri üzerinde düzgün olarak çalışır. İkili arama, aranan değer ile veri dizisinin en ortasındaki değeri karşılaştırır. Bir eşleşme olursa, o zaman ilgili index geri döndürülür. Eşleşme olmamışsa ve ortadaki değer aranan değerden büyükse, değer ortadaki indexin solundaki alt dizide, aksi halde ortadaki indexin sağındaki alt dizide aranır. Bu işlem, alt dizinin boyutu sıfıra inene kadar devam eder. Görselleştirilmiş bir örnek ile ikili aramayı daha iyi anlayacağınızı umuyorum.

Aşağıdaki sıralı dizide 31 değerininin indexini bulmaya çalıştığımızı varsayalım:



Öncelikle dizinin ortasındaki indexi belirleyeceğiz:

mid = low + (high - low) / 2    -->    mid = 0 + (9 - 0) / 2 = 4.5  (4 tamsayı değeri)



Yani dizinin ortasındaki indis 4 olarak bulunur. Daha sonra dizinin 4. indisindeki değer ile aranan değer yani 31 değeri karşılaştırılır. Dizinin 4. indisindeki 27 değeri ile aranan 31 değerinin eşleşmediği tespit edilir. Aranan 31 değeri 27'den büyük olduğu ve dizimiz de sıralı bir dizi olduğu için, aranan değerimiz dizinin üst kısmında(4. indisin sağ tarafındaki alt dizide) bulunabilir. Bu yüzden 31 değerini bu alt dizide aramak üzere dizimizin en küçük indisini ortanca indisten 1 büyük olmak üzere güncelleyeceğiz:



low = mid + 1
mid = low + (high - low) / 2 Artık yeni ortanca indisimiz 7 olduğu için, 7. indisteki değer ile 31 değerini karşılaştırıyoruz.


Dizinin 7. indisindeki değer ile aradığımız 31 değeri eşleşmediği için ve aradığımız değer bu indisteki 35 değerinden küçük olduğu için aranan değerimizi alt dizinin alt dizisinde(7. indisin sol tarafındaki yeni alt dizide) aramalıyız.



high = mid - 1
mid = low + (high - low) / 2 Yeni ortanca indisimiz 5 olarak hesaplanmış oldu.



Dizinin 5. indisindeki değer ile aradığımız değeri tekrar karşılaştığımızda bir eşleşme olduğunu tespit ettik.



Böylece aradığımız değerin hedef veri setinin 5. indisinde bulunduğu sonucunu elde etmiş olduk.
Interpolation Search - İnterpolasyon arama algoritması ikili arama algoritmasına çok benzer bir algoritmadır. Yine sıralı veri setleri üzerinde, böl ve yönet prensibiyle çalışır. İkili aramadan farkı ise ikili arama algoritması ile arama yaparken dizinin ortanca elemanına bakıyorduk ve karşılaştırma sonucuna göre diziyi ikiye bölüp dizinin sağ veya sol alt dizisinde değerimizi arıyorduk. İnterpolasyon aramada ise diziyi böleceğimiz pozisyon değerini, yani merkez alınacak indisi aşağıdaki formül ile hesaplıyoruz:

position = low + [ (high - low) / (array[high] - array[low]) * (value - array[low]) ]
    position ➺ Karşılaştırma yapacağımız ve karşılaştırma sonucuna göre diziyi bölmek için baz alacağımız pozisyon
    array     ➺ Arama yaptığımız dizi
    low        ➺ Dizinin en küçük indisi
    high       ➺ Dizinin en büyük indisi
    value     ➺ Dizide bulmak için arama yaptığımız değer

Algoritma ise aşağıdaki adımlardan oluşuyor:
- Pozisyon değerini hesapla ve aranan değer ile dizinin pozisyon numaralı indisindeki değeri karşılaştır.
- Eşleşme olursa geriye değerin bulunduğuna dair bir sonuç döndür.
- Aksi halde, aranan değer dizinin ilgili indisinden küçükse sol, büyükse sağ alt dizide pozisyon hesapla ve arama yap.
- Eşleşme bulunana kadar veya alt dizi boyutu 0 olana kadar işlemlere devam et.

Sorting Algorithms

Sıralama algoritmaları, verileri belirli bir düzende sıralama yollarını belirtir. En yaygın sıralamalar sayısal veriler veya sözlük sıralamalarıdır. Sıralamanın önemi, veriler sıralı bir şekilde saklanırsa, bu veriler üzerinde arama yapmanın çok yüksek bir performans düzeyine getirilebileceği gerçeğinde yatmaktadır. Sıralama, telefon rehberlerinde veya sözlüklerdeki kelimelerde olduğu gibi verileri daha okunabilir formatlarda göstermek için de kullanılabilir.

Bubble Sort - Kabarcık sıralama basit bir sıralama algoritmasıdır. Bu sıralama algoritması, her bir bitişik eleman çiftinin karşılaştırıldığı ve sıralı olmadıklarında elemanların yer değiştirildiği karşılaştırma tabanlı bir algoritmadır. Bu algoritma, büyük veri kümeleri için uygun değildir. Çünkü n elemanlı bir dizi için ortalama ve en kötü durum karmaşıklığı O(n²)'dir. Aşağıdaki örnek ile kabarcık algoritmasını görselleştirerek anlamaya çalışalım:



Şekildeki gibi sıralanmamış ve kısa bir diziyi kabarcık sıralama algoritması ile sıralayacağız. Bunun için ilk iki elemandan başlayarak ikişerli ikişerli karşılaştırma yapacağız.



İlk karşılaştırmada 33 değeri zaten 14 değerinden büyük olduğu için ilk 2 değerin zaten sıralanmış olduğunu görüyoruz. Bu yüzden yer değiştirme yapmadan sonraki 2 değer olan 33 ile 27 değerini karşılaştırıyoruz.



27 değeri ile 33 değerini karşılaştırdığımızda 27 değeri 33 değerinden küçük olduğu için bu iki değerin yer değiştirmesi gerektiğini tespit ettik.



Yer değiştirme işleminden sonra dizimiz aşağıdaki gibi olmalı:



Sıralama işlemine kaldığımız yerden devam ediyoruz ve 33 ile 35 değerlerini karşılaştırıyoruz.



Zaten sıralı oldukları için yer değiştirme yapmadan sıralama işlemine devam ediyoruz ve 35 ile 10 değerlerini karşılaştırıyoruz.



10 değeri 35 değerinden küçük olduğu için sıralı olmadıklarını ve bu 2 değerin yer değiştirmesi gerektiğini tespi ettik.



Bu 2 değerin yerlerini değiştiriyoruz ve dizinin sonuna geldiğimizi görüyoruz. Böylece dizideki en büyük eleman dizinin sonuncu indisine yerleşti ve dizimiz şimdilik aşağıdaki gibi oldu.



Tüm dizi sıralanana kadar algoritmayı uygulamaya devam ediyoruz ve bunun için tekrar ilk indisten başlayarak son indis hariç bir şekilde aynı işlemleri uyguluyoruz. Böylece bir sonraki iterasyonda dizimiz aşağıdaki gibi görünecektir.



Bir sonraki iterasyondan sonra ise dizimiz aşağıdaki gibi görünüyor ve her iterasyondan sonra en az 1 değerin yer değiştirdiğini görüyoruz.



İterasyonlara devam ederken herhangi bir yer değiştirme işlemine gerek kalmadığında kabarcık sıralama algoritması ile verilerimizi sıralamış oluruz ve nihai olarak dizimiz aşağıdaki gibi olur.
Merge Sort - Birleştirme sıralama, böl ve yönet tekniğine dayanan bir sıralama algoritmasıdır. Merge sort, sıralanacak diziyi alt dizi eleman sayısı 1 olana kadar sürekli yarıya böler ve sonra en küçük alt diziden en büyük diziye doğru bu alt dizileri sıralı bir şekilde birleştirir. Aşağıdaki gibi sıralanmamış bir dizimiz olsun:



Atomik değerler elde edene kadar sıralamak istediğimiz diziyi yinelemeli olarak 2 eşit parçaya böleceğiz. 8 elemandan oluşan dizimizi ilk aşamada 4 elemanlı 2 eşit parçaya böldük.



Sıralama işlemi dizi atomik değerlere parçalanana kadar başlamayacağı için yarılanmış parçalar henüz sıralı olmayacaktır. Atomik değerler elde edene kadar elde edilen alt dizileri de 2 eşit parçaya bölmeye devam ediyoruz.



Elde edilen dizileri 2 eşit parçaya bölme işlemine devam ediyoruz ve sonunda tek elemanlı atomik dizilerimizi elde ediyoruz.



Şimdi sıra atomik değerlerimizi sıralayarak birleştirme işlemine geldi. Karşılaştırma yapıp sıralayarak birleştireceğimiz diziler aynı renklerde gösterilmiştir. Öncelikle aynı renklerdeki listelerin değerlerini karşılaştırırız ve daha sonra bunları sıralı bir şekilde başka bir listede birleştiririz. 14 ve 33 değerlerinin sıralı pozisyonlarda olduğunu görüyoruz. 27 ile 10 değerlerini karşılaştırıyoruz ve 10 değeri 27 değerinden küçük olduğu için bu iki değeri ilk elemanı 10 olacak şekilde birleştiriyoruz. 19 ve 35 değerlerinin de sırasını değiştirirken 42 ve 44 değerlerinin sırasını değiştirmeden bu elemanları da birleştiriyoruz.



Birleştirme aşamasının bir sonraki iterasyonunda, daha önce birleştirme yaparak elde ettiğimiz listeleri karşılaştırır ve elemanları sıralı olacak şekilde bu listeleri de birleştiririz.



Son iterasyon ile yapılacak birleştirme işleminden sonra da listemiz nihai olarak aşağıdaki şekilde görünecektir.
Insertion Sort - Ekleme sıralama algoritması yerinde karşılaştırma tabanlı bir sıralama algoritmasıdır. Bu algoritmada her zaman, sıralanan bir alt liste tutulur. Algoritmada dizinin ilk elemanı alt liste olarak belirlenir ve ilk aşamada alt listede zaten tek eleman olduğu için bu alt liste sıralıdır. Dizinin ikinci indisinden başlanarak ve her iterasyondan sonra indis numarası da son iterasyonda dizi boyutu olacak şekilde artırılarak, her iterasyonda dizinin daha küçük indislerine doğru karşılaştırma yapılır ve her eleman kendine uygun sırayı bulduğunda sırayla alt diziye eklenir. Aşağıdaki örnek ile algoritmamızı daha detaylı inceleyelim.



İlk iki elemanı karşılaştırarak algoritmayı uygulamaya başlıyoruz.



İlk iki değer olan 14 ve 33 değerlerinin sıralanmış olduğunu yani 14 değerinin konumunun doğru olduğunu tespit ediyoruz ve 14 değerine sıralanmış alt listede yerini veriyoruz.



Algoritmayı uygulamaya devam ediyoruz ve 27 değeri ile 33 değerini karşılaştırıyoruz.



Karşılaştırmada 33 değerinin konumunun doğru olmadığını tespit ediyoruz.



Sıralı olmadıkları için 27 ile 33 değerlerinin yerini değiştiriyoruz ve sıralanmış alt listedeki tüm elemanları 27 ile karşılaştırmaya devam ederek konumlarını kontrol ediyoruz.Sıralanmış alt listenin tek elemanı olduğunu ve 14 değerine sahip bu elemanın zaten 27 değerinden küçük olduğunu görüyoruz.



Sonuç olarak şu anda alt listemize 14 ve 27 değerleri yerleşmiş bulunmaktalar. Algoritmayı uygulamaya kaldığımız yerden devam ediyoruz ve 10 değeri ile 33 değerlerini karşılaştırıyoruz.



Bu 2 değerin sıralı olmadıklarını görüyoruz.



Sıralı olmadıkları için bu iki değerin yerlerini değiştiriyoruz.



Bu yer değiştirme işleminden sonra 10 değerini alt listeyle en küçük indise inene veya bu değerin alt listedeki doğru konumunu bulana kadar karşılaştırmaya devam ediyoruz ve 10 ile 27 değerlerinin de sıralı olmadığını tespit ediyoruz.



Sıralı olmadıkları için 10 ve 27 değerlerinin de yerlerini değiştiriyoruz.



Algoritmayı uygulamaya devam ediyoruz ve 10 ile 14 değerlerinin de sıralı olmadığını tespit ediyoruz.



Sıralı olmadıkları için bu değerlerin de yerlerini değiştiriyoruz ve 3 iterasyon sonucunda ilk 4 elemanın 3 elemanlı sıralanmış alt listesini elde etmiş bulunuyoruz.



Aynı işlemlere sıralanmamış tüm değerler sıralanmış bir alt listeye yerleşene kadar devam ediyoruz ve nihai olarak listemizi sıralı bir şekilde elde ediyoruz.
Selection Sort - Selection sort algoritması, sıralamak istediğimiz listeyi soldaki sıralanmış alt liste ve sağdaki sıralanmamış alt liste olacak şekilde ikiye ayıran karşılaştırma tabanlı bir algoritmadır. Başlangıçta, sıralanan taraf boştur ve sıralanmamış taraf ise listenin tamamıdır. Listenin en küçük elemanı sıralanmamış kısımdan seçilir, en soldaki eleman ile değiştirilir ve bu eleman artık sıralanan dizinin elemanı olur. Bu işleme sıralama işlemi bitene kadar, sıralanmamış dizinin alt sınırını birer birer arttırarak devam ederiz. Aşağıdaki sıralanmamış dizi üzerinde selection sort algoritmasını uygulayalım.



Sıralanmış listedeki ilk konum için listedeki tüm elemanları sırayla tarıyoruz ve 10 değerinin listedeki en küçük değer olduğunu tespit ediyoruz.



Bu yüzden listenin ilk indisindeki 14 değeri ile 10 değerlerinin yerlerini değiştiriyoruz. Böylece sıralanmamış listenin en küçük elemanı olan 10 değeri sıralanmış listenin ilk konumuna yerleşmiş oldu.



Sıralanmamış listenin alt sınırını 1 arttırarak algoritmayı uygulamaya devam ediyoruz ve 33 değerinin bulunduğu ikinci konum, yani artık sıralanmamış listenin ilk konumu için listenin geri kalanını doğrusal bir şekilde arıyoruz.



14 değerinin listedeki en küçük ikinci değer olduğunu ve ikinci sırada, diğer bir deyişle de sıralanmamış listenin en küçük elemanı olduğunu ve sıralanmamış listenin ilk indisinde görünmesi gerektiğini tespit ediyoruz.



İki iterasyondan sonra, en az iki değerin sıralı olarak konumlandırıldığını görüyoruz.



Tüm dizi sıralanana kadar aynı işlemleri dizinin geri kalan elemanlarına uygulayarak selection sort algoritmasını tam olarak tamamlıyoruz.
Quick Sort - Sıralanmak istenen veri dizisinin daha küçük dizilere parçalanmasına dayanan oldukça verimli bir sıralama algoritmasıdır. Büyük bir dizi, dizi içerisinde seçilen rastgele bir değerden(genelde dizinin sonuncu elemanı) daha küçük ve daha büyük değerleri tutacak olan iki diziye bölünür ve bu işlemi yaparken referans aldığımız değer işlem bittikten sonra pivot olarak adlandırılır. Daha sonra tekrar aynı algoritmayı bu pivot değerinin solunda kalan diziye ve sağında kalan diziye uygulayarak bu alt dizilerin pivot değerleri elde edilir. Böylece bu alt diziler de aynı işlemler sürecinde kendi alt dizilerine parçalanacaktır. Bu recursive(yinelemeli) işlemler parçalanmış dizilerin eleman sayısı 1 olduğunda son bulacaktır ve büyük dizimiz sıralanmış olacaktır.

Yukarıdaki animasyonu beraber inceleyelim. Öncelikle dizinin sonuncu elemanı referans değer olarak seçildi. Daha sonra dizinin en küçük indisi low index ve sondan ikinci indisi ise high index olarak seçildi. Low index değeri high index değerinden küçük olmak şartıyla(1. kural); low index eleman değeri referans değerden küçük olduğu sürece(2. kural) low index değeri artırıldı ve high index eleman değeri referans değerden büyük olduğu sürece(3. kural) high index değeri azaltıldı. 1. kural sağlandığı sürece hem 2. hem de 3. kuralın sağlanmadığı low index ve high index değerleri tespit edildiğinde bu indexlerin değerlerinin yerleri değiştirildi. 1. kural bozulduğunda yani low index değerinin high index değerine eşit olma durumu söz konusu olduğunda, eşit oldukları index eleman değeri ile referans değerin yerleri değiştirildi ve referans değer pivot değer kabul edilerek liste bu pivot değerin sol tarafı ve sağ tarafı olmak üzere ikiye bölündü. Aynı işlemler bu bölünmüş diziler üzerinde de uygulanmaya devam edecek ve algoritma sonlandığında tüm dizi sıralanmış olacaktır.
Aynı algoritmaların çözümlerine farklı yaklaşımlar olabilir. Bu repository'den ulaşabileceğiniz Quick Sort algoritması çözümünde yine dizinin son elemanı referans değer olarak seçildi. Dizinin ilk index değeri low index olarak seçildi ve ilk eleman değerinden başlanarak dizinin sondan 2. elemanına kadar referans değerden küçük olan eleman ile dizinin low index değerindeki eleman değiştirildi ve low index değeri bu işlem her gerçekleştiğinde 1 arttırıldı. Bu iterasyon tamamlandığında referans değerden küçük olan değerlerin hepsi low index değerinin sol tarafında birikmiş oldu. Böylece bu low index değerinin ve sağ tarafındaki değerlerin referans değere eşit veya büyük olduğunu garantilemiş olduk. Low index değeri ile referans değerin yerini değiştirdiğimizde ise artık low index değeri referans aldığımız değeri göstermiş oldu ve böylece referans değerin sol tarafında bu değerden küçük elemanlar ve sağ tarafında ise kendisine eşit veya büyük elemanlar birikmiş oldu. Bu değeri pivot değer olarak seçtik ve büyük listeyi bu pivot değerin sol ve sağ tarafı olmak üzere ikiye böldük. Aynı işlemleri bu bölünmüş dizilere de uygulayarak algoritmamızı tamamladık.