Insertion Sort di Python

 

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.