Algoritma - Shell Sort

Shell sort, algoritma ini biasa disebut algoritma pertambahan menurun, ditemukan oleh Donald Shell tahun 1959. Prinsipnya adalah penyortiran yang sangat efisien berdasarkan perbaikan terhadap metode insertion sort dengan menghindari pergeseran besar seperti dalam kasus penyisipan, jika nilai yang lebih kecil ke paling kanan dan harus dipindahkan ke paling kiri.

Dalam semacam penyisipan kadang-kadang kita sangat perlu dalam menggeser blok besar untuk memasukkan item di lokasi yang benar. Dengan menggunakan semacam shell, kita dapat menghindari sejumlah besar pergeseran. Penyortiran dilakukan dengan interval tertentu. Setelah setiap lulus, interval dikurangi untuk membuat interval yang lebih kecil. Metode ini juga mengurutkan data dengan cara membandingkan suatu data lain yang punya jarak tertentu selanjutnya yang menghasilkan kompleksitas run time dari O (n log2 n)selanjutnya membentuk sebuah sub-list, kemudian dilakukan pertukaran apabila diperlukan.

Algoritma Sorting semacam ini efektif: - Untuk data set kecil - Untuk data yang hampir disortir

Algoritma Sorting tidak efisien saat: - Elemen harus bergerak jauh dalam susunan

Kompleksitas Teknik Sortir Shell

Kompleksitas waktu atau Time Complexity: O (n log n) untuk kasus terbaik, dan untuk kasus lain, itu tergantung pada urutan jeda. Kompleksitas Ruang atau Space Complexity: O (1)

Ide dari Shellsort adalah sebagai berikut:

  • Mengatur urutan data dalam array dua dimensi
  • Mengurutkan kolom dari array

Efeknya adalah urutan data disortir sebagian. Proses di atas diulang, tetapi setiap kali dengan array yang lebih sempit, yaitu dengan jumlah kolom yang lebih sedikit. Pada langkah terakhir, array hanya terdiri dari satu kolom. Di setiap langkah, urutan urutannya ditingkatkan, sampai pada langkah terakhir itu benar-benar disortir. Namun, jumlah operasi penyortiran yang diperlukan dalam setiap langkah terbatas, karena presortisasi urutan yang diperoleh dalam langkah-langkah sebelumnya

Disini akan kita perlihatkan contoh algoritma ini, gambar dibawah menunjukkan ‘shell sort’ yang dijalankan pada array integer, kotak berwarna merah adalah nilai saat ini yang kita pegang.

box1

box2

box3

Misalnya terdapat data bilangan 35,4,8,12,1, maka diterjemahkan posisi 0 adalah angka 35 sampai dengan posisi 4 adalah angka 1. Shell short dimulai pada jarak tengah jumlah deret bilangan, artinya jumlah bilangan dibagi 2, dalam kasus ini N/2 = 52 dianggap 8. Kemudian jarak yang diambil misalnya 2 jarak dari angka 35 adalah 8, yaitu dari posisi 0 ke posisi 2. Shell sort selalu membandingkan angka di posisi dengan jarak-jarak tersebut dalam hal ini berjarak 2, dengan hitungan mundur.

Implementasi Sebenarnya, urutan data tidak diatur dalam array dua dimensi, tetapi diadakan dalam array satu dimensi yang diindeks dengan tepat. Algoritma menggunakan urutan kenaikan untuk menentukan seberapa jauh elemen yang akan disortir adalah:

  • Langkah 1 - Inisialisasi nilai h
  • Langkah 2 - Bagilah list menjadi sub-list yang lebih kecil dari interval yang sama h
  • Langkah 3 - Urutkan sub-list ini menggunakan penyisipan
  • Langkah 3 - Ulangi sampai list lengkap disortir

Adapun pseudocode-nya bisa dilihat prosesnya:


procedure shellSort()
   A : array of items

   / * menghitung 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:

      / * pilih nilai yang akan dimasukkan * /
      valueToInsert = A[outer]
      inner = outer;

         /* Geser elemen ke kanan*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /*masukkan nomor pada posisi lubang */
      A[inner] = valueToInsert

      end for

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

   end while

end procedure