Kategori: Algoritma

Insertion sort adalah algoritma sorting sederhana yang mirip dengan cara kita menyortir kartu dengan tangan.

Algoritma

Algoritma dari insertion sort adalah seperti 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 karena 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 bila jumlah elemennya sedikit, atau hanya sedikit elemen yang belum sesuai urutan.