Shell Sort

#Nasıl çalışır?

Shell sort, eklemeli sıralamanın geliştirilmiş halidir. Eklemeli sıralama elemanları yalnızca birer adım kaydırabildiği için uzaktaki bir elemanı yerine getirmesi uzun sürer.

Shell sort önce birbirinden uzak (örneğin n/2 aralıklı) elemanları karşılaştırıp yer değiştirir. Küçük elemanlar böylece dizinin başına doğru büyük adımlarla atlar. Aralık her turda küçülür ve sonunda 1 olur.

Son tur sıradan bir eklemeli sıralamadır, ama dizi o noktada neredeyse sıralı olduğu için çok hızlı biter.

#Canlı animasyon

gap = n / 2
while gap > 0:
  for i = gap to n - 1:
    j = i; while j >= gap and a[j - gap] > a[j]:
      swap(a[j], a[j - gap]); j = j - gap
  gap = gap / 2

#Adım adım

1. 01Aralığı (gap) n/2 olarak başlat.
2. 02Birbirinden gap uzaktaki elemanlarla eklemeli sıralama yap.
3. 03Aralığı yarıya indir.
4. 04Aralık 1 olana kadar tekrarla.
5. 05Son tur (gap = 1) diziyi tamamen sıralar.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def shell_sort(a: list[int]) -> None:
    """Insertion sort on elements `gap` apart, with the gap halving down to 1."""
    gap = len(a) // 2
    while gap > 0:
        for i in range(gap, len(a)):
            key, j = a[i], i
            while j >= gap and a[j - gap] > key:
                a[j] = a[j - gap]
                j -= gap
            a[j] = key
        gap //= 2


numbers = [5, 1, 4, 2, 8, 3]
shell_sort(numbers)
print(*numbers)

#Karmaşıklık

Karmaşıklık seçilen aralık dizisine bağlıdır. Basit n/2, n/4, … dizisinde en kötü durum O(n²)'dir; Knuth ya da Ciura gibi daha iyi aralık dizileriyle O(n^1.5) ve altına iner. Kesin ortalama analizi hâlâ açık bir problemdir.

#Ne zaman kullanılır?

Kodu kısa, ek bellek istemeyen ve orta büyüklükteki dizilerde eklemeli sıralamadan çok daha hızlı bir algoritma gerektiğinde kullanılır. Gömülü sistemlerde ve bazı standart kütüphanelerin küçük dizi durumlarında tercih edilir.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.