Insertion Sort

Definisi

Insertion Sort adalah algoritma pengurutan yang membandingkan 2 elemen data pertama lalu mengurutkannya kemudian mengecek elemen data berikutnya satu persatu dan membandingkan elemen data yang telah diurutkan.

Ilustrasi

Algoritma

1. Bandingkan data ke-2 dengan data ke-1. Jika data ke-2 lebih kecil maka tukar posisinya, jika tidak maka biarkan saja.
2. Data ke-3 dibandingkan dengan data ke-1 dan data ke-2. Jika data ke-3 lebih kecil kemudian ditukar lagi posisinya.
3. Data ke-4 dibandingkan dengan data ke-3,ke-2,ke-1. Jika data ke-4 lebih kecil dari ketiganya maka letakkan data ke-4 ke posisi paling depan. Begitu seterusnya sampai tidak ada lagi data yang bisa dipindahkan. 

Kode Program

def insertion(alist):
    for i in range (1,len(alist)):
        nilai = alist[i]
        posisi = i
        while posisi>0 and alist[posisi-1]> nilai:
            alist[posisi] = alist[posisi-1]
            posisi=posisi-1
        alist[posisi]=nilai
        print(alist)

data=[24,56,32,77,90,12,17,30]

insertion(data)