Algoritma Insertion Sort

Pendahuluan

Algoritma Insertion Sort adalah salah satu algoritma penyortiran yang sederhana dan efisien untuk daftar kecil. Algoritma ini bekerja dengan cara membangun urutan yang diurutkan satu per satu, dengan mengambil satu elemen dari daftar dan memasukkannya ke posisi yang tepat dalam daftar yang sudah diurutkan.

Cara Kerja

Diagram di bawah ini menggambarkan cara kerja algoritma Insertion Sort:

Berikut adalah cara kerja Algoritma Insertion Sort untuk mengurutkan daftar [54, 26, 93, 17, 77, 31, 44, 55, 20] seperti pada gambar di atas:

1. Mulai dengan elemen kedua (karena elemen pertama dianggap sudah terurut):
   • Elemen saat ini: 26
   • Bandingkan dengan elemen sebelumnya (54):
     • 26 < 54, maka tukar:
     • Daftar menjadi: [26, 54, 93, 17, 77, 31, 44, 55, 20]
2. Lanjut ke elemen ketiga:
   • Elemen saat ini: 93
   • Bandingkan dengan elemen sebelumnya (54):
     • 93 > 54, jadi tidak ada perubahan:
     • Daftar tetap: [26, 54, 93, 17, 77, 31, 44, 55, 20]
3. Lanjut ke elemen keempat:
   • Elemen saat ini: 17
   • Bandingkan dengan elemen sebelumnya (93):
     • 17 < 93, maka tukar:
     • Daftar menjadi: [26, 54, 17, 93, 77, 31, 44, 55, 20]
   • Bandingkan dengan elemen sebelumnya (54):
     • 17 < 54, maka tukar:
     • Daftar menjadi: [26, 17, 54, 93, 77, 31, 44, 55, 20]
   • Bandingkan dengan elemen sebelumnya (26):
     • 17 < 26, maka tukar:
     • Daftar menjadi: [17, 26, 54, 93, 77, 31, 44, 55, 20]
4. Lanjut ke elemen kelima:
   • Elemen saat ini: 77
   • Bandingkan dengan elemen sebelumnya (93):
     • 77 < 93, maka tukar:
     • Daftar menjadi: [17, 26, 54, 77, 93, 31, 44, 55, 20]
   • Bandingkan dengan elemen sebelumnya (54):
     • 77 > 54, jadi tidak ada perubahan:
     • Daftar tetap: [17, 26, 54, 77, 93, 31, 44, 55, 20]
5. Lanjut ke elemen keenam:
   • Elemen saat ini: 31
   • Bandingkan dengan elemen sebelumnya (93):
     • 31 < 93, maka tukar:
     • Daftar menjadi: [17, 26, 54, 77, 31, 93, 44, 55, 20]
   • Bandingkan dengan elemen sebelumnya (77):
     • 31 < 77, maka tukar:
     • Daftar menjadi: [17, 26, 54, 31, 77, 93, 44, 55, 20]
   • Bandingkan dengan elemen sebelumnya (54):
     • 31 < 54, maka tukar:
     • Daftar menjadi: [17, 26, 31, 54, 77, 93, 44, 55, 20]
   • Bandingkan dengan elemen sebelumnya (26):
     • 31 > 26, jadi tidak ada perubahan:
     • Daftar tetap: [17, 26, 31, 54, 77, 93, 44, 55, 20]
6. Lanjut ke elemen ketujuh:
   • Elemen saat ini: 44
   • Bandingkan dengan elemen sebelumnya (93):
     • 44 < 93, maka tukar:
     • Daftar menjadi: [17, 26, 31, 54, 77, 44, 93, 55, 20]
   • Bandingkan dengan elemen sebelumnya (77):
     • 44 < 77, maka tukar:
     • Daftar menjadi: [17, 26, 31, 54, 44, 77, 93, 55, 20]
   • Bandingkan dengan elemen sebelumnya (54):
     • 44 < 54, maka tukar:
     • Daftar menjadi: [17, 26, 31, 44, 54, 77, 93, 55, 20]
   • Bandingkan dengan elemen sebelumnya (31):
     • 44 > 31, jadi tidak ada perubahan:
     • Daftar tetap: [17, 26, 31, 44, 54, 77, 93, 55, 20]
7. Lanjut ke elemen kedelapan:
   • Elemen saat ini: 55
   • Bandingkan dengan elemen sebelumnya (93):
     • 55 < 93, maka tukar:
     • Daftar menjadi: [17, 26, 31, 44, 54, 77, 55, 93, 20]
   • Bandingkan dengan elemen sebelumnya (77):
     • 55 < 77, maka tukar:
     • Daftar menjadi: [17, 26, 31, 44, 54, 55, 77, 93, 20]
   • Bandingkan dengan elemen sebelumnya (54):
     • 55 > 54, jadi tidak ada perubahan:
     • Daftar tetap: [17, 26, 31, 44, 54, 55, 77, 93, 20]
8. Lanjut ke elemen kesembilan:
   • Elemen saat ini: 20
   • Bandingkan dengan elemen sebelumnya (93):
     • 20 < 93, maka tukar:
     • Daftar menjadi: [17, 26, 31, 44, 54, 55, 77, 20, 93]
   • Bandingkan dengan elemen sebelumnya (77):
     • 20 < 77, maka tukar:
     • Daftar menjadi: [17, 26, 31, 44, 54, 55, 20, 77, 93]
   • Bandingkan dengan elemen sebelumnya (55):
     • 20 < 55, maka tukar:
     • Daftar menjadi: [17, 26, 31, 44, 54, 20, 55, 77, 93]
   • Bandingkan dengan elemen sebelumnya (54):
     • 20 < 54, maka tukar:
     • Daftar menjadi: [17, 26, 31, 44, 20, 54, 55, 77, 93]
   • Bandingkan dengan elemen sebelumnya (44):
     • 20 < 44, maka tukar:
     • Daftar menjadi: [17, 26, 31, 20, 44, 54, 55, 77, 93]
   • Bandingkan dengan elemen sebelumnya (31):
     • 20 < 31, maka tukar:
     • Daftar menjadi: [17, 26, 20, 31, 44, 54, 55, 77, 93]
   • Bandingkan dengan elemen sebelumnya (26):
     • 20 < 26, maka tukar:
     • Daftar menjadi: [17, 20, 26, 31, 44, 54, 55, 77, 93]
   • Bandingkan dengan elemen sebelumnya (17):
     • 20 > 17, jadi tidak ada perubahan:
     • Daftar tetap: [17, 20, 26, 31, 44, 54, 55, 77, 93]

Setelah semua elemen sudah diproses, daftar menjadi terurut: [17, 20, 26, 31, 44, 54, 55, 77, 93]. Inilah cara kerja Algoritma Insertion Sort dalam mengurutkan daftar elemen dengan membandingkan dan menyisipkan elemen pada posisi yang sesuai.

Implementasi Python

Berikut adalah program Python yang mengimplementasikan algoritma Insertion Sort:

def insertion_sort(a_list):
  # Loop dari elemen kedua hingga elemen terakhir dalam daftar
  for index in range(1, len(a_list)):
    # Simpan nilai dari elemen saat ini dan posisi awalnya
    current_value = a_list[index]
    position = index

    # Geser elemen-elemen yang lebih besar dari current_value ke kanan untuk memberi ruang bagi current_value
    while position > 0 and a_list[position - 1] > current_value:
       a_list[position] = a_list[position - 1]
       position = position - 1

    # Masukkan current_value ke posisi yang benar
    a_list[position] = current_value

# Daftar yang akan diurutkan
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]

# Memanggil fungsi insertion_sort untuk mengurutkan a_list
insertion_sort(a_list)

# Mencetak daftar yang sudah diurutkan
print(a_list)

Mari kita lihat bagaimana algoritma ini bekerja langkah demi langkah:

1. Inisialisasi dan Loop Utama:
   • Fungsi insertion_sort menerima sebuah daftar (a_list) sebagai argumen.
   • Loop utama (for index in range(1, len(a_list))) berjalan dari indeks 1 hingga indeks terakhir daftar. Ini menentukan elemen yang akan diproses dalam setiap iterasi.
2. Penyimpanan Nilai dan Posisi Awal:
   • Dalam setiap iterasi, nilai elemen saat ini disimpan dalam current_value, dan posisinya disimpan dalam position.
3. Perbandingan dan Pergeseran Elemen:
   • Selama position lebih besar dari 0 dan elemen di posisi sebelumnya (a_list[position - 1]) lebih besar dari current_value, elemen tersebut digeser ke kanan
   • Proses ini memberi ruang bagi current_value untuk dimasukkan ke posisi yang tepat.
4. Penyisipan Nilai:
   • Setelah menemukan posisi yang benar, current_value dimasukkan ke posisi tersebut:pythonCopy codea_list[position] = current_value
5. Hasil Akhir:
   • Setelah semua iterasi selesai, daftar akan terurut dalam urutan menaik.
   • Daftar yang diberikan ([54, 26, 93, 17, 77, 31, 44, 55, 20]) setelah diurutkan akan menjadi: [17, 20, 26, 31, 44, 54, 55, 77, 93].

Program di atas adalah implementasi dasar dari algoritma Insertion Sort yang bekerja dengan kompleksitas waktu rata-rata O(n^2) dan kompleksitas waktu terbaik O(n) ketika daftar sudah terurut. Algoritma ini sangat efisien untuk daftar kecil atau hampir terurut, karena tidak memerlukan perbandingan dan pergeseran yang banyak.