Insertion Sort Studi Kasus & Contoh Penggunaan

Insertion Sort: Memahami Algoritma Penyortiran Sederhana dengan Studi Kasus dan Contoh Penggunaan

Insertion Sort, atau penyortiran sisip, merupakan salah satu algoritma penyortiran yang paling sederhana dan intuitif. Berbeda dengan algoritma lain yang mungkin terlihat lebih rumit dan efisien untuk data berukuran besar, Insertion Sort unggul dalam kesederhanaan implementasi dan efisiensinya pada data yang berukuran kecil atau hampir terurut. Inti dari Insertion Sort adalah membangun urutan terurut secara bertahap dengan menyisipkan setiap elemen data ke posisi yang tepat di dalam sub-array yang sudah terurut. Proses ini mirip dengan cara kita menyortir kartu remi di tangan. Kita mengambil satu kartu dan memindahkannya ke posisi yang sesuai di antara kartu-kartu yang sudah terurut.

Cara Kerja Insertion Sort: Langkah Demi Langkah

Insertion Sort bekerja dengan membagi array menjadi dua bagian: bagian yang sudah terurut dan bagian yang belum terurut. Awalnya, bagian yang sudah terurut hanya berisi elemen pertama dari array. Kemudian, untuk setiap elemen di bagian yang belum terurut, algoritma akan melakukan hal berikut:

1. Ambil elemen: Ambil elemen pertama dari bagian yang belum terurut (sebut saja key).
2. Bandingkan dan geser: Bandingkan key dengan elemen-elemen di bagian yang sudah terurut, mulai dari elemen terakhir (paling kanan). Jika key lebih kecil dari elemen yang dibandingkan, geser elemen tersebut ke kanan untuk memberi ruang bagi key. Proses ini terus diulangi sampai key lebih besar atau sama dengan elemen yang dibandingkan, atau sampai kita mencapai awal dari bagian yang sudah terurut.
3. Sisipkan: Sisipkan key ke posisi yang kosong yang telah dibuat di langkah sebelumnya.

Proses ini diulangi sampai semua elemen di bagian yang belum terurut telah dipindahkan ke bagian yang sudah terurut.

Contoh Sederhana: Menyortir Angka

Misalkan kita memiliki array angka berikut: [5, 2, 4, 6, 1, 3]

Berikut adalah langkah-langkah Insertion Sort untuk mengurutkan array ini:

1. Iterasi 1: [5, 2, 4, 6, 1, 3] (Bagian terurut: [5], Bagian belum terurut: [2, 4, 6, 1, 3])
   • key = 2
   • Bandingkan 2 dengan 5. Karena 2 < 5, geser 5 ke kanan.
   • Sisipkan 2 ke posisi yang kosong: [2, 5, 4, 6, 1, 3]
2. Iterasi 2: [2, 5, 4, 6, 1, 3] (Bagian terurut: [2, 5], Bagian belum terurut: [4, 6, 1, 3])
   • key = 4
   • Bandingkan 4 dengan 5. Karena 4 < 5, geser 5 ke kanan.
   • Bandingkan 4 dengan 2. Karena 4 > 2, sisipkan 4 ke posisi yang kosong: [2, 4, 5, 6, 1, 3]
3. Iterasi 3: [2, 4, 5, 6, 1, 3] (Bagian terurut: [2, 4, 5, 6], Bagian belum terurut: [1, 3])
   • key = 6
   • Bandingkan 6 dengan 5. Karena 6 > 5, tidak perlu menggeser.
   • Sisipkan 6 ke posisinya (tetap di tempat): [2, 4, 5, 6, 1, 3]
4. Iterasi 4: [2, 4, 5, 6, 1, 3] (Bagian terurut: [2, 4, 5, 6], Bagian belum terurut: [1, 3])
   • key = 1
   • Bandingkan 1 dengan 6. Karena 1 < 6, geser 6 ke kanan.
   • Bandingkan 1 dengan 5. Karena 1 < 5, geser 5 ke kanan.
   • Bandingkan 1 dengan 4. Karena 1 < 4, geser 4 ke kanan.
   • Bandingkan 1 dengan 2. Karena 1 < 2, geser 2 ke kanan.
   • Sisipkan 1 ke posisi yang kosong: [1, 2, 4, 5, 6, 3]
5. Iterasi 5: [1, 2, 4, 5, 6, 3] (Bagian terurut: [1, 2, 4, 5, 6], Bagian belum terurut: [3])
   • key = 3
   • Bandingkan 3 dengan 6. Karena 3 < 6, geser 6 ke kanan.
   • Bandingkan 3 dengan 5. Karena 3 < 5, geser 5 ke kanan.
   • Bandingkan 3 dengan 4. Karena 3 < 4, geser 4 ke kanan.
   • Bandingkan 3 dengan 2. Karena 3 > 2, sisipkan 3 ke posisi yang kosong: [1, 2, 3, 4, 5, 6]

Hasil akhirnya adalah array yang sudah terurut: [1, 2, 3, 4, 5, 6]

Studi Kasus: Penyortiran Data Sensor

Bayangkan sebuah sistem pemantauan lingkungan yang mengumpulkan data dari berbagai sensor, seperti suhu, kelembaban, dan tekanan udara. Data ini perlu disortir secara berkala untuk analisis dan pelaporan. Data sensor seringkali datang dalam aliran yang berkelanjutan (stream), dan Insertion Sort dapat menjadi pilihan yang baik untuk menyortir data ini secara online – yaitu, saat data tiba.

Mengapa Insertion Sort cocok untuk studi kasus ini?

• Efisiensi untuk Data Hampir Terurut: Data sensor cenderung memiliki perubahan yang bertahap. Dengan kata lain, data yang baru diterima seringkali dekat dengan nilai-nilai yang sudah ada. Insertion Sort sangat efisien dalam kasus ini, karena hanya memerlukan sedikit pergeseran untuk menyisipkan data baru ke posisi yang tepat.
• Implementasi Sederhana: Karena kesederhanaannya, Insertion Sort mudah diimplementasikan dan dipelihara. Ini penting dalam sistem yang memerlukan keandalan dan stabilitas.
• Memori Kecil: Insertion Sort merupakan algoritma in-place, yang berarti ia hanya memerlukan sedikit memori tambahan untuk beroperasi. Ini penting untuk sistem embedded atau sistem dengan sumber daya terbatas.

Contoh Penggunaan Kode (Python)

Berikut adalah contoh implementasi Insertion Sort dalam Python:

def insertion_sort(arr):
  for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and key < arr[j]:
      arr[j + 1] = arr[j]
      j -= 1
    arr[j + 1] = key

# Contoh penggunaan
data_sensor = [25.5, 24.8, 26.1, 25.9, 25.0]
insertion_sort(data_sensor)
print(data_sensor)  # Output: [24.8, 25.0, 25.5, 25.9, 26.1]

Kode di atas menunjukkan bagaimana Insertion Sort dapat digunakan untuk mengurutkan data sensor suhu. Setiap kali data sensor baru tiba, ia dapat langsung disisipkan ke dalam array yang sudah terurut menggunakan fungsi insertion_sort.

Kelebihan dan Kekurangan Insertion Sort

Kelebihan:

• Sederhana untuk diimplementasikan.
• Efisien untuk data berukuran kecil atau hampir terurut.
• Algoritma in-place (tidak memerlukan memori tambahan yang signifikan).
• Stabil (mempertahankan urutan elemen dengan nilai yang sama).
• Dapat digunakan untuk penyortiran online.

Kekurangan:

• Kurang efisien untuk data berukuran besar dengan urutan yang acak.
• Kompleksitas waktu rata-rata dan terburuk adalah O(n^2), di mana n adalah jumlah elemen.

Kapan Sebaiknya Menggunakan Insertion Sort?

Insertion Sort paling cocok digunakan dalam situasi berikut:

• Data yang akan disortir berukuran kecil (misalnya, kurang dari 100 elemen).
• Data hampir terurut.
• Membutuhkan algoritma yang sederhana dan mudah diimplementasikan.
• Memiliki batasan memori.
• Melakukan penyortiran online.

Kesimpulan

Insertion Sort, meskipun sederhana, tetap relevan dalam berbagai skenario. Kemampuannya untuk menangani data kecil dan hampir terurut secara efisien menjadikannya pilihan yang baik untuk aplikasi tertentu, seperti penyortiran data sensor atau komponen internal dari algoritma penyortiran yang lebih kompleks seperti hybrid sort. Memahami prinsip kerja dan batasan Insertion Sort memungkinkan pengembang untuk memilih algoritma penyortiran yang paling sesuai dengan kebutuhan spesifik proyek mereka. Penting untuk mempertimbangkan ukuran data, tingkat keterurutannya, dan batasan sumber daya saat memilih algoritma penyortiran. Dengan pemilihan yang tepat, kita dapat mengoptimalkan kinerja dan efisiensi sistem kita.