7. Shell Sıralama (Shell Sort)

SHELL SORT’UN ÇALIŞMA MANTIĞI

Meta sort algoritması yani başka bir sort algoritması üzerinde çalışır. Bu başka sort algoritması genelde insertion sort olmak ile birlikte herhangi bir algoritma olabilir. Bu sebeple bu algoritmaya sort algoritması demektense başka sort algoritmalarının verimliliğini artıran bir algoritma demek de yanlış olmaz. İsmini algoritmayı bulan Donald Shell’den alır.

5, 7, 9, 3, 4, 6 , 8 , 10 , 11 , 1 ,0 , 2  dizisi olsun. Shell sortta ilk olarak gapler belirlenir. Aslında bu gap denen şey kaçarlı sütun oluşturacağınıza karar vermekten başka bir şey değildir. Bizim burda gap’imiz 4 olsun. Gaplerin belirlenmesiyle aşağıdaki sutün yapısı oluşturulur.

5 ,   7 ,  9 ,   3

4,    6 ,  8 ,  10

11 , 1 ,  0 ,   2

Daha sonra her sutün kendi arasında sıralanır. İşte bu sıralama işleminde herhangi başka bir sıralama algoritması kullanabilirsiniz.

5 ,    7 ,   9 ,    3                             4  ,      1  ,      0  ,     2

4,      6 ,   810        –>               ,       6 ,      8 ,     3

11  , 1 ,  0 ,                                11 ,      7      9 ,    10

Her sütun kendi arasında sıralandıktan sonra tekrar satırlar yanyana getirilerek dizi haline çevrilir.

4 , 1 , 0 , 2 , 5 , 6 , 8 ,3 , 11 , 7 , 9 , 10

Yukarıdaki aşama tekrar uygulanır. Ancak bu sefer gap bir önceki gap’in yarısı olur. Yani  4/2’den 2şerli sütunlar üzerinde işlem yaparız.

  4      1                     0         1
  0      2                     4         2
  5      6       –>         5         3
  8      3                     8         6
 11    7                      9         7
  9     10                   11       10 

Tekrar diziyi satırlar yanyana gelecek şekilde birleştiririz ve yeni bir dizi oluştururuz.

 0, 1, 4, 2 ,5, 3, 8, 6 ,9 ,7 ,11 , 10

Bu sefer üstteki aşamaları 1lik kolondan oluşan son dizi için yaparız ki bu da bizi sıralı diziye ulaştırır.

SHELL SORT’UN ALGORITMA ANALIZI

Best Case : Shell sort’ta dizi üzerinden her bir geçiş bizi best case’e daha çok yaklaştırır.
Worst Case : Herhangi bir avantaj sağlamaz

SHELL SORT’UN C# ile IMPLEMENTASYONU

 public static void Shellsort(List<double> arr)
 {
       int n = arr.Count;

      for (int gap = n / 2; gap > 0; gap /= 2)
      {
          for (int i = gap; i < n; i += 1)
          {
           double temp = arr[i];

            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
            arr[j] = arr[j - gap];

            arr[j] = temp;
           }
       }
    }