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.

 

 

 

2 thoughts on “Insertion Sort di Python”

    1. teorinya untuk insertion sort pada umumnya pakai ascending. untuk kebalikannya, bisa diurutkan pakai fungsi sorted atau pakai metode sort list.

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *