Algoritma Insertion Sort Python3

Halo, teman-teman pembaca pada postingan kali ini saya akan membahas salah satu algoritma yang digunakan untuk mengurutkan data numerik. Algoritma pengurutan atau sorting sebenarnya ada banyak jenisnya namun yang akan saya bahas adalah algoritma insertion sort. Algoritma ini tergolong algoritma yang sederhana. Insertion sort adalah algoritma yang membandingkan dua elemen pertama pada array, kemudian membandingkan dengan data pada array berikutnya sampai data tersebut membentuk urutan dari besar ke kecil atau dari kecil ke besar. Algoritma ini seperti kartu yang sedang diurutkan, misalnya kartu pertama digeser ke kedua maka kartu selanjutnya juga ikut mundur.

 Berikut adalah implementasi insertion sort dengan python3

def insertionSort(arr):
    for i in range(len(arr)):
        j=i
        while j > 0 and arr[j] < arr[j-1]:
            arr[j], arr[j-1] = arr[j-1], arr[j]
            j-=1
    return arr

arr = list(map(int, input('Masukkan array: ').split()))
print(insertionSort(arr))

Algoritma tersebut memiliki kompleksitas sebagai berikut:

Time Complexity
Best	O(n)
Worst	O(n2)
Average	O(n2)
Space Complexity	O(1)
Stability	Yes

Demikian pembahasan mengenai algoritma insertion sort semoga bermanfaat apabila ada pertanyaan silahkan tulis di kolom komentar. Terima kasih.