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. 
package Sorts;
import static Sorts.SortUtils.less;
import static Sorts.SortUtils.print;
/**
* @author Varun Upadhyay (https://github.com/varunu28)
* @author Podshivalov Nikita (https://github.com/nikitap492)
*/
class InsertionSort implements SortAlgorithm {
/**
* This method implements the Generic Insertion Sort
* Sorts the array in increasing order
*
* @param array The array to be sorted
**/
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
for (int j = 1; j < array.length; j++) {
// Picking up the key(Card)
T key = array[j];
int i = j - 1;
while (i >= 0 && less(key, array[i])) {
array[i + 1] = array[i];
i--;
}
// Placing the key (Card) at its correct position in the sorted subarray
array[i + 1] = key;
}
return array;
}
// Driver Program
public static void main(String[] args) {
// Integer Input
Integer[] integers = {4, 23, 6, 78, 1, 54, 231, 9, 12};
InsertionSort sort = new InsertionSort();
sort.sort(integers);
// Output => 1 4 6 9 12 23 54 78 231
print(integers);
// String Input
String[] strings = {"c", "a", "e", "b", "d"};
sort.sort(strings);
//Output => a b c d e
print(strings);
}
}
package Sorts;
import java.util.Arrays;
import java.util.List;
/**
* The class contains util methods
*
* @author Podshivalov Nikita (https://github.com/nikitap492)
**/
final class SortUtils {
/**
* This method checks if first element is less then the other element
*
* @param v first element
* @param w second element
* @return true if the first element is less then the second element
*/
static <T extends Comparable<T>> boolean less(T v, T w) {
return v.compareTo(w) < 0;
}
/**
* Prints an array
*
* @param toPrint - the array which should be printed
*/
static void print(Object[] toPrint) {
System.out.println(Arrays.toString(toPrint));
}
}
view raw SortUtils.java hosted with ❤ by GitHub
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 ...