Ekleme Sıralaması (Insertion Sort) Nedir ?

Ekleme sıralaması (Insertion Sort) basit bir sıralama algoritmasıdır. Bu algoritmayı günlük hayatta oyun kartlarını elimizde sıralarken kullanıyoruz. Ekleme sıralamasının çok elemanlı listelerde kullanımı facia ile sonuçlanabilir. Büyük listeleri sıralarken genellikle quick, merge veya heap sort gibi algoritmalardan yararlanırız. Insertion sort küçük boyutlu listelerde(ortalama 30 ve altı) tercih ediliyor. Çünkü performansı O(n ^ 2)'dir. Bu demek oluyor ki listedeki veri miktarı arttıkça çalışma süresi n ile doğru orantılı olarak artacaktır. Java 12'de Arrays sınıfının altında hazır gelen sort fonksiyonu, Vladimir Yaroslavskiy, Jon Bentley, ve Joshua Bloch'un uyguladığı (implement ettiği) Quicksort algoritmasını kullanır. Bu algoritmanın performansı ise O(n log(n)) dir. Bu algoritmayı büyük listelerde(örneğin 10 milyon kişinin puanı)  gönül rahatlığı ile kullanılabilir.

Kaynak


Kaynak
Elimizde 8 elemanlı bir dizi var. Şekilde de gördüğümüz üzere 2.elemandan başlıyoruz ve önceki elemanlar ile karşılaştırıp sayının yeni yerini belirliyoruz. Örneğin ilk aşamada 3 ile 4'ü karşılaştırdık ve 3 < 4 olduğundan yerlerini değiştirdik. 3. elemandan devam ediyoruz. Bakıyoruz ki 2 < 4 o halde karşılaştırmaya devam ediyoruz ve 2 < 3 olduğundan ve karşılaştıracak herhangi bir eleman kalmadığından 2'nin yeni yeri belirlenmiş oluyor. Algoritmamız çalışma mantığını kavradığımıza göre Java'da nasıl uygulayacağımıza bakalım. 
Kaynak

Burada T[] (Generic, neden kullanıldığını bilmiyorsanız buraya) dönüş tipi olan sort adında bir fonksiyon ve yardımcı fonksiyonların bulunduğun bir SortUtils sınıfımız mevcut. Burada dizimizi ekrana basacak print adında bir fonksiyon ve iki değeri karşılaştırıp sonucu boolean döndürecek less adlı bir fonksiyonumuz mevcut. Son olarak fonksiyonumuzun test edildiği main fonksiyonumuz var. Basit bir unit test yazmak daha iyi olacaktır. Sort fonksiyonunda parametre olarak alınan dizimizin boyutu kadar dönen bir for döngümüz var. Döngümüz 1'den başlıyor çünkü yukarıda belirttiğimiz gibi önceki sayılar ile kıyaslayacağız. Yani 1-0, 2-1-0, 3-2-1-0 diye devam edecek. Daha sonra bir key değeri belirliyoruz ve ikinci index'imizi içine atıyoruz(array[1]). Sonrasında bir i değeri belirliyoruz ve j değerimizin bir önceki değierini içine atıyoruz.(0 => array[0] için). i değerimizin 0>= olduğu ve key(array[1]) ile array[0] less fonksiyonuna parametre olarak yolladığımız bir while döngüsüne sokuyoruz. Eğer şart sağlanırsa yani 3<4 ise döngünün içindeki işlemler ile 4<=>3 yer değiştiriyor. Mantık bu şekilde devam ediyor. Herhangi bir sorunuz olursa yorum olarak belirtebilirsiniz. İyi çalışmalar.




Hiç yorum yok:

Yorum Gönder

Spring Boot Uygulamasını Heroku üzerinde Deploy Etme

Bu yazımızda sizlere spring boot ile yazılmış basit bir Rest api'nin heroku üzerinde nasıl deploy edebileceğimizi göstereceğim. Önce ...