Insertion Sort Eklemeli Sıralama
Sıralama Algoritmalarında son anlatıcağım hatta anlatmaya çalışacağım ders Insertion Sort..
İngilizce Adı Insertion Sort
Ortalama O(n + d)
En kötü O(n²)
Bellek O(1)
Kararlı mı? Evet
Yöntem Karşılaştırma ile Ekleme
Her zamanki gibi Video ile Başlıyoruz..
Şimdi Nedir Bu Insertion Sort.. Sıralanacak eleman kümesinden ikinci eleman alınır ve birinci elemanla karsılastırılır.kucukse yerdegistirir.. bir sonraki iterasyonda üçüncü elemanı alır ve onceki elemanlarla teker teker kontrol eder.iterasyon dizi boyutu kadar devam eder.
Yani Grafik olarak..
Animasyon olarak…
Java Kodumuz…
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Random;
public class INSERTION_SORT {
private static int[] arr;
private static BufferedReader read;
private static Random randomGenerator;
private static int size;
private static int random;
private static void printArray() {
for(int i=0; i<size; i++) {
System.out.println(“a[” + i + “] = ” + arr[i]);
}
}
static void insertionSort() {
int i, j, mv;
for(i = 1; i < arr.length; i++) {
mv = arr[i];
j =i;
while(j > 0 && arr[j-1] > mv) {
arr[j] = arr[j-1];
j–;
}
arr[j] = mv;
}
}
public static void main(String[] args) {
read = new BufferedReader(new InputStreamReader(System.in));
randomGenerator = new Random();
try
{
System.out.print(“Please enter array size : “);
size = Integer.parseInt(read.readLine());
System.out.print(“Please enter the random range : “);
random = Integer.parseInt(read.readLine());
// create array
arr = new int[size];
// fill array
for(int i=0; i<size; i++) {
arr[i] = randomGenerator.nextInt(random);
}
//printArray();
// runtime timer
long start = System.currentTimeMillis();
System.out.println(“Starting : ” + start);
insertionSort();
// runtime timer
System.out.println(System.currentTimeMillis() – start + ” millisecond.”);
//printArray();
}
catch(Exception ex)
{
ex.printStackTrace();
}
}
}
