AlgoPit

Shell Sort Algoritması

Shell Sort, Insertion Sort'un geliştirilmiş bir versiyonudur. Donald Shell tarafından 1959'da geliştirilen bu algoritma, elemanları belirli aralıklarla (gap) karşılaştırarak sıralama işlemini optimize eder. Gap değeri her iterasyonda azaltılarak son aşamada normal insertion sort uygulanır.

Avantajlar

  • Insertion Sort'tan önemli ölçüde daha hızlıdır
  • In-place sıralama algoritmasıdır (O(1) alan karmaşıklığı)
  • Adaptive algoritma - kısmen sıralı dizilerde daha hızlı çalışır
  • Küçük ve orta boyutlu diziler için oldukça verimlidir
  • Kararlı olmasa da pratik uygulamalarda iyi performans gösterir

Dezavantajlar

  • En kötü durum karmaşıklığı O(n²)'dir
  • Kararlı bir sıralama algoritması değildir
  • Gap dizisinin seçimi performansı önemli ölçüde etkiler
  • Büyük veri setlerinde Quick Sort veya Merge Sort kadar verimli değildir
  • Teorik analizi karmaşıktır

İnteraktif Demo

Shell Sort Algoritması

Dizinizdeki sayıları Shell Sort algoritması ile sıralayın ve algoritmanın nasıl çalıştığını görün.

Sonuç yok

Kod Örnekleri

Shell Sort - TypeScript
1function shellSort(arr: number[]): number[] {
2  const result = [...arr];
3  const n = result.length;
4  
5  // Gap değerini n/2'den başlayarak her iterasyonda yarıya böl
6  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
7    // Gap kadar ayrı olan elemanları insertion sort ile sırala
8    for (let i = gap; i < n; i++) {
9      const temp = result[i];
10      let j = i;
11      
12      // Gap aralığında insertion sort uygula
13      while (j >= gap && result[j - gap] > temp) {
14        result[j] = result[j - gap];
15        j -= gap;
16      }
17      result[j] = temp;
18    }
19  }
20  
21  return result;
22}
23
24// Kullanım örneği
25const array = [64, 34, 25, 12, 22, 11, 90];
26console.log(shellSort(array)); // [11, 12, 22, 25, 34, 64, 90]

Algoritma Nasıl Çalışır?

Shell Sort algoritması, insertion sort'un performansını artırmak için gap (aralık) kavramını kullanır. Algoritma şu adımlarla çalışır:

1. Gap Değerinin Belirlenmesi

İlk gap değeri genellikle dizi uzunluğunun yarısı olarak belirlenir. Her iterasyonda bu değer yarıya bölünür ve gap 1 olana kadar devam edilir.

2. Gap Aralığında Sıralama

Her gap değeri için, gap kadar ayrı olan elemanlar insertion sort algoritması ile sıralanır. Bu, uzak elemanların hızlı bir şekilde doğru konumlarına yakın yerleştirilmesini sağlar.

3. Gap Azaltılması

Gap değeri her iterasyonda azaltılır. En yaygın kullanılan gap dizisi şudur: n/2, n/4, n/8, ..., 1. Son iterasyonda gap=1 olduğunda, algoritma normal insertion sort haline gelir.

4. Performans Avantajı

Shell Sort'un ana avantajı, büyük elemanları başlangıçta hızlı bir şekilde doğru konumlarına yakın yerleştirmesidir. Bu, son aşamada yapılan insertion sort'un çok daha az iş yapmasını sağlar.