Eklemeli Sıralama

Sıralama O(n²) O(1)

Sıralı öneki her seferinde bir eleman büyütür; yeni eleman yerine oturana dek büyük değerleri sağa kaydırır.

Boşta

8 eleman üzerinde Insertion Sort başlıyor.

DeğişmezA[0..1-1] sıralı. Anahtar elde tutulduğu için dizideki boşluk kaybolmuş bir değer değil.

1/49

karşılaştırma0hareket0i0j0key0

karşılaştırtakaskaydırseçsıralı

insertion-sort.c

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Eklemeli Sıralama nasıl çalışır?

Sol kısmı sıralı tut. Sıradaki elemanı al, ondan büyük her şeyi bir sağa kaydır ve boşluğa bırak — eldeki iskambil kartlarını sıralamak gibi.

En iyi durum

Zaten (veya neredeyse) sıralı — her eleman en fazla bir adım kayar: O(n).

En kötü durum

Ters sıralı — her eleman en sola kadar yürür: O(n²).

Ne zaman kullanılır?

Küçük veya neredeyse sıralı diziler; Timsort gibi hibrit sıralamaların bitirme geçişi.