[22,27,16,2,18,6] -> Insertion Sort
- Yukarı verilen dizinin sort türüne göre aşamalarını yazınız.
- Big-O gösterimini yazınız.
- Time Complexity: Average case: Aradığımız sayının ortada olması,Worst case: Aradığımız sayının sonda olması, Best case: Aradığımız sayının dizinin en başında olması.
- Dizi sıralandıktan sonra 18 sayısı hangi case kapsamına girer? Yazınız.
[7,3,5,8,2,9,4,15,6] dizisinin Insertion Sort'a göre ilk 4 adımını yazınız.
Insertion Sort: En basit sorting algoritmasıdır. Basit olarak çalışma mantığı dizideki her bir elemanı aramak için iç içe iki döngüden yararlanan bir algoritma. İlk çalıştığında dizinin en küçük elemanı dizinin ilk elamanı ile yerini değişiyor. ikinci çalıştığında ikinci eleman ile ikin ci en küçük sayıyı buluyor, bu işlem n Elemanlı bir dizi için n sefer gerçekleşiyor.
dizi [ 22 , 27 , 16 , 2 , 18 , 6 ] (n)
Adım-01 ["2" , 27 , 16 , "22" , 18 , 6 ] (n-1)
Adım-02 [ 2 , "6" , 16 , 22 , 18 , "27" ] (n-2)
Adım-03 [ 2 , 6 , "16", 22 , 18 , 27 ] (n-3)
Adım-04 [ 2 , 6 , 16 , "18" , "22", 27 ] (n-4)
Adım-05 [ 2 , 6 , 16 , 18 , 22 , 27 ] (n-5)
----------------------------------------------------------
* Average case : Aradığımız sayının ortada olması
* Worst case : Aradığımız sayının sonda olması
* Best case : Aradığımız sayının dizinin en başında olması.
-
Dizimizin son hali
Dizimizin son hali= [ 2 , 6 , 16 , "18" , 22 , 27 ]
Aradığımız sayı dizinin ortasında bulunduğundan Average case kapsamına girmesine neden olur.
-
Dizisinin Insertion Sort'a göre ilk 4 adımını yazınız.
dizi [ 7 , 3 , 5 , 8 , 2 , 9 , 4 , 15 , 6 ] (n) Adım-01 [ "2" , 3 , 5 , 8 ,"7" , 9 , 4 , 15 , 6 ] (n-1) Adım-02 [ 2 , "3" , 5 , 8 , 7 , 9 , 4 , 15 , 6 ] (n-2) Adım-03 [ 2 , 3 , "4" , 8 , 7 , 9 ,"5", 15 , 6 ] (n-3) Adım-04 [ 2 , 3 , 4 ,"5", 7 , 9 ,"8", 15 , 6 ] (n-4)