Pengurutan Penyisipan (Insertion Sort) - Algoritma dan Pemograman

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 <- length(data)-1

    { Menampilkan data yang belum terurut }
    showData(data, batas)

    { Proses pengurutan metode penyisipan }
    for i := 1 to batas do
        { Mengisi nilai sisipan dengan data[i] }
        sisip <- datai

        { Mengisi nilai indeks j }
        j <- i-1

        { Pengurutan menaik }
        while ((j >= 0) and (sisip < dataj)) do
            { Proses pertukaran/pergeseran data }
            dataj+1 <- dataj
            j <- j-1

        { Proses penyisipan data sisip }
        dataj+1 <- sisip

    { Menampilkan data yang sudah terurut }
    showData(data, batas)

2. Bahasa Pascal

program penyisipan;

{ Prosedur menampilkan data }
procedure showData(tab : array of integer; batas : integer);

{ Deklarasi variabel prosedur }
var
    i       : integer;

begin
    for i := 0 to batas do
    begin
        write(tab[i], ' ');
    end;

    writeln();
end;

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

{ Bagian program utama }
begin
    { Memberi masukan ke dalam variabel batas }
    batas := length(data)-1;

    { Menampilkan data yang belum terurut }
    showData(data, batas);

    { Proses pengurutan metode penyisipan }
    for i := 1 to batas do
    begin
        { Mengisi nilai sisipan dengan data[i] }
        sisip := data[i];

        { Mengisi nilai indeks j }
        j := i-1;

        { Pengurutan menaik }
        while ((j >= 0) and (sisip < data[j])) do
        begin
            { Proses pertukaran/pergesaran data }
            data[j+1] := data[j];
            j := j-1;
        end;

        { Proses penyisipan data sisip }
        data[j+1] := sisip;
    end;

    { Menampilkan data yang sudah terurut }
    showData(data, batas);
end.

3. Bahasa C++

#include <iostream>
using namespace std;

// Prosedur menampilkan data
void showData(int tab[], int batas)
{
    // Deklarasi variabel prosedur
    int i;

    for (i = 0; i < batas; i++)
    {
        cout << tab[i] << " ";
    }

    cout << endl;
}

// Bagian program utama
int main()
{
    // Deklarasi variabel utama dan sekaligus memberi nilai pada data
    int i;
    int j;
    int sisip;
    int data[7] = {3, 7, 2, 1, 5, 4, 6};
    int batas;

    // Memberi masukan ke dalam variabel batas
    batas = sizeof(data)/sizeof(data[0]);

    // Menampilkan data yang belum terurut
    showData(data, batas);

    // Proses pengurutan metode penyisipan
    for (i = 0; i < batas; i++)
    {
        // Mengisi nilai sisipan dengan data[i]
        sisip = data[i];

        // Mengisi nilai indeks j
        j = i-1;

        // Pengurutan menaik
        while ((j >= 0) && (sisip < data[j]))
        {
            // Proses pertukaran/pergesaran data
            data[j+1] = data[j];
            j = j-1;
        }

        // Proses penyisipan data sisip
        data[j+1] = sisip;
    }

    // Menampilkan data yang sudah terurut
    showData(data, batas);

    // Mengembalikan nilai
    return 0;
}

4. Bahasa Java

public class Main
{
    // Method menampilkan data
    public static void showData(int tab[], int batas)
    {
        // Deklarasi variabel method
        int i;

        for (i = 0; i < batas; i++)
        {
            System.out.print(tab[i] + " ");
        }

        System.out.println();
    }

    // Bagian program utama
    public static void main(String[]args)
    {
        // Deklarasi variabel utama dan sekaligus memberi nilai pada data
        int i;
        int j;
        int sisip;
        int[] data = {3, 7, 2, 1, 5, 4, 6};
        int batas;

        // Memberi masukan ke dalam variabel batas
        batas = data.length;

        // Menampilkan data yang belum terurut
        showData(data, batas);

        // Proses pengurutan metode penyisipan
        for (i = 0; i < batas; i++)
        {
            // Mengisi nilai sisipan dengan data[i]
            sisip = data[i];

            // Mengisi nlai indeks j
            j = i-1;

            // Pengurutan menaik
            while ((j >= 0) && (sisip < data[j]))
            {
                // Proses pertukaran/pergeseran data
                data[j+1] = data[j];
                j = j-1;
            }

            // Proses penyisipan data sisip
            data[j+1] = sisip;
        }

        // Menampilkan data yang sudah terurut
        showData(data, batas);
    }
}