Kaydırma

Sıralı bölümde doğru yeri bulana kadar elemanları sağa kaydırmayı öğrenirsin.

Tam insertion sort

Insertion sort'u tam uygulamak için dış döngü 1'den n-1'e kadar gider ve her eleman için kaydır-yerleştir yapar.

Her dış döngü adımında, sıralı bölüm bir eleman büyür ve yeni eleman doğru yerine yerleştirilir.

En iyi durum

Insertion sort'un en iyi durumu, dizi zaten sıralıysa O(n)'dir. Bu durumda iç while döngüsü hiç çalışmaz.

En kötü durum (ters sıralı dizi) O(n^2)'dir çünkü her eleman için tüm sıralı bölüm kaydırılır.

Uygulama Insertion sort

insertion_sort(arr) yaz. Her elemanı doğru yere yerleştir. print(insertion_sort([5, 2, 4, 6, 1, 3])) ile [1, 2, 3, 4, 5, 6] yazdır.

Örnek çözümü göster

def insertion_sort(arr):
    # Diziyi sırala
    for i in range(1, len(arr)):
        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_sort([5, 2, 4, 6, 1, 3]))

Kendini test et

İç döngü

Kaydırma için ____ döngüsü kullanılır.

Cevabı göster

Kaydırma için while döngüsü kullanılır.

Kaydırma: kavramları eşleştir

Dış döngü

1'den n-1'e
İç while

Kaydırır
En iyi

O(n)
En kötü

O(n^2)
Insertion sort en iyi durumda nedir?
- O(n)
- O(n log n)
- O(n^2)
- O(1)
Cevabı göster

O(n) — En iyi durum O(n)'dir.

Sıradaki ders: Yerleştirme

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler