Implementation (Part 2)
Coddy'nin Insertion Sort - DSA Serisi kursunda ders 6 / 9.
Senaryo: [5, 2, 9, 1, 5] Dizisini Sıralama
Adım 1: Başlangıç Durumu
- Orijinal Dizi: [5, 2, 9, 1, 5]
- Bunu elimizdeki kartlar (veya bir sayı dizisi) olarak hayal edin.
Adım 2: Birinci Eleman (i=1, key=2)
- İkinci kartla (elemanla) başlıyoruz: key = 2.
- 2'yi 5 (şu ana kadar sıralanmış tek eleman) ile karşılaştırın.
- 2 daha küçük olduğu için, 5'i sağa kaydırıyoruz ve 2'yi onun yerine yerleştiriyoruz.
- Güncellenmiş Dizi: [2, 5, 9, 1, 5]
Adım 3: İkinci Eleman (i=2, key=9)
- Bir sonraki karta geçin: key = 9.
- 9'u 5 ile karşılaştırın.
- 9 daha büyük olduğu için kaydırmaya gerek yok.
- Güncellenmiş Dizi: [2, 5, 9, 1, 5] (değişiklik yok)
Adım 4: Üçüncü Eleman (i=3, key=1)
- Bir sonraki karta geçin: key = 1.
- 1'i önce 9 ile, sonra 5 ile karşılaştırın.
- 9 ve 5'i sağa kaydırarak 1 için yer açın.
- Güncellenmiş Dizi: [1, 2, 5, 9, 5]
Adım 5: Dördüncü Eleman (i=4, key=5)
- Bir sonraki karta geçin: key = 5.
- 5'i 9 ile karşılaştırın.
- 5 daha küçük olduğu için kaydırmaya gerek yok.
- Güncellenmiş Dizi: [1, 2, 5, 9, 5] (değişiklik yok)
Adım 6: Beşinci Eleman (i=5, key=5)
- Son karta geçin: key = 5.
- 5'i 9 ile karşılaştırın.
- 5 daha küçük olduğu için kaydırmaya gerek yok.
- Güncellenmiş Dizi: [1, 2, 5, 5, 9]
Final Sonucu:
- Sıralanmış Dizi: [1, 2, 5, 5, 9]
Her adımda bir kart (eleman) seçiyoruz, onu sıralanmış olanlarla karşılaştırıyoruz ve gerekirse diğerlerini kaydırarak doğru yere yerleştiriyoruz. Tüm dizi sıralanana kadar bu işlemi tekrarlıyoruz.
Görev
KolayŞimdi, her bir öğe için sıralama işlemini gerçekleştiren iç döngüyü uygulayın.
Sıralama işlemini insertionSort fonksiyonu içinde tamamlayın.
Fonksiyon ayrıca sonunda dizinin öğelerini, aralarında yeni bir satır olacak şekilde tek tek yazdırmalıdır.
Önceki dersleri ve ipucunu referans olarak kullanın :)
Kendin dene
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
print(key)
Insertion Sort - DSA Serisi bölümündeki tüm dersler
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity