Struktur Data dan Algoritma - Shell Sort

Jenis shell adalah algoritma pengurutan yang sangat efisien dan didasarkan pada algoritma pengurutan penyisipan. Algoritme ini menghindari pergeseran besar seperti pada kasus penyisipan, jika nilai yang lebih kecil berada di paling kanan dan harus dipindahkan ke paling kiri.

Algoritme ini menggunakan semacam penyisipan pada elemen yang tersebar luas, pertama untuk mengurutkannya lalu mengurutkan elemen yang berjarak kurang luas. Jarak ini disebut sebagaiinterval. Interval ini dihitung berdasarkan rumus Knuth sebagai -

Formula Knuth

h = h * 3 + 1
where −
   h is interval with initial value 1

Algoritme ini cukup efisien untuk kumpulan data berukuran sedang karena rata-rata dan kompleksitas kasus terburuk dari algoritme ini bergantung pada urutan celah yang paling dikenal adalah Ο (n), di mana n adalah jumlah item. Dan kompleksitas ruang kasus terburuk adalah O (n).

Bagaimana Shell Sort Bekerja?

Mari kita pertimbangkan contoh berikut untuk mendapatkan gambaran tentang cara kerja shell sort. Kami mengambil larik yang sama yang telah kami gunakan dalam contoh kami sebelumnya. Untuk contoh dan kemudahan pemahaman kami, kami mengambil interval 4. Buat sub-daftar virtual semua nilai yang terletak pada interval 4 posisi. Berikut nilai-nilai tersebut adalah {35, 14}, {33, 19}, {42, 27} dan {10, 44}

Kami membandingkan nilai di setiap sub-daftar dan menukarnya (jika perlu) dalam larik asli. Setelah langkah ini, array baru akan terlihat seperti ini -

Kemudian, kami mengambil interval 1 dan celah ini menghasilkan dua sub-daftar - {14, 27, 35, 42}, {19, 10, 33, 44}

Kami membandingkan dan menukar nilai, jika diperlukan, dalam larik asli. Setelah langkah ini, array akan terlihat seperti ini -

Terakhir, kita mengurutkan sisa array menggunakan interval nilai 1. Jenis shell menggunakan jenis penyisipan untuk mengurutkan array.

Berikut ini adalah penggambaran langkah demi langkah -

Kami melihat bahwa itu hanya membutuhkan empat swap untuk mengurutkan sisa array.

Algoritma

Berikut algoritma untuk shell sort.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

Pseudocode

Berikut adalah pseudocode untuk shell sort.

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

Untuk mengetahui tentang implementasi shell sort dalam bahasa pemrograman C, silakan klik di sini .