Yerleştirme
- Algoritmalar kursu
- Başlangıç
- Ders 31/80
- 4 dk
Boşalan yere elemanı koymayı ve tüm diziyi sıralamayı öğrenirsin.
Insertion sort avantajları
Insertion sort, küçük veya neredeyse sıralı dizilerde çok verimlidir. En iyi durum O(n) olduğundan, neredeyse sıralı dizilerde hızlıdır.
Ayrıca yerinde sıralar: ek bellek gerektirmez. Bu, bellek kısıtlı sistemlerde avantajlıdır.
Karmaşıklık karşılaştırma
Insertion sort, bubble sort ve selection sort ile aynı O(n^2) karmaşıklığa sahiptir ama pratikte daha hızlıdır çünkü daha az yazma işlemi yapar.
Neredeyse sıralı dizilerde insertion sort O(n) iken, bubble sort ve selection sort hala O(n^2) çalışır.
Uygulama Insertion adımı
insertion_step(arr, i) yaz. i. elemanı sıralı bölüme kaydırarak yerleştir. print(insertion_step([2, 4, 6, 3], 3)) ile [2, 3, 4, 6] yazdır.
Başlangıç kodu
def insertion_step(arr, i):
# Bir adım yapÖrnek çözüm
def insertion_step(arr, i):
# Bir adım yap
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
return arr
print(insertion_step([2, 4, 6, 3], 3))Beklenen çıktı
[2, 3, 4, 6]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Yerleştirme: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Insertion sort |
Neredeyse sıralı |
En iyi |
O(n) |
Yerinde |
Ek bellek yok |
Az yazma |
Hızlı pratik |
2 Insertion sort hangi dizilerde en hızlıdır?
- Ters sıralı
- Rastgele
- Neredeyse sıralı Doğru cevap
- Çok büyük
Açıklama: Neredeyse sıralı dizilerde en hızlıdır.
3 Yerinde sıralama
Insertion sort ____ ek bellek gerektirir.Insertion sort az ek bellek gerektirir.Açıklama: az doğru.