Apa itu insertion sort dan contohnya?

Pengurutan penyisipan [Insertion Sort] adalah metode pengurutan data yang mengambil sebuah data sisipan pada data yang akan diurutkan dan menggeser/mengganti data yang lebih besar atau kecil sesuai dengan jenis pengurutannya, yang dibandingkan dengan data sisipan agar data sisipan berada pada tempat/indeks yang benar. Berikut contoh proses pengurutan metode penyisipan dan ilustrasinya :

Data Awal :
[3, 7, 2, 1, 5, 4, 6]

Perulangan ke-1
Data Sisipan : 7
Perubahan Data : 
[3, 7, 2, 1, 5, 4, 6]

Perulangan ke-2
Data Sisipan : 2
Perubahan Data : 
[3, 7, 7, 1, 5, 4, 6]
[3, 3, 7, 1, 5, 4, 6]
[2, 3, 7, 1, 5, 4, 6]

Perulangan ke-3
Data Sisipan : 1
Perubahan Data : 
[2, 3, 7, 7, 5, 4, 6]
[2, 3, 3, 7, 5, 4, 6]
[2, 2, 3, 7, 5, 4, 6]
[1, 2, 3, 7, 5, 4, 6]

Perulangan ke-4
Data Sisipan : 5
Perubahan Data : 
[1, 2, 3, 7, 7, 4, 6]
[1, 2, 3, 5, 7, 4, 6]

Perulangan ke-5
Data Sisipan : 4
Perubahan Data : 
[1, 2, 3, 5, 7, 7, 6]
[1, 2, 3, 5, 5, 7, 6]
[1, 2, 3, 4, 5, 7, 6]

Perulangan ke-6
Data Sisipan : 6
Perubahan Data : 
[1, 2, 3, 4, 5, 7, 7]
[1, 2, 3, 4, 5, 6, 7]

Berikut adalah contoh pengurutan penyisipan beserta penulisannya dalam bahasa algoritmik dan beberapa bahasa pemograman :

1. Bahasa Algoritmik

{ Prosedur menampilkan data }
procedure showData[tab : array of integer; batas : integer]

{ Deklarasi variabel prosedur }
    i       : integer

    for i := 0 to batas do
        output[tab[i], ' ']

    output['\n']

{ Deklarasi variabel utama dan sekaligus memberi nilai pada data }
    i       : integer
    j       : integer
    sisip   : integer
    data    : array[0..6] of integer = [3, 7, 2, 1, 5, 4, 6]
    batas   : integer

{ Bagian program utama }
    { Memberi masukan ke dalam variabel batas }
    batas