Bu yazımızda kabuk sıralama algoritmasını tartışacağız. Kabuk sıralama, çeşitli konumlardaki boşluklarla ayrılmış öğeleri karşılaştırarak ekleme sıralamasının dezavantajlarının üstesinden gelen ekleme sıralamasının genelleştirilmesidir.

Eklemeli sıralamanın genişletilmiş versiyonu olan bir sıralama algoritmasıdır. Kabuk sıralaması, ekleme sıralamasının ortalama zaman karmaşıklığını iyileştirmiştir. Eklemeli sıralamaya benzer şekilde karşılaştırmaya dayalı ve yerinde sıralama algoritmasıdır. Kabuk sıralaması orta büyüklükteki veri kümeleri için etkilidir.

Eklemeli sıralamada, öğeler aynı anda yalnızca bir konum ileri taşınabilir. Bir öğeyi uzak bir konuma taşımak için algoritmanın yürütme süresini artıran birçok hareket gerekir. Ancak kabuk sıralaması, ekleme sıralamasının bu dezavantajının üstesinden gelir. Uzaktaki elemanların hareket etmesine ve değiştirilmesine de olanak tanır.

Bu algoritma öncelikle birbirinden uzak olan elemanları sıralıyor, daha sonra aralarındaki boşluğu azaltıyor. Bu boşluğa şu ad verilir: aralık. Bu aralık şu şekilde hesaplanabilir: Knuth'un aşağıda verilen formül -

dünyanın en iyi arabası

 h = h * 3 + 1 where, 'h' is the interval having initial value 1. 

Şimdi kabuk sıralama algoritmasını görelim.

Algoritma

Kabuk sıralamasını gerçekleştirmenin basit adımları aşağıda listelenmiştir:

komut dosyası kabuğunu çalıştır

 ShellSort(a, n) // &apos;a&apos; is the given array, &apos;n&apos; is the size of array for (interval = n/2; interval &gt; 0; interval /= 2) for ( i = interval; i <n; i +="1)" temp="a[i];" for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; a[j] = temp; End ShellSort </n;>

Kabuk sıralama algoritmasının çalışması

Şimdi kabuk sıralama algoritmasının çalışmasına bakalım.

Kabuk sıralama algoritmasının çalışmasını anlamak için sıralanmamış bir diziyi ele alalım. Bir örnek üzerinden kabuk sıralamasını anlamak daha kolay olacaktır.

Dizinin elemanları şöyle olsun:

Kabuk sıralamasının orijinal dizisini, yani aralık olarak N/2, N/4,....,1'i kullanacağız.

İlk döngüde n, 8'e eşittir (dizinin boyutu), dolayısıyla elemanlar 4 (n/2 = 4) aralığında yer alır. Öğeler sıralı değilse karşılaştırılacak ve değiştirilecektir.

Burada ilk döngüde 0'daki eleman^bukonum 4'teki elemanla karşılaştırılacaktır^bukonum. 0 ise^bueleman daha büyükse 4'teki elemanla değiştirilecektir^bukonum. Aksi takdirde aynı kalır. Geriye kalan unsurlar için bu süreç devam edecektir.

4 aralığında alt listeler şunlardır: {33, 12}, {31, 17}, {40, 25}, {8, 42}.

Şimdi her alt listedeki değerleri karşılaştırmamız gerekiyor. Karşılaştırmadan sonra, gerekirse orijinal dizide bunları değiştirmemiz gerekir. Karşılaştırma ve değiştirme işleminden sonra güncellenen dizi aşağıdaki gibi görünecektir:

İkinci döngüde elemanlar 2 (n/4 = 2) aralığında yer almaktadır, burada n = 8'dir.

dizeyi tam sayıya dönüştür

Şimdi aralığını alıyoruz 2 dizinin geri kalanını sıralamak için. 2 aralıkla iki alt liste oluşturulacaktır: {12, 25, 33, 40} ve {17, 8, 31, 42}.

Şimdi yine her alt listedeki değerleri karşılaştırmamız gerekiyor. Karşılaştırmadan sonra, gerekirse orijinal dizide bunları değiştirmemiz gerekir. Karşılaştırma ve değiştirme işleminden sonra güncellenen dizi aşağıdaki gibi görünecektir:

Java'da özyineleme

Üçüncü döngüde elemanlar 1 (n/8 = 1) aralığında yer alır, burada n = 8. Son olarak, dizi elemanlarının geri kalanını sıralamak için 1 değer aralığını kullanırız. Bu adımda kabuk sıralaması, dizi öğelerini sıralamak için ekleme sıralamasını kullanır.

Artık dizi artan düzende sıralanıyor.

Kabuk sıralama karmaşıklığı

Şimdi Shell sıralamasının zaman karmaşıklığını en iyi durum, ortalama durum ve en kötü durumda görelim. Ayrıca Shell sıralamasının uzay karmaşıklığını da göreceğiz.

1. Zaman Karmaşıklığı

En İyi Durum Karmaşıklığı -Sıralama gerekmediğinde oluşur, yani dizi zaten sıralanmıştır. Kabuk sıralamasının en iyi durum zaman karmaşıklığı şudur: O(n*logn). Ortalama Vaka Karmaşıklığı -Dizi öğeleri, düzgün şekilde artan ve düzgün şekilde alçalan olmayan, karışık bir düzende olduğunda ortaya çıkar. Kabuk sıralamasının ortalama vaka süresi karmaşıklığı O(n*logn). En Kötü Durum Karmaşıklığı -Dizi elemanlarının ters sırada sıralanması gerektiğinde ortaya çıkar. Bu, dizi elemanlarını artan sırada sıralamanız gerektiğini, ancak elemanlarının azalan sırada olduğunu varsayalım anlamına gelir. Shell sıralamasının en kötü durum zaman karmaşıklığı Açık²).

2. Uzayın Karmaşıklığı

• Kabuk sıralamasının uzay karmaşıklığı O(1)'dir.

Kabuk sıralamasının uygulanması

Şimdi farklı programlama dillerinde Shell sort programlarına bakalım.

Program: C dilinde Kabuk sıralamasını uygulayan bir program yazın.

 #include /* function to implement shellSort */ int shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval &gt; 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; // put temp (the original a[i]) in its correct position a[j] = temp; } } return 0; } void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 42 i++) printf('%d ', a[i]); } int main() { a[]="{" 33, 31, 40, 8, 12, 17, 25, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarr(a, n); shell(a, printf('
after applying shell sort, the return 0; < pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-7.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in C++.</p> <pre> #include using namespace std; /* function to implement shellSort */ int shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval &gt; 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; // put temp (the original a[i]) in its correct position a[j] = temp; } } return 0; } void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 41 i++) cout< <a[i]<<' '; } int main() { a[]="{" 32, 30, 39, 7, 11, 16, 24, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarr(a, n); shell(a, cout<<'
after applying shell sort, the return 0; < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-8.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in C#.</p> <pre> using System; class ShellSort { /* function to implement shellSort */ static void shell(int[] a, int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval &gt; 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; /* put temp (the original a[i]) in its correct position */ a[j] = temp; } } } static void printArr(int[] a, int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 40 i++) console.write(a[i] + ' '); } static void main() { int[] a="{" 31, 29, 38, 6, 10, 15, 23, }; int n="a.Length;" console.write('before sorting array elements are - 
'); printarr(a, n); shell(a, console.write('
after applying shell sort, the < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-9.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in Java.</p> <pre> class ShellSort { /* function to implement shellSort */ static void shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval &gt; 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; /* put temp (the original a[i]) in its correct position */ a[j] = temp; } } } static void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 39 i++) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{" 30, 28, 37, 5, 9, 14, 22, }; n="a.length;" system.out.print('before sorting array elements are - 
'); printarr(a, n); shell(a, system.out.print('
after applying shell sort, the < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-10.webp" alt="Shell Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>