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.