Belajar Shell Sort Contoh Soal dan Pembahasan

Shell Sort: Algoritma Sorting Efisien dengan Jarak yang Menyusut

Shell Sort adalah algoritma pengurutan (sorting) yang merupakan generalisasi dari insertion sort. Ia bekerja dengan membandingkan elemen-elemen yang terpisah dengan jarak tertentu (disebut gap atau interval) lalu melakukan insertion sort pada sub-list yang terbentuk dari elemen-elemen tersebut. Proses ini diulangi dengan mengurangi jarak secara bertahap hingga jarak menjadi 1, yang pada dasarnya adalah insertion sort standar.

Kelebihan utama Shell Sort adalah kemampuannya untuk memindahkan elemen-elemen yang jauh dari posisi seharusnya dengan cepat di awal proses. Ini memperkecil jumlah perbandingan dan pertukaran yang diperlukan di tahap akhir, sehingga meningkatkan efisiensi dibandingkan insertion sort standar, terutama untuk array berukuran besar. Meskipun bukan algoritma pengurutan tercepat, Shell Sort seringkali lebih cepat daripada insertion sort atau bubble sort, dan relatif mudah diimplementasikan.

Prinsip Kerja Shell Sort: Konsep Gap dan Insertion Sort

Inti dari Shell Sort terletak pada konsep gap. Algoritma ini dimulai dengan gap yang besar, yang kemudian secara bertahap dikurangi hingga mencapai 1. Untuk setiap nilai gap, algoritma ini melakukan “gapped insertion sort”. Artinya, ia membandingkan elemen-elemen yang terpisah sejauh gap dan menukarnya jika perlu.

Misalnya, jika gap adalah 5, algoritma akan membandingkan elemen di indeks 0 dengan elemen di indeks 5, elemen di indeks 1 dengan elemen di indeks 6, dan seterusnya. Setelah satu iterasi selesai, gap dikurangi, dan proses ini diulangi. Pengurangan gap biasanya dilakukan dengan membagi gap sebelumnya dengan faktor tertentu (seringkali 2 atau 3).

Gapped insertion sort ini memungkinkan elemen-elemen yang berada jauh dari posisi yang benar untuk bergerak lebih cepat menuju posisi yang lebih tepat di array. Ketika gap mencapai 1, algoritma pada dasarnya melakukan insertion sort pada array yang hampir terurut, yang sangat efisien.

Langkah-langkah Algoritma Shell Sort

Berikut adalah langkah-langkah umum algoritma Shell Sort:

1. Pilih Urutan Gap: Tentukan urutan nilai gap yang akan digunakan. Urutan ini sangat penting untuk kinerja Shell Sort. Beberapa urutan gap yang umum adalah:

   • Shell’s Original Sequence: n/2, n/4, ..., 1 (di mana n adalah ukuran array)
   • Knuth’s Sequence: (3^k - 1) / 2 (mulai dari k yang terbesar sehingga hasilnya kurang dari n/3)
   • Sedgewick’s Sequence: Berbagai variasi yang lebih kompleks, seringkali memberikan kinerja yang lebih baik.

2. Iterasi untuk Setiap Gap: Untuk setiap nilai gap dalam urutan yang dipilih:

   • Gapped Insertion Sort: Lakukan gapped insertion sort pada array dengan gap tersebut. Ini berarti:
     • Iterasi melalui array dari indeks gap hingga akhir array.
     • Untuk setiap elemen pada indeks i, bandingkan dengan elemen pada indeks i - gap, i - 2*gap, dan seterusnya, hingga mencapai awal array atau menemukan elemen yang lebih kecil (atau sama dengan, tergantung urutan yang diinginkan).
     • Sisipkan elemen pada indeks i pada posisi yang tepat dalam urutan yang telah diurutkan sebagian.

3. Selesai: Setelah iterasi selesai untuk gap = 1, array akan terurut sepenuhnya.

Contoh Soal dan Pembahasan: Mengurutkan Array dengan Shell Sort

Misalkan kita memiliki array berikut: [12, 34, 54, 2, 3, 89, 76, 21]

Mari kita urutkan array ini menggunakan Shell Sort dengan Shell’s Original Sequence (gap = n/2, n/4, … 1). Ukuran array adalah 8.

1. Gap = 8/2 = 4:

   • Bandingkan arr[0] (12) dengan arr[4] (3): Tukar. Array menjadi: [3, 34, 54, 2, 12, 89, 76, 21]
   • Bandingkan arr[1] (34) dengan arr[5] (89): Tidak ada perubahan.
   • Bandingkan arr[2] (54) dengan arr[6] (76): Tidak ada perubahan.
   • Bandingkan arr[3] (2) dengan arr[7] (21): Tukar. Array menjadi: [3, 34, 54, 21, 12, 89, 76, 2]

2. Gap = 4/2 = 2:

   • Bandingkan arr[0] (3) dengan arr[2] (54): Tukar. Array menjadi: [54, 34, 3, 21, 12, 89, 76, 2]
   • Bandingkan arr[1] (34) dengan arr[3] (21): Tukar. Array menjadi: [54, 21, 3, 34, 12, 89, 76, 2]
   • Bandingkan arr[2] (3) dengan arr[4] (12): Tidak ada perubahan.
   • Bandingkan arr[3] (34) dengan arr[5] (89): Tidak ada perubahan.
   • Bandingkan arr[4] (12) dengan arr[6] (76): Tidak ada perubahan.
   • Bandingkan arr[5] (89) dengan arr[7] (2): Tukar. Array menjadi: [54, 21, 3, 34, 12, 2, 76, 89]

   Setelah menyelesaikan iterasi dengan gap 2 dan melakukan insertion sort pada setiap sub-list (0, 2, 4, 6) dan (1, 3, 5, 7), kita mendapatkan array: [3, 2, 12, 21, 54, 34, 76, 89]

3. Gap = 2/2 = 1:

   • Sekarang kita memiliki gap 1, yang pada dasarnya adalah insertion sort standar. Lakukan insertion sort pada seluruh array.
   • Hasil akhir setelah insertion sort: [2, 3, 12, 21, 34, 54, 76, 89]

Array sekarang sudah terurut.

Implementasi Kode (Python)

def shell_sort(arr):
  n = len(arr)
  gap = n // 2

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

  return arr

# Contoh penggunaan
arr = [12, 34, 54, 2, 3, 89, 76, 21]
sorted_arr = shell_sort(arr)
print("Array setelah diurutkan:", sorted_arr) # Output: [2, 3, 12, 21, 34, 54, 76, 89]

Kompleksitas Waktu Shell Sort

Kompleksitas waktu Shell Sort sangat bergantung pada urutan gap yang digunakan. Tidak ada formula yang tepat untuk kompleksitas waktu terbaik atau terburuk untuk semua urutan gap.

• Best Case: O(n log n) – terjadi ketika array sudah hampir terurut.
• Average Case: Bervariasi tergantung urutan gap. Untuk beberapa urutan, bisa mencapai O(n^(3/2)) atau bahkan lebih baik.
• Worst Case: O(n^2) – terjadi untuk beberapa urutan gap yang buruk.

Meskipun kompleksitas waktu Shell Sort tidak sebaik algoritma pengurutan tingkat lanjut seperti merge sort atau quicksort, ia seringkali lebih cepat daripada insertion sort, terutama untuk array berukuran sedang.

Kapan Menggunakan Shell Sort?

Shell Sort adalah pilihan yang baik dalam situasi berikut:

• Array berukuran sedang: Untuk array yang tidak terlalu besar, Shell Sort seringkali memberikan kinerja yang baik dengan implementasi yang relatif sederhana.
• Ketika implementasi sederhana lebih diutamakan daripada kinerja optimal: Jika Anda membutuhkan algoritma pengurutan yang cepat diimplementasikan dan tidak terlalu rumit, Shell Sort bisa menjadi pilihan yang baik.
• Ketika insertion sort dianggap terlalu lambat: Shell Sort dapat dianggap sebagai peningkatan dari insertion sort, yang membuatnya lebih efisien untuk array yang lebih besar.

Kesimpulan

Shell Sort adalah algoritma pengurutan yang efisien dengan konsep gap yang cerdas. Ia mengombinasikan keunggulan insertion sort dengan kemampuan untuk memindahkan elemen-elemen yang jauh dari posisi seharusnya dengan cepat. Meskipun tidak secepat algoritma pengurutan tingkat lanjut lainnya, Shell Sort seringkali lebih cepat daripada insertion sort dan relatif mudah diimplementasikan. Pemilihan urutan gap yang tepat sangat penting untuk kinerja Shell Sort. Memahami prinsip kerja dan langkah-langkah algoritma ini memungkinkan Anda untuk mengaplikasikannya dalam berbagai situasi pengurutan data. Apakah ada situasi spesifik di mana Anda mempertimbangkan menggunakan Shell Sort dibandingkan algoritma sorting lainnya?