Insertion Sort Worst Case
Insertion Sort'un en kötü durum analizini (worst case scenario) yapacak olursak, tersten sıralı bir dizi örneği verebiliriz.
Bu durumda her işlemde kaydırma işlemi yapılmak zorunda kalınacaktır. yani;
(n-1) + (n-2) + (n-3) + ... + 2 + 1
işlemi hesaplayacak olursak n*(n+1) / 2 gelecektir. yani (n^2+1) / 2 sonucu karşımıza çıkar.
Bu ifadenin Büyük O notasyonu O(n^2) 'dir.
Yani Insertion Sort Worst Case değeri O(n^2) ile ifade edilebilir.
Insertion Sort Best Case
Insertion Sort algoritması n^2'den daha az zaman alabilir mi diye sorarsanız evet diyebiliriz. Çünkü dizi eğer sıralı ise sadece geçiş işlemleri gerçekleşir. Geçiş işlemleri ise eleman sayısı kadar olacağından toplamda n adet geçiş oluşur. böylece;
Insertion Sort Best Case O(n) durumundadır.
Insertion Sort Avarage Case
Insertion Sort'un ortalama durumu O(n^2) ile ifade edilmektedir, ancak genel olarak Selection Sort ve Bubble Sort'a göre çok daha hızlıdır. Ve genel olarak tercih edilir.
Bu algoritma ek veri alanı ihtiyacı duymaz.
Etiketler: Insertion Sort Worst Case, insertion sort, insertion sort best case
