Kode Program (Python)

# insertionsort.py
# oleh: HY
from rich.console import Console
from rich.panel import Panel
console = Console(width=45)
langkah = 0
# -------------------------------------
def list_with_key_to_str(l, i) -> str:
   # Menerima list dan indeks
   # Mengembalikan string terformat dari list
   if len(l) > 0 and i > 0:
       s = str(l)
       sl = s[1:len(s)-1].split(", ")
       sl[i-1] = f"[bold bright_red]{sl[i-1]}[/]"
       sl[i] = f"[bold underline gold1]{sl[i]}[/]"
       return "[" + ", ".join(sl) + "]"
   else:
       return "error"
# -------------------------------------
def insertion_sort(data) -> None:
   # Insertion sort teroptimasi
   for i in range(1, len(data)):
       current_elmt = data[i]
       j = i - 1
       while j >= 0 and current_elmt < data[j]:
           data[j + 1] = data[j]
           j -= 1
       data[j + 1] = current_elmt
# -------------------------------------
def insertion_sort_original(data) -> None:
   # Insertion sort original
   # dengan penambahan output
   global langkah
   langkah = 0
   for i in range(1, len(data)):
       console.rule(title = f"(i = {i})", align = "left")
       j = i
       while j > 0:
           langkah += 1
           console.print(f"   Iterasi ke-{langkah:2d}: ",
               end = "", highlight=False)
           console.print(list_with_key_to_str(data, j))
           if data[j-1] > data[j]:
               tmp = data[j]
               data[j] = data[j-1]
               data[j-1] = tmp
           j = j-1
# -------------------------------------
### PROGRAM UTAMA ###
if __name__ == '__main__':
   print()
   data = [5, 8, 9, 3, 4, 7, 1, 2, 6]
   console.print(f"Data: [bold white]{str(data)}[/]")
   print("INSERTION SORT")
   insertion_sort_original(data)
   console.rule()
   console.print(Panel.fit(f"Hasil: [bold white]{str(data)}[/]\n" +
       f"Banyak langkah: [bold white]{langkah}[/]\n" +
       "G(n) = [bold]n(n-1)/2[/] ==> [bold]O(n^2)[/]"))
   print()
### AKHIR PROGRAM ###
 

Pembahasan

Insertion Sort adalah salah satu jenis pengurutan yang sederhana. Urut-urutan langkahnya dapat dianalogikan dengan pengurutan kartu berdasarkan angka/nilai kartu pada sebuah permainan kartu.

Pada program di atas, diberikan dua versi fungsi insertion sort: versi yang sedikit dioptimasi, dan versi original.
Agar dapat lebih menampilkan urut-urutan insertion sort sesuai definisi, maka dipilih algoritma insertion sort yang original.

Terkait dengan kompleksitas algoritma, insertion sort memiliki G(n) = n(n-1)/2, sama dengan algoritma pengurutan sederhana yang lain, yaitu bubble sort. Kompleksitas algoritmanya adalah O(n²).

Contoh hasil eksekusi dapat dilihat pada gambar. Karena output yang cukup panjang, maka hasil tangkapan layar dari eksekusi program dibagi menjadi 2 gambar.