Sorting : Insertion short dan implementasinya dengan bahasa python

Insertion sort 

       Prinsip algoritma insertion sort pada dasarnya membagi data yang akan diurutkan menjadi dua bagian, satu bagian yang belum diurutkan dan yang satunya lagi sudah diurutkan. Elemen pertama diambil dari bagian list yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari list yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian list yang belum diurutkan.

Langkahnya seperti di bawah ini :

Bandingkan data ke-2 dengan data ke-1, jika data ke-2 lebih kecil maka tukar posisinya, jika tidak biarkan aja.

Data ke-3 dibandingkan dengan data ke-1 dan ke-2, jika data ke-3 lebih kecil kemudian tukar lagi posisinya.

Data ke-4 dibandingkan dengan data ke-3, ke-2, dan 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.


Contoh script dalam Python :
disini saya menggunakan list 100 angka acak

def insert(listData):

    for x in range(len(listData)):

        key = listData[x]

        aw = x

        while aw > 0 and listData[aw-1]<key:

            listData[aw] = listData[aw-1]

            aw -= 1

        listData[aw] = key

        print(listData)

import random,time

c = []

for x in range(100):

    c.append(random.randint(0,100))

start = time.time()

insert(c)

end = time.time()-start

print("Waktu proses : ",end,'detik')

Author : http://widi-skelington.blogspot.com

Share this

Related Posts