Yerleştirme

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.

Örnek çözümü göster

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

Kendini test et

Yerleştirme: kavramları eşleştir

Insertion sort

Neredeyse sıralı
En iyi

O(n)
Yerinde

Ek bellek yok
Az yazma

Hızlı pratik
Insertion sort hangi dizilerde en hızlıdır?
- Ters sıralı
- Rastgele
- Neredeyse sıralı
- Çok büyük
Cevabı göster

Neredeyse sıralı — Neredeyse sıralı dizilerde en hızlıdır.

Yerinde sıralama

Insertion sort ____ ek bellek gerektirir.

Cevabı göster

Insertion sort az ek bellek gerektirir.

Sıradaki ders: Özet - Insertion sort

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler