/dsa_kodluyoruz_proje123

Kodluyoruz: Proje1 / Proje2 / Proje3

Proje 1: Selection ve Insertion Sort

[22,27,16,2,18,6] --> Insertion sort için:
Big O gösterimi: O(n^2)
Time Complexity: Dizi sıralandıktan sonra 18 sayısı ortalama duruma girer, çünkü dizinin ortasında bulunur. Kötü durumda bulunmamasını düşünmemin nedeni 18 sayısının dizinin en sonuna yakın olsa bile en sonunda olmamasından kaynaklanmaktadır.

[7,3,5,8,2,9,4,15,6] dizisinin Selection Sort' a göre ilk 4 adımı nedir?

  1. arr[0] indexi dizideki en küçük ilk elemanı tutmak için sanal olarak rezerve edilir. Ardından dizideki en küçük eleman aranır ve bulunur. arr[0] indeximiz, arr[4] index numarasında bulunan 2 değeri ile yer değiştirir. Yeni dizi [2,3,5,8,7,9,4,15,6] oldu. Artık arr[0] indexi dizide sıralanmış olarak kabul edilir ve sonraki aramalardan etkilenmez.
  2. arr[1] indexi dizideki en küçük ikinci elemanı tutmak için sanal olarak rezerve edilir. Ardından dizideki sıralanmamış kısımdan en küçük değer aranır ve bulunur, bu durumda arr[1] yani 3 değeridir. Bu aşamada dizide herhangi bir değişiklik yapılmaz çünkü zaten arr[1] indexinde en küçük ikinci eleman tutulmaktadır. Artık dizinin ilk iki indexi sıralanmış kabul edilir ve sonraki aramalardan etkilenmez çünkü aramalar sıralanmamış kısımdan yapılacaktır. Güncel dizi: [2,3,5,8,7,9,4,15,6]
  3. arr[2] indexi tekrardan sıralanmamış dizideki min. değer için rezerve edilir. Sıralanmamış dizideki en küçük değer bulunur, bu durumda arr[6] yani 4 değeridir. Dizideki 5 ve 4 yani arr[2] ile arr[6] yer değiştirir. Güncel dizi: [2,3,4,8,7,9,5,15,6]
  4. arr[3] sıralanmamış diziden gelecek sonraki min. değer için sanal olarak rezerve edilir. Sıralanmamış dizideki en küçük değer aranır ve bulunur, bu durumda arr[6] indexi yani 5 değeridir. arr[3] indexinde ki 8 değeri ile arr[6] indexinde ki 5 değeri yer değiştirir. Güncel dizi [2,3,4,5,7,9,8,15,6] olur.

    İşte dizi üzerinde selection sort ile gerçekleşecek ilk 4 adım bu şekildedir.

Proje 2: Merge Sort

[16,21,11,8,12,22]
Dizinin Merge Sort' a göre aşamaları:

  • Dizi baştan sona (16,21), (11,8), (12,22) şeklinde ikişer olarak parçalara bölünür.
  • Daha sonra 16, 21, 11, 8, 12, 22 olarak tekli parçalara bölünür.
  • Dizinin her bir elemanı parçaladığımızın tersi şeklinde tekrar birleşir. Ancak birleşirken dizi elemanları arasında kıyaslama gerçekleşir ve birleşme bu kıyaslamaya dayalı olarak sıralanmış olarak gerçekleşir. Kıyaslama gerçekleşirken dizi küçük parçalardan büyük parçalara evrilir, bu sebeple de kıyaslama sorgusu daha verimli bir şekilde gerçekleşir.
  • Dizinin son hali: [8,11,12,16,21,22] olur.

    Dizinin Big O Gösterimi: worst case için (n log(n))' dir.

Proje 3: Binary Search Tree

[7, 5, 1, 8, 3, 6, 0, 9, 4, 2]

  • Verilen dizinin binary search tree aşamaları:
    1. root 7 olarak belirlenir
    2. 5 değeri root' un sol altına yerleşir
    3. 1 değeri 5' in sol altına yerleşir
    4. 8 değeri root' un sağ altına yerleşir
    5. 3 değeri 1' in sağ altına yerleşir
    6. 6 değeri 5' in sağ altına yerleşir
    7. 0 değeri 1' in sol altına yerleşir
    8. 9 değeri 8' in sağ altına yerleşir
    9. 4 değeri 3' ün sağ altına yerleşir
    10. 2 değeri 3' ün sol altına yerleşir

Diziyi binary search tree yapısına uygun hale getirilecek adımlar bunlardır.