Insertion Sort Di Python
Insertion sort yaitu algoritma sorting sederhana yang ibarat dengan cara kita menyortir kartu dengan tangan.
Algoritma
Algoritma dari insertion sort yaitu ibarat berikut
// Sortir arr[] berukuran n
insertion_sort(arr, n)
looping dari i = 1 s/d n - 1
Ambil elemen arr[i[ dan sisipkan pada deret yang sudah berurut arr[0..1-1]
Contoh:
12, 11, 13, 5, 6
Mari kita loop for i = 1 (elemen ke 2 dari array) sampai ke 5 (ukuran array)
i = 1. Karena 11 lebih kecil dari 12, pindahkan 12 dan sisipkan 11 sebelum 13
11, 12, 13, 5, 6
i = 2. 13 tetap di posisinya alasannya yaitu semua elemen A[0…l-1] lebih kecil dari 13
11, 12, 13, 5, 6
i = 3. 5 akan pindah ke depan semua elemen mulai dari 11 sampai 13 akan pindah 1 posisi ke kanan dari posisi sebelumnya.
5, 11, 12, 13, 6
i = 4. 6 akan pindah ke posisi setelah 5, dan elemen dari 11 sampai 13 akan pindah satu posisi ke kanan.
5, 6, 11, 12, 13
# Program insertion sort
# fungsi insertion sort
def insertion_sort(arr):
# traverse dari 1 sampai len(arr)
for i in range(1, len(arr)):
key = arr[i]
# Pindahkan elemen arr[0...i-1], yang lebih besar
# dari key, satu posisi ke kanan
# dari posisi sekarang
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
# testing
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print ("Sorted array: ")
for i in range(len(arr)):
print ("%d" %arr[i])
Output
5 6 11 12 13
Insertion sort cocok digunakan jikalau jumlah elemennya sedikit, atau hanya sedikit elemen yang belum sesuai urutan.