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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)); | |
} | |
} |
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