ÖRNEK ile Kabuk Sıralama Algoritması

Kabuk Sıralaması Nedir?

Shell'in yöntemi veya Veri yapısındaki Shell sıralaması, etkili bir yerinde karşılaştırma sıralama algoritmasıdır. Adını 1959'da ilk fikri ortaya atan Donald Shell'den almıştır. Kabuk sıralaması, ekleme sıralama algoritmasının genelleştirilmiş bir uzantısıdır.

Bu sıralama algoritmasının temel fikri, birbirinden uzaktaki öğeleri gruplamak ve buna göre sıralamaktır. Daha sonra aralarındaki boşluğu kademeli olarak azaltır. Kabuk sıralaması, uzaktaki öğeleri karşılaştırarak ve değiştirerek ekleme sıralamasının ortalama durum zamanı karmaşıklığının üstesinden gelir.

Aralık olarak bilinen bu boşluk, bazı optimal aralık dizilerine göre azaltılır. Kabuk sıralamasının çalışma süresi de bu dizilere bağlıdır. Shell'in orijinal dizisi, Knuth formülü, Hibbard'ın artışları vb. gibi çeşitli boşluk dizileri vardır. Shell'in orijinal boşluk dizisi şu şekildedir: n/2, n/4, n/8, ……….1

Kabuk Sıralama Algoritması

Kabuk sıralama algoritmasının adımları veya prosedürü aşağıdaki gibidir:

) 1 Adım Aralık değerini sıfırlayın, h = n/2. (Bu örnekte n, dizinin boyutudur)

) 2 Adım h aralığı içindeki tüm elemanları bir alt listeye yerleştirin.

) 3 Adım Bu alt listeleri ekleme sıralamasını kullanarak sıralayın.

) 4 Adım Yeni aralığı ayarlayın, h=h/2.

) 5 Adım Eğer h>0 ise 2. adıma gidin. Aksi takdirde 6. adıma gidin.

) 6 Adım Ortaya çıkan çıktı sıralanmış dizi olacaktır.

Kabuk Sıralaması Nasıl Çalışır?

Eklemeli sıralamada öğeler aynı anda yalnızca bir konuma taşınır. Bunun aksine, kabuk sıralaması, diziyi aralık değerine göre daha küçük parçalara böler ve bu parçalar üzerinde ekleme sıralaması gerçekleştirir.

Yavaş yavaş aralık değeri azalır ve bölünen parçaların boyutu artar. Parçalar önceden ayrı ayrı sıralandığından bu parçaları birleştirmek, birleştirme işleminden daha az adım gerektirir. ekleme türü.

Aşağıdaki GIF, kabuk sıralamasının bir gösterimini gösterir. Bu demoda, kırmızı ve mavi gösterilen değer, ekleme sıralamasına göre karşılaştırılır ve değiştirilir. Daha sonra aralık azalır ve kabuk sıralaması, neredeyse sıralanmış verilerde ekleme sıralamasını başlatır.

Kabuk Sıralama Algoritmasının Çalışması

Bir kabuk sıralama algoritmasının aşağıdaki örneğine bakalım. Bu örnekte, aşağıdaki diziyi kabuk sıralamasını kullanarak sıralayacağız:

) 1 Adım Burada dizi boyutu 8'dir. Dolayısıyla aralık değeri h = 8/2 veya 4 olacaktır.

) 2 Adım Şimdi tüm elemanları 4 mesafede saklayacağız. Bizim durumumuz için alt listeler- {8, 1}, {6, 4}, {7, 5}, {2, 3}.

) 3 Adım Artık bu alt listeler, her iki sayıyı karşılaştırmak ve buna göre sıralamak için geçici bir değişkenin kullanıldığı ekleme sıralaması kullanılarak sıralanacak.

Takas işlemlerinden sonra dizi aşağıdaki gibi olacaktır:

) 4 Adım Şimdi aralığın başlangıç ​​değerini azaltacağız. Yeni aralık h=h/2 veya 4/2 veya 2 olacaktır.

) 5 Adım 2>0 olarak tüm elemanları 2 mesafeye depolamak için 2. adıma gideceğiz. Bu seferlik alt listeler-

{1, 5, 8, 7}, {4, 2, 6, 3}

Daha sonra bu alt listeler ekleme sıralaması kullanılarak sıralanacaktır. İlk alt listeyi karşılaştırıp değiştirdikten sonra dizi aşağıdaki gibi olacaktır.

İkinci alt listeyi sıraladıktan sonra orijinal dizi şöyle olacaktır:

Daha sonra aralık yine azalacaktır. Şimdi aralık h=h/2 veya 2/1 veya 1 olacaktır. Bu nedenle, değiştirilen diziyi sıralamak için ekleme sıralama algoritmasını kullanacağız.

Aşağıda ekleme sıralamasının adım adım prosedürel tasviri yer almaktadır.

Aralık yine 2'ye bölünür. Bu sırada aralık 0 olur. Böylece 6. adıma geçiyoruz.

) 6 Adım Aralık 0 olduğundan dizi bu zamana göre sıralanır. Sıralanan dizi-

sözde kod

Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
    for (i = interval; i & lt; n; i += 1)
        temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
    a[j] = a[j - interval];
a[j] = temp;
End

C/'de Kabuk Sıralama ProgramıC++

Giriş:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Çıktı:

Sorted Output:

1 2 3 4 5 6 7 8

Kabuk Sıralama Örneği Python

Giriş:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Çıktı:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Kabuk Sıralama Uygulamaları

Kabuk Sıralamanın önemli uygulamaları şunlardır:

• Kabuk sıralaması kullanılır Linux çekirdeği çünkü çağrı yığını kullanmaz.
• uClibc kütüphanesi Kabuk sıralamasını kullanır.
• bzip2 kompresörü özyinelemeyi aşmayı durdurmak için Kabuk sıralamasını kullanır.

Kabuk Sıralamanın Avantajları ve Dezavantajları

Avantajlar	Dezavantajlar
Yığın çağrısına gerek yoktur.	Büyük dizi boyutları için verimli değildir.
Kolay uygulama.	Geniş alana yayılmış elemanlar için verimsiz.
Daha az geniş aralıklı elemanlar için verimlidir.

Kabuk Sıralama Karmaşıklık Analizi

Kabuk Sıralamasının Zaman Karmaşıklığı

Kabuk sıralama algoritmasının zaman karmaşıklığı O(n^2)'dir. Mantık şu şekildedir:

En iyi durum senaryosu için, dizinin daha önce düzenlendiği tüm aralıklar için toplam test miktarı log n'e eşit olacaktır. Bu nedenle karmaşıklık O(n*log n) olacaktır.

En kötü senaryo için dizinin, elemanların en yüksek sayıda karşılaştırmayı gerektireceği şekilde oluştuğunu düşünelim. Daha sonra tüm öğeler son yinelemeye kadar karşılaştırılmayacak ve değiştirilmeyecektir. Bu nedenle son artış için gereken toplam karşılaştırmalar O(n^2)'dir.

Sonuç olarak, zaman karmaşıklıkları şunlar olacaktır:

1. En iyi durum karmaşıklığı: O(n*log n)
2. Ortalama durum karmaşıklığı: O(n*log n)
3. En kötü durum karmaşıklığı: O(n^2)

Kabuk sıralamasının çalışma zamanı karmaşıklığı büyük ölçüde kullanılan boşluk artış dizilerine bağlıdır. Ancak, kabuk sıralaması için en iyi artış dizisi hala bilinmemektedir.

Kabuk Sıralama Alanı Karmaşıklığı

Bu karşılaştırma sıralamasında, herhangi bir ek yardımcı alana ihtiyacımız yoktur. Bu nedenle, bu tür algoritmaların alan karmaşıklığı O(1)'dir.