Shell Sort di C++: Pengertian, Cara Kerja, dan Contoh Program

Sorting adalah salah satu operasi fundamental dalam ilmu komputer yang sering digunakan di berbagai aplikasi. Ada berbagai algoritma sorting yang dapat digunakan, tetapi salah satu yang cukup menarik adalah Shell Sort. Dalam artikel ini, kita akan membahas secara mendalam tentang Shell Sort di C++, termasuk pengertiannya, cara kerjanya, dan tentu saja, contoh programnya.

Shell Sort di C++

Pengertian Shell Sort

Shell Sort adalah sebuah algoritma pengurutan yang diciptakan oleh Donald L. Shell pada tahun 1959. Algoritma ini merupakan sebuah varian dari algoritma insertion sort. Keunikan dari Shell Sort terletak pada cara ia membandingkan elemen yang tidak berdekatan, sebelum akhirnya mengurutkan elemen yang berdekatan.

Cara Kerja Shell Sort

Mekanisme kerja Shell Sort di C++ cukup unik. Algoritma ini memulai dengan suatu "gap" atau jarak antara elemen yang akan dibandingkan. Gap ini akan terus mengecil hingga mencapai nilai 1, di mana algoritma akan berubah menjadi insertion sort biasa. Berikut adalah langkah-langkah dalam Shell Sort: 

1. Inisialisasi Gap: Memilih ukuran gap, biasanya setengah dari total elemen.
2. Pembandingan dan Pertukaran: Membandingkan elemen yang berjarak sejauh 'gap' dan menukarnya jika diperlukan.
3. Pengurangan Gap: Mengurangi ukuran gap dan mengulangi proses.
4. Selesai: Proses berakhir ketika gap = 1 dan array sudah terurut.

Baca Juga: Tutorial Lengkap Belajar Bahasa Pemrograman C++

Contoh Program Shell Sort di C++

Pada bagian ini, kita akan melihat contoh program yang mengimplementasikan algoritma Shell Sort di C++. Berikut adalah kode programnya:

#include <iostream>

using namespace std;

void shellSort(int arr[], int n) {

  for (int gap = n/2; gap > 0; gap /= 2) {

    for (int i = gap; i < n; i += 1) {

      int temp = arr[i];

      int j;

      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)

        arr[j] = arr[j - gap];

      arr[j] = temp;

    }

  }

}

int main() {

  int arr[] = {45, 67, 23, 45, 21, 24, 7, 2, 6, 4, 90};

  int n = sizeof(arr)/sizeof(arr[0]);

  shellSort(arr, n);

  

  for (int i=0; i<n; i++)

    cout << arr[i] << " ";

  return 0;

}

Output

2 4 6 7 21 23 24 45 45 67 90

Penjelasan Program

#include <iostream>: Ini adalah header file untuk fungsi input-output di C++.

using namespace std; : Ini memungkinkan kita untuk menggunakan standar fungsi C++ tanpa perlu menulis std:: sebelum setiap fungsi.

void shellSort(int arr[], int n): Fungsi shellSort didefinisikan dengan dua parameter; sebuah array arr[] dan jumlah elemennya n.

• for (int gap = n/2; gap > 0; gap /= 2): Loop pertama mengatur ukuran gap. Ini dimulai dari setengah panjang array dan setiap iterasinya akan dibagi 2.
• for (int i = gap; i < n; i += 1): Loop kedua berjalan mulai dari indeks yang sejauh gap dari awal array hingga akhir array.
• int temp = arr[i];: Variabel temp menyimpan nilai elemen yang akan kita bandingkan.
• int j;: Variabel j digunakan untuk membantu dalam swapping dan membandingkan elemen. 
• for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap];: Loop ketiga ini bertugas untuk membandingkan dan menukar elemen jika perlu.
• arr[j] = temp;: Menempatkan temp pada posisinya yang benar di array.

int main(): Fungsi utama di mana program dimulai.

• int arr[] = {45, 67, 23, 45, 21, 24, 7, 2, 6, 4, 90};: Inisialisasi array yang akan diurutkan.
• int n = sizeof(arr)/sizeof(arr[0]);: Menentukan ukuran array.
• shellSort(arr, n);: Memanggil fungsi shellSort untuk mengurutkan array.
• for (int i=0; i<n; i++) cout << arr[i] << " ";: Mencetak array yang telah diurutkan ke layar.

Program di atas menunjukkan bagaimana Shell Sort di C++ dapat diimplementasikan secara efisien. Program diatas adalah contoh program Shell Sort dalam C++ yang sederhana namun sangat efektif.

Kelebihan dan Kekurangan Shell Sort

Kelebihan Shell Sort:

• Efisiensi: Meskipun tidak seefisien algoritma sorting yang lebih canggih seperti Quick Sort atau Merge Sort, Shell Sort biasanya lebih efisien daripada algoritma sederhana seperti Bubble Sort atau Insertion Sort.
• Sederhana untuk Implementasi: Shell Sort relatif mudah untuk diimplementasikan. Ini membuatnya menjadi pilihan yang baik untuk proyek atau aplikasi skala kecil.
• Membutuhkan Memori Sedikit: Tidak seperti algoritma lain seperti Merge Sort, Shell Sort adalah algoritma in-place, yang berarti ia tidak membutuhkan alokasi memori tambahan.
• Adaptif: Shell Sort dapat beradaptasi terhadap tingkat penyebaran elemen di dalam array. Jika array sebagian sudah terurut, waktu eksekusi bisa menjadi lebih cepat.

Kekurangan Shell Sort:

• Tidak Stabil: Salah satu kelemahan dari Shell Sort adalah tidak stabil. Artinya, ia mungkin akan mengubah urutan relatif dari elemen-elemen yang memiliki nilai sama.
• Kompleksitas Waktu: Meski lebih cepat dibandingkan dengan algoritma sorting sederhana, kompleksitas waktu Shell Sort dalam kasus terburuk masih cukup tinggi, yaitu O(n2). 
• Pemilihan Gap: Efisiensi dari Shell Sort sangat tergantung pada pemilihan gap. Memilih gap yang salah bisa menurunkan efisiensi algoritma.
• Tidak Cocok untuk Data Besar: Karena kompleksitas waktu yang cukup tinggi, algoritma ini kurang cocok untuk digunakan pada dataset yang sangat besar.

Shell Sort di C++ adalah algoritma yang cukup efisien untuk mengurutkan elemen dalam array. Meski bukan yang tercepat, algoritma ini memiliki kelebihan dalam beberapa skenario penggunaan. Melalui pemahaman yang baik tentang pengertiannya dan mekanismenya, serta dengan bantuan contoh program, kita bisa memahami algoritma ini lebih baik.

Daftar Pustaka

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). The MIT Press.
• Sedgewick, R. (2011). Algorithms (4th ed.). Addison-Wesley.

Semoga artikel ini membantu Anda memahami lebih lanjut mengenai Shell Sort di C++. Selamat coding!

MateriDosen.Com

Berbagi: