Shell Sıralaması
Sıralama O(n log² n) O(1)Küçülen aralıklarla eklemeli sıralama: uzak elemanlar önce hareket eder, böylece son geçişte az iş kalır.
23
7
41
15
3
34
9
28
8 eleman üzerinde Shell Sort başlıyor.
Değişmez1 aralıklı her zincir sıralı. Küçük boşluklar bu işi devralır, bu yüzden son turda yapacak iş az kalır.
1/47
karşılaştırma0hareket0gap0i0j0key0
shell-sort.c
void shellSort(int arr[], int n) {for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int key = arr[i];int j = i;while (j >= gap && arr[j - gap] > key) {arr[j] = arr[j - gap];j -= gap;}arr[j] = key;}}}
Shell Sıralaması nasıl çalışır?
Aralarında gap kadar mesafe olan elemanlara eklemeli sıralama uygula, sonra gap'i küçült. Uzak elemanlar erken aşamada son yerlerine yaklaşır; son gap-1 geçişi neredeyse sıralı bir dizi bulur.
En iyi durum
Zaten sıralı — her gap geçişi yalnızca doğrular: yaklaşık O(n log n).
En kötü durum
Gap dizisine bağlı; n/2ᵏ gap'lerle O(n²)'ye düşer.
Ne zaman kullanılır?
Özyineleme ve ek bellek olmadan düz eklemeli sıralamayı geçen basit yerinde sıralama.