Insertion Sort Algoritma Sorting untuk Pemula

Insertion Sort: Algoritma Sorting Sederhana untuk Pemula

Insertion Sort, atau pengurutan sisip, adalah algoritma pengurutan sederhana yang bekerja dengan cara menyisipkan elemen-elemen ke posisi yang tepat dalam sub-array yang sudah terurut. Bayangkan Anda sedang bermain kartu remi dan ingin menyusun kartu di tangan Anda. Anda mengambil satu kartu pada satu waktu dan memasukkannya ke posisi yang benar di antara kartu-kartu yang sudah terurut. Prinsip inilah yang mendasari cara kerja Insertion Sort. Algoritma ini sangat intuitif dan mudah dipahami, membuatnya menjadi pilihan yang baik untuk pemula yang baru belajar tentang algoritma pengurutan. Walaupun kurang efisien dibandingkan algoritma pengurutan yang lebih canggih seperti Merge Sort atau Quick Sort untuk dataset besar, Insertion Sort memiliki beberapa keunggulan dalam situasi tertentu.

Bagaimana Cara Kerja Insertion Sort?

Insertion Sort bekerja dengan membagi array menjadi dua bagian: sub-array yang sudah terurut (di awal array) dan sub-array yang belum terurut (sisa array). Pada setiap iterasi, Insertion Sort mengambil elemen pertama dari sub-array yang belum terurut dan menyisipkannya ke posisi yang tepat dalam sub-array yang sudah terurut.

Mari kita ilustrasikan dengan contoh: Array [5, 2, 4, 6, 1, 3].

1. Iterasi 1: Sub-array terurut: [5]. Sub-array belum terurut: [2, 4, 6, 1, 3]. Kita ambil 2. Karena 2 < 5, kita sisipkan 2 sebelum 5. Array menjadi: [2, 5, 4, 6, 1, 3].
2. Iterasi 2: Sub-array terurut: [2, 5]. Sub-array belum terurut: [4, 6, 1, 3]. Kita ambil 4. Karena 4 berada di antara 2 dan 5, kita sisipkan 4 di antara keduanya. Array menjadi: [2, 4, 5, 6, 1, 3].
3. Iterasi 3: Sub-array terurut: [2, 4, 5]. Sub-array belum terurut: [6, 1, 3]. Kita ambil 6. Karena 6 > 5, kita sisipkan 6 setelah 5. Array menjadi: [2, 4, 5, 6, 1, 3].
4. Iterasi 4: Sub-array terurut: [2, 4, 5, 6]. Sub-array belum terurut: [1, 3]. Kita ambil 1. Karena 1 adalah elemen terkecil, kita sisipkan 1 di awal array. Array menjadi: [1, 2, 4, 5, 6, 3].
5. Iterasi 5: Sub-array terurut: [1, 2, 4, 5, 6]. Sub-array belum terurut: [3]. Kita ambil 3. Karena 3 berada di antara 2 dan 4, kita sisipkan 3 di antara keduanya. Array menjadi: [1, 2, 3, 4, 5, 6].

Setelah semua iterasi selesai, array akan terurut.

Implementasi Kode Insertion Sort (Python):

Berikut adalah contoh implementasi Insertion Sort dalam bahasa Python:

def insertion_sort(arr):
  """
  Mengurutkan array menggunakan algoritma Insertion Sort.

  Args:
    arr: Array yang akan diurutkan.

  Returns:
    Array yang sudah diurutkan.
  """
  for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
      arr[j + 1] = arr[j]
      j -= 1
    arr[j + 1] = key
  return arr

# Contoh penggunaan
angka = [5, 2, 4, 6, 1, 3]
angka_terurut = insertion_sort(angka)
print(f"Array yang belum diurutkan: {angka}")
print(f"Array yang sudah diurutkan: {angka_terurut}")

Kode ini bekerja dengan mengulang melalui array, mulai dari elemen kedua. Pada setiap iterasi, elemen saat ini (key) dibandingkan dengan elemen-elemen di sub-array yang sudah terurut. Jika elemen saat ini lebih kecil dari elemen-elemen di sub-array yang sudah terurut, elemen-elemen tersebut digeser ke kanan untuk membuat ruang bagi elemen saat ini. Elemen saat ini kemudian disisipkan ke posisi yang tepat.

Kompleksitas Waktu dan Ruang

Kompleksitas waktu Insertion Sort bergantung pada keadaan awal array.

• Kasus Terbaik (Best Case): Jika array sudah terurut, Insertion Sort hanya perlu melakukan satu perbandingan untuk setiap elemen. Dalam kasus ini, kompleksitas waktunya adalah O(n), di mana n adalah jumlah elemen dalam array.
• Kasus Rata-rata (Average Case): Dalam kasus rata-rata, Insertion Sort perlu melakukan sekitar n/2 perbandingan dan pergeseran untuk setiap elemen. Dalam kasus ini, kompleksitas waktunya adalah O(n^2).
• Kasus Terburuk (Worst Case): Jika array terurut secara terbalik, Insertion Sort perlu melakukan n perbandingan dan pergeseran untuk setiap elemen. Dalam kasus ini, kompleksitas waktunya adalah O(n^2).

Kompleksitas ruang Insertion Sort adalah O(1), karena algoritma ini hanya membutuhkan ruang tambahan yang konstan untuk menyimpan variabel-variabel sementara. Ini berarti Insertion Sort adalah algoritma in-place, yang berarti ia mengurutkan array tanpa memerlukan ruang tambahan yang signifikan.

Kapan Sebaiknya Menggunakan Insertion Sort?

Meskipun Insertion Sort memiliki kompleksitas waktu O(n^2), ia memiliki beberapa keunggulan yang membuatnya cocok untuk situasi tertentu:

• Ukuran Array Kecil: Untuk array dengan ukuran kecil (misalnya, kurang dari 20 elemen), Insertion Sort seringkali lebih cepat daripada algoritma pengurutan yang lebih canggih seperti Merge Sort atau Quick Sort. Hal ini disebabkan overhead tambahan yang terkait dengan algoritma-algoritma yang lebih canggih.
• Array Hampir Terurut: Jika array hampir terurut, Insertion Sort dapat mengurutkannya dengan sangat cepat. Hal ini karena Insertion Sort hanya perlu melakukan sedikit perbandingan dan pergeseran untuk setiap elemen. Dalam kasus ini, kinerjanya mendekati O(n).
• Algoritma Online: Insertion Sort adalah algoritma online, yang berarti ia dapat mengurutkan data saat data tersebut diterima. Hal ini menjadikannya cocok untuk aplikasi di mana data diterima secara bertahap, seperti dalam sistem streaming data.
• Implementasi Sederhana: Insertion Sort sangat mudah diimplementasikan dan dipahami, membuatnya menjadi pilihan yang baik untuk pemula atau untuk situasi di mana kode harus mudah dibaca dan dipelihara.

Alternatif untuk Insertion Sort

Untuk dataset yang lebih besar, algoritma pengurutan lain biasanya lebih efisien daripada Insertion Sort. Beberapa alternatif yang populer meliputi:

• Merge Sort: Memiliki kompleksitas waktu O(n log n) dalam semua kasus (terbaik, rata-rata, dan terburuk). Ini adalah algoritma divide-and-conquer yang stabil.
• Quick Sort: Memiliki kompleksitas waktu rata-rata O(n log n), tetapi kompleksitas waktu terburuknya adalah O(n^2). Biasanya lebih cepat daripada Merge Sort dalam praktiknya, tetapi kurang stabil.
• Heap Sort: Memiliki kompleksitas waktu O(n log n) dalam semua kasus dan merupakan algoritma in-place.
• Radix Sort: Bukan algoritma berbasis perbandingan, dan dapat mengurutkan data dalam waktu O(nk), di mana n adalah jumlah elemen dan k adalah panjang kunci terpanjang. Sangat efisien untuk data dengan rentang nilai yang terbatas.

Pilihan algoritma pengurutan terbaik tergantung pada karakteristik data dan persyaratan aplikasi. Pertimbangkan ukuran dataset, keadaan awal data (misalnya, apakah hampir terurut), dan kebutuhan akan stabilitas dan penggunaan memori.

Kesimpulan

Insertion Sort adalah algoritma pengurutan yang sederhana dan intuitif yang mudah dipahami dan diimplementasikan. Meskipun kurang efisien dibandingkan algoritma pengurutan yang lebih canggih untuk dataset besar, Insertion Sort memiliki keunggulan dalam situasi tertentu, seperti untuk array kecil, array yang hampir terurut, dan dalam aplikasi online. Pemahaman tentang Insertion Sort adalah langkah penting dalam mempelajari algoritma pengurutan, dan dapat memberikan dasar yang kuat untuk memahami algoritma pengurutan yang lebih kompleks. Selanjutnya, cobalah mengimplementasikan algoritma pengurutan ini sendiri dengan berbagai bahasa pemrograman untuk memperdalam pemahaman Anda. Apakah Anda akan menggunakan Insertion Sort untuk menyelesaikan masalah pengurutan Anda berikutnya? Pertimbangkan baik-baik sebelum mengambil keputusan!