Shell Sort: Cara Kerja, Kelebihan, dan Implementasinya
Shell Sort adalah algoritma pengurutan (sorting algorithm) yang merupakan generalisasi dari Insertion Sort. Ia mengatasi kekurangan Insertion Sort yang kurang efisien dalam mengurutkan elemen yang berjauhan. Dikembangkan oleh Donald Shell pada tahun 1959, Shell Sort dikenal karena kesederhanaannya dan performa yang cukup baik untuk ukuran data sedang hingga besar.
Prinsip Dasar Shell Sort
Berbeda dengan Insertion Sort yang membandingkan elemen yang berdekatan, Shell Sort bekerja dengan membandingkan elemen yang terpisah dengan jarak tertentu, yang disebut gap. Gap ini berkurang secara bertahap hingga mencapai 1. Pada setiap iterasi dengan gap tertentu, algoritma ini melakukan Insertion Sort pada sub-list yang terbentuk dari elemen-elemen yang terpisah oleh gap tersebut. Dengan kata lain, data diurutkan sebagian pada setiap iterasi dengan gap yang lebih besar, yang memungkinkan elemen yang jauh dari posisi akhirnya berpindah lebih cepat daripada hanya menggunakan Insertion Sort biasa.
Langkah-langkah Algoritma Shell Sort
Berikut adalah langkah-langkah umum dalam algoritma Shell Sort:
- Tentukan Sequence Gap: Pilih urutan nilai gap (biasanya disebut increment sequence). Salah satu sequence yang umum digunakan adalah Shell’s sequence:
n/2, n/4, n/8, ..., 1(di mananadalah ukuran array). Ada sequence lain yang lebih efisien, seperti Hibbard’s sequence dan Sedgewick’s sequence, namun Shell’s sequence lebih mudah dipahami. - Looping dengan Gap yang Berkurang: Mulai dengan gap terbesar (dari sequence yang dipilih) dan ulangi langkah-langkah berikut hingga gap mencapai 1:
- Looping Sub-list: Untuk setiap sub-list yang terbentuk dengan gap tertentu, lakukan Insertion Sort. Sub-list ini terdiri dari elemen-elemen pada indeks
i, i + gap, i + 2*gap, ...di manaibervariasi dari 0 hinggagap - 1. - Insertion Sort pada Sub-list: Untuk setiap elemen dalam sub-list, bandingkan dengan elemen-elemen sebelumnya dengan jarak gap dan sisipkan elemen tersebut pada posisi yang tepat. Ini dilakukan dengan cara yang sama seperti Insertion Sort, tetapi dengan jarak perbandingan yang lebih besar (gap).
- Looping Sub-list: Untuk setiap sub-list yang terbentuk dengan gap tertentu, lakukan Insertion Sort. Sub-list ini terdiri dari elemen-elemen pada indeks
- Gap = 1: Insertion Sort Terakhir: Ketika gap mencapai 1, algoritma ini melakukan Insertion Sort pada seluruh array. Pada tahap ini, array sudah hampir terurut, sehingga Insertion Sort akan bekerja dengan sangat efisien.
Ilustrasi Cara Kerja Shell Sort
Mari kita ilustrasikan cara kerja Shell Sort dengan array: [12, 34, 54, 2, 3, 8, 9, 4, 1]. Kita akan menggunakan Shell’s sequence: n/2, n/4, n/8, ..., 1. Dalam kasus ini, n = 9, sehingga sequence gap kita adalah 4, 2, 1.
- Gap = 4: Kita memiliki 4 sub-list:
[12, 3][34, 8][54, 9][2, 4]
Setelah melakukan Insertion Sort pada setiap sub-list, array menjadi:[3, 8, 9, 2, 12, 34, 54, 4, 1]
- Gap = 2: Kita memiliki 2 sub-list:
[3, 9, 12, 54, 1][8, 2, 34, 4]
Setelah melakukan Insertion Sort pada setiap sub-list, array menjadi:[1, 2, 3, 4, 12, 8, 34, 9, 54]
- Gap = 1: Kita melakukan Insertion Sort pada seluruh array. Karena array sudah hampir terurut, Insertion Sort bekerja dengan cepat dan menghasilkan array yang terurut:
[1, 2, 3, 4, 8, 9, 12, 34, 54]
Kelebihan Shell Sort
- Sederhana dan Mudah Diimplementasikan: Algoritma Shell Sort relatif mudah dipahami dan diimplementasikan, terutama jika dibandingkan dengan algoritma pengurutan yang lebih kompleks seperti Merge Sort atau Quick Sort.
- Performa yang Baik untuk Data Berukuran Sedang: Shell Sort umumnya lebih efisien daripada Insertion Sort dan Bubble Sort untuk data berukuran sedang. Meskipun tidak secepat algoritma O(n log n) seperti Merge Sort atau Quick Sort untuk data yang sangat besar, Shell Sort seringkali menjadi pilihan yang baik karena kesederhanaannya.
- In-place Sorting: Shell Sort adalah algoritma in-place, yang berarti ia hanya memerlukan sedikit ruang memori tambahan di luar array yang akan diurutkan.
- Adaptif: Performa Shell Sort dapat ditingkatkan dengan memilih sequence gap yang lebih optimal.
Kekurangan Shell Sort
- Kompleksitas Waktu Rata-rata dan Terburuk yang Kurang Jelas: Analisis kompleksitas waktu Shell Sort sangat kompleks dan bergantung pada sequence gap yang digunakan. Secara umum, kompleksitas waktu rata-rata berada di antara O(n log n) dan O(n2), tetapi tidak ada formula yang pasti. Dalam kasus terburuk, kompleksitasnya bisa mencapai O(n2).
- Tidak Stabil: Shell Sort bukanlah algoritma pengurutan yang stabil. Ini berarti bahwa jika ada dua elemen dengan nilai yang sama, urutan relatifnya mungkin berubah setelah pengurutan.
Implementasi Shell Sort dalam Kode (Python)
def shell_sort(arr):
n = len(arr)
gap = n // 2 # Shell's sequence
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, 8, 9, 4, 1]
sorted_arr = shell_sort(arr)
print("Array yang diurutkan:", sorted_arr) # Output: Array yang diurutkan: [1, 2, 3, 4, 8, 9, 12, 34, 54]Implementasi Shell Sort dalam Kode (Java)
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {12, 34, 54, 2, 3, 8, 9, 4, 1};
shellSort(arr);
System.out.print("Array yang diurutkan: ");
for (int i : arr) {
System.out.print(i + " ");
}
// Output: Array yang diurutkan: 1 2 3 4 8 9 12 34 54
}
}Pemilihan Sequence Gap yang Optimal
Pemilihan sequence gap yang tepat sangat penting untuk kinerja Shell Sort. Shell’s sequence (n/2, n/4, n/8, …, 1) adalah sequence yang paling sederhana, tetapi bukan yang paling efisien. Sequence lain yang lebih optimal termasuk:
- Hibbard’s Sequence: 2k – 1 (1, 3, 7, 15, 31, …)
- Sedgewick’s Sequence: 1, 4, 13, 40, 121, 364, … (Rumusnya lebih kompleks)
Secara umum, Sedgewick’s sequence cenderung memberikan kinerja terbaik untuk berbagai ukuran data.
Kesimpulan
Shell Sort adalah algoritma pengurutan yang sederhana, in-place, dan efisien untuk data berukuran sedang. Meskipun kompleksitas waktunya tidak sejelas algoritma O(n log n), Shell Sort seringkali menjadi pilihan yang baik karena kemudahannya dalam implementasi dan performanya yang cukup baik. Pemilihan sequence gap yang optimal dapat meningkatkan kinerja Shell Sort secara signifikan. Dengan memahami prinsip dasar dan langkah-langkah algoritmanya, Anda dapat memanfaatkan Shell Sort untuk mengurutkan data Anda dengan lebih efisien. Apakah Anda akan mencoba mengimplementasikan Shell Sort dengan sequence gap yang berbeda dan membandingkan kinerjanya?
