Java ile Backend Web Development Patikası

Veri Yapıları ve Algoritmalar

Proje Ödevi -01

[22,27,16,2,18,6] -> Insertion Sort

1. Yukarı verilen dizinin sort türüne göre aşamalarını yazınız.
2. Big-O gösterimini yazınız.
3. 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ı.
4. 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.

---

Çözüm

[22,27,16,2,18,6] Insertion Sort türüne göre aşamaları

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)	
----------------------------------------------------------

Big-O gösterimini

$$ n*(n+1)/2 =(n ^ { 2 } + n)/2 => (Big-O= n ^ { 2 } ) $$

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ı.

Case kapsamı (18)

• 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.

[7,3,5,8,2,9,4,15,6] Insertion Sort

• 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)
  

License

MIT