Panduan Lengkap Shell Sort Contoh Kode dan Analisis

Shell Sort: Panduan Lengkap Contoh Kode dan Analisis

Shell Sort adalah algoritma pengurutan (sorting algorithm) yang merupakan generalisasi dari insertion sort, dan seringkali menawarkan performa yang lebih baik. Ditemukan oleh Donald Shell pada tahun 1959, algoritma ini bekerja dengan membagi array menjadi beberapa sub-array yang lebih kecil berdasarkan interval (gap) tertentu, kemudian mengurutkan sub-array tersebut menggunakan insertion sort. Interval ini kemudian dikurangi secara bertahap hingga menjadi 1, pada saat itu, array secara keseluruhan diurutkan dengan efektif menggunakan insertion sort. Keunggulan Shell Sort terletak pada kemampuannya memindahkan elemen-elemen yang jauh dari posisi seharusnya dengan cepat, sehingga mengurangi jumlah perbandingan dan pergeseran yang dibutuhkan pada tahap akhir pengurutan.

Bagaimana Shell Sort Bekerja?

Konsep utama Shell Sort adalah “diminishing increment sort,” yang berarti mengurutkan elemen-elemen yang dipisahkan oleh interval yang berkurang secara progresif. Berikut adalah langkah-langkah dasarnya:

1. Inisialisasi Interval (Gap): Tentukan nilai awal interval. Umumnya, nilai interval awal adalah setengah dari panjang array (n/2). Ada juga variasi lain, seperti menggunakan formula 3*h + 1 (sedikit lebih kompleks tapi seringkali menghasilkan performa lebih baik, terutama untuk data berukuran besar).
2. Pengurutan Sub-array: Urutkan sub-array yang elemen-elemennya dipisahkan oleh interval. Ini biasanya dilakukan menggunakan insertion sort. Bayangkan array sebagai matriks di mana setiap kolom merepresentasikan sub-array yang akan diurutkan.
3. Pengurangan Interval: Kurangi nilai interval. Misalnya, jika interval awal adalah n/2, maka interval berikutnya bisa menjadi n/4, n/8, dan seterusnya.
4. Ulangi Langkah 2 dan 3: Ulangi proses pengurutan sub-array dan pengurangan interval sampai interval bernilai 1. Ketika interval bernilai 1, seluruh array diurutkan menggunakan insertion sort, namun array sudah hampir terurut (sebagian besar elemen sudah berada di posisi yang benar) sehingga insertion sort berjalan lebih efisien.

Contoh Kode Implementasi Shell Sort (Python)

Berikut adalah contoh implementasi Shell Sort dalam bahasa Python:

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

    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 # Kurangi interval

# Contoh penggunaan
data = [12, 34, 54, 2, 3, 33, 10]
shell_sort(data)
print("Array yang telah diurutkan:", data)

Penjelasan Kode:

• Fungsi shell_sort(arr) menerima array arr sebagai input.
• n = len(arr) menyimpan panjang array.
• gap = n // 2 menginisialisasi interval awal sebagai setengah dari panjang array (integer division).
• while gap > 0: adalah loop utama yang terus berjalan selama interval masih positif.
• for i in range(gap, n): adalah loop untuk iterasi melalui setiap elemen mulai dari indeks gap.
• temp = arr[i] menyimpan nilai elemen saat ini yang akan disisipkan di posisi yang benar.
• j = i menginisialisasi indeks j untuk iterasi mundur dalam sub-array.
• while j >= gap and arr[j - gap] > temp: adalah loop untuk membandingkan elemen saat ini dengan elemen di belakangnya dengan jarak gap. Jika elemen di belakang lebih besar dari elemen saat ini, elemen tersebut digeser ke depan.
• arr[j] = temp menyisipkan elemen saat ini di posisi yang benar setelah pergeseran.
• gap //= 2 mengurangi interval setelah selesai mengurutkan sub-array dengan interval saat ini.

Analisis Kompleksitas Waktu:

Analisis kompleksitas waktu Shell Sort cukup rumit karena sangat bergantung pada urutan interval yang digunakan. Kompleksitas waktu terbaik (best-case) adalah O(n log n), terjadi ketika data sudah hampir terurut. Kompleksitas waktu rata-rata (average-case) bervariasi tergantung pada urutan interval, namun secara umum berada di antara O(n log n) dan O(n²). Kompleksitas waktu terburuk (worst-case) adalah O(n²), terjadi ketika urutan interval tidak optimal dan menyebabkan banyak perbandingan dan pergeseran. Beberapa urutan interval yang lebih baik, seperti urutan Knuth (h = 3*h + 1), dapat menghasilkan performa yang lebih mendekati O(n log n).

Keunggulan dan Kekurangan Shell Sort:

Keunggulan:

• Lebih Efisien daripada Insertion Sort: Shell Sort secara signifikan lebih efisien daripada Insertion Sort, terutama untuk array berukuran besar, karena mampu memindahkan elemen-elemen yang jauh dari posisi seharusnya dengan cepat.
• Relatif Mudah Diimplementasikan: Meskipun analisis kompleksitasnya rumit, implementasi kode Shell Sort relatif sederhana.
• In-place Sorting: Shell Sort adalah algoritma in-place sorting, yang berarti tidak membutuhkan ruang tambahan yang signifikan (hanya ruang konstan untuk variabel sementara).

Kekurangan:

• Kompleksitas Waktu Bergantung pada Urutan Interval: Performa Shell Sort sangat sensitif terhadap urutan interval yang dipilih. Urutan interval yang buruk dapat menyebabkan performa yang buruk.
• Tidak Stabil: Shell Sort bukan algoritma pengurutan yang stabil. Ini berarti bahwa elemen-elemen dengan nilai yang sama mungkin tidak mempertahankan urutan aslinya setelah pengurutan.
• Kurang Efisien Dibandingkan Algoritma Pengurutan Lanjutan: Algoritma pengurutan yang lebih canggih seperti Merge Sort atau Quick Sort umumnya menawarkan performa yang lebih baik, terutama untuk array berukuran sangat besar.

Kapan Menggunakan Shell Sort?

Shell Sort merupakan pilihan yang baik dalam situasi berikut:

• Array Berukuran Sedang: Shell Sort bekerja dengan baik untuk array berukuran sedang (beberapa ribu elemen).
• Implementasi yang Sederhana Dibutuhkan: Ketika implementasi yang sederhana lebih penting daripada performa optimal.
• Ruang Memori Terbatas: Ketika ruang memori terbatas dan algoritma in-place sorting dibutuhkan.
• Sebagai Langkah Awal Pengurutan: Shell Sort dapat digunakan sebagai langkah awal untuk mengurutkan array sebelum menggunakan algoritma pengurutan lain yang lebih canggih (seperti Insertion Sort pada array yang hampir terurut).

Tips untuk Meningkatkan Performa Shell Sort:

• Pilih Urutan Interval yang Optimal: Gunakan urutan interval yang telah terbukti efektif, seperti urutan Knuth (h = 3*h + 1).
• Eksperimen dengan Urutan Interval yang Berbeda: Untuk aplikasi khusus, mungkin perlu bereksperimen dengan urutan interval yang berbeda untuk menemukan yang paling cocok.
• Pertimbangkan Ukuran Array: Urutan interval yang optimal mungkin berbeda tergantung pada ukuran array.

Kesimpulan

Shell Sort adalah algoritma pengurutan yang praktis dan efisien untuk array berukuran sedang. Meskipun kompleksitas waktunya bergantung pada urutan interval yang dipilih, implementasinya yang relatif sederhana dan sifat in-place sorting membuatnya menjadi pilihan yang baik dalam banyak situasi. Dengan memilih urutan interval yang tepat, Shell Sort dapat memberikan peningkatan performa yang signifikan dibandingkan dengan Insertion Sort. Pertimbangkan faktor-faktor seperti ukuran array, kebutuhan memori, dan kompleksitas implementasi saat memutuskan apakah akan menggunakan Shell Sort atau algoritma pengurutan lain. Shell Sort memberikan alternatif yang solid dan menyeimbangkan kemudahan implementasi dengan efisiensi yang cukup baik, menjadikannya alat yang berharga dalam gudang senjata seorang programmer.