Shell Sort Algoritma Pengurutan dengan Jarak Incremental

Shell Sort: Algoritma Pengurutan dengan Jarak Incremental

Shell Sort, seringkali disebut juga dengan istilah diminishing increment sort, adalah algoritma pengurutan yang merupakan generalisasi dari algoritma insertion sort. Keunggulan utama Shell Sort terletak pada kemampuannya untuk mengurutkan elemen-elemen data yang terletak jauh satu sama lain, sesuatu yang sulit dilakukan oleh insertion sort secara efisien pada data berukuran besar. Inilah yang membuat Shell Sort menjadi pilihan menarik dibandingkan insertion sort standar, terutama ketika berhadapan dengan array yang sebagian besar belum terurut.

Prinsip Dasar: Jarak Incremental

Inti dari Shell Sort terletak pada konsep gap atau jarak incremental. Algoritma ini tidak langsung membandingkan elemen yang berdekatan seperti insertion sort. Sebaliknya, ia membagi array menjadi sub-list yang lebih kecil berdasarkan jarak incremental tertentu (misalnya, jarak 5 elemen). Setiap sub-list ini kemudian diurutkan menggunakan insertion sort.

Setelah sub-list dengan jarak yang lebih besar diurutkan, jarak incremental diperkecil (misalnya, menjadi 2). Proses pengurutan sub-list dengan insertion sort diulang dengan jarak incremental yang baru. Pengurangan jarak incremental ini terus dilakukan sampai akhirnya jarak incremental menjadi 1, yang berarti seluruh array diurutkan dengan insertion sort standar.

Kunci keberhasilan Shell Sort adalah pemilihan urutan jarak incremental yang tepat. Pemilihan urutan yang buruk dapat mengakibatkan kinerja yang buruk pula, bahkan dalam beberapa kasus bisa seburuk insertion sort biasa.

Algoritma Shell Sort: Langkah demi Langkah

Berikut adalah langkah-langkah umum dalam algoritma Shell Sort:

1. Tentukan Urutan Jarak Incremental: Pilih urutan jarak incremental (gap sequence). Contoh urutan yang umum digunakan adalah: n/2, n/4, n/8, …, 1, di mana n adalah ukuran array. Urutan lainnya termasuk yang diusulkan oleh Hibbard atau Sedgewick.
2. Loop Utama (Outer Loop): Iterasi melalui urutan jarak incremental, mulai dari jarak incremental terbesar sampai 1.
3. Loop Sub-list (Middle Loop): Untuk setiap jarak incremental, iterasi melalui array, mulai dari indeks jarak_incremental hingga akhir array.
4. Insertion Sort Modifikasi (Inner Loop): Untuk setiap elemen pada indeks tertentu, lakukan insertion sort pada sub-list yang dibentuk oleh jarak incremental. Artinya, bandingkan elemen tersebut dengan elemen sebelumnya yang berjarak jarak_incremental, dan geser elemen yang lebih besar ke kanan hingga menemukan posisi yang tepat untuk elemen tersebut.

Contoh Implementasi Kode (Python):

def shell_sort(arr):
  n = len(arr)
  jarak = n // 2  # Inisialisasi jarak incremental

  while jarak > 0:
    for i in range(jarak, n):
      temp = arr[i]
      j = i
      while j >= jarak and arr[j - jarak] > temp:
        arr[j] = arr[j - jarak]
        j -= jarak
      arr[j] = temp
    jarak //= 2

  return arr

# Contoh penggunaan
data = [12, 34, 54, 2, 3, 56, 22, 98, 76, 45]
print("Array sebelum diurutkan:", data)
data_urut = shell_sort(data)
print("Array setelah diurutkan:", data_urut)

Pada kode di atas, fungsi shell_sort menerima sebuah array arr sebagai input. Variabel jarak diinisialisasi dengan setengah dari panjang array. Outer loop berlanjut selama jarak lebih besar dari 0. Di dalam outer loop, middle loop melakukan iterasi melalui array dengan menggunakan jarak sebagai jarak incremental. Inner loop kemudian melakukan insertion sort pada sub-list yang dibentuk. Akhirnya, jarak dibagi 2 pada setiap iterasi outer loop.

Kompleksitas Waktu dan Ruang

Kompleksitas waktu Shell Sort sangat bergantung pada urutan jarak incremental yang digunakan. Dalam kasus terburuk, kompleksitasnya bisa mencapai O(n²), sama seperti insertion sort. Namun, dengan pemilihan urutan yang baik, Shell Sort dapat mencapai kompleksitas waktu mendekati O(n log n) pada kasus rata-rata dan terbaik.

Kompleksitas ruang Shell Sort adalah O(1), karena algoritma ini melakukan pengurutan di tempat (in-place sorting), yang berarti tidak memerlukan ruang tambahan yang signifikan.

Kelebihan dan Kekurangan Shell Sort

• Kelebihan:

  • Relatif sederhana untuk diimplementasikan.
  • Lebih efisien daripada insertion sort, terutama untuk data berukuran besar.
  • Melakukan pengurutan di tempat (in-place).

• Kekurangan:

  • Kompleksitas waktu sangat bergantung pada urutan jarak incremental yang dipilih.
  • Tidak stabil (yaitu, elemen dengan nilai yang sama mungkin tidak mempertahankan urutan aslinya).
  • Tidak seefisien algoritma pengurutan lanjutan seperti merge sort atau quicksort dalam kasus rata-rata.

Pemilihan Urutan Jarak Incremental (Gap Sequence)

Pemilihan urutan jarak incremental adalah faktor krusial dalam kinerja Shell Sort. Beberapa urutan yang umum digunakan termasuk:

• Knuth’s sequence: h = 3h + 1 (misalnya, 1, 4, 13, 40, 121, …)
• Hibbard’s sequence: h = 2<sup>k</sup> - 1 (misalnya, 1, 3, 7, 15, 31, …)
• Sedgewick’s sequence: Menggunakan kombinasi rumus kompleks untuk menghasilkan urutan yang lebih optimal.

Tidak ada urutan jarak incremental yang secara universal terbaik untuk semua jenis data. Pemilihan urutan yang tepat seringkali bergantung pada karakteristik data yang akan diurutkan. Eksperimen dengan beberapa urutan berbeda mungkin diperlukan untuk menemukan urutan yang memberikan kinerja terbaik untuk kasus tertentu.

Kapan Menggunakan Shell Sort?

Shell Sort menjadi pilihan yang baik dalam situasi berikut:

• Ketika data berukuran sedang (tidak terlalu kecil, tidak terlalu besar).
• Ketika implementasi yang sederhana lebih diprioritaskan daripada kinerja yang optimal.
• Ketika algoritma pengurutan di tempat (in-place) diperlukan.
• Sebagai langkah awal untuk algoritma pengurutan yang lebih kompleks, seperti hybrid sort.

Shell Sort mungkin kurang sesuai untuk data berukuran sangat besar atau ketika stabilitas pengurutan sangat penting. Dalam kasus tersebut, algoritma seperti merge sort atau quicksort mungkin lebih baik.

Kesimpulan

Shell Sort adalah algoritma pengurutan yang elegan dan praktis yang menawarkan peningkatan kinerja dibandingkan insertion sort tradisional, terutama untuk data berukuran sedang. Konsep jarak incremental memungkinkan elemen-elemen data yang terletak jauh satu sama lain untuk dipindahkan ke posisi yang tepat lebih cepat daripada insertion sort. Meskipun kompleksitas waktu sangat bergantung pada urutan jarak incremental yang dipilih, dengan pemilihan yang tepat, Shell Sort dapat menjadi pilihan yang efisien dan mudah diimplementasikan untuk berbagai aplikasi pengurutan. Memahami prinsip dasar dan faktor-faktor yang mempengaruhi kinerja Shell Sort memungkinkan pengembang untuk membuat keputusan yang tepat dalam memilih algoritma pengurutan yang paling sesuai untuk kebutuhan mereka. Pertimbangkan karakteristik data Anda dan batasan sumber daya untuk memaksimalkan efektivitas algoritma Shell Sort. Apakah Anda siap untuk bereksperimen dengan urutan jarak incremental yang berbeda dan melihat bagaimana mereka mempengaruhi kecepatan pengurutan data Anda?