Dalam dunia programming, penguasaan algoritma adalah sebuah hal penting. Karena algoritma adalah dasar dari segala jenis pemrograman, baik untuk pemrograman Android, Windows, dan lainnya. Pengertian algoritma pemrograman adalah urutan langkah logis tertentu untuk memecahkan suatu masalah. Pengertian lainnya dari algoritma pemrograman adalah urutan langkah-langkah logis penyelesaian masalah yang disusun sistematis.
Dalam algoritma, alur pemikiran dalam menyelesaikan suatu persoalan dituangkan secara tertulis. Algoritma seseorang bisa berbeda dari algoritma orang lain. Sedangkan, alur pemikiran tersebut bisa berupa kalimat, gambar, atau tabel tertentu.
Algoritma sendiri terdiri dari beberapa jenis. Salah satu jenisnya adalah algoritma insertion sort. Fungsi algoritma insertion sort adalah untuk mengurutkan sebuah array data yang tidak terurut agar menjadi sebuah array yang terurut. Algoritma insertion sort adalah algoritma pengurutan yang menggunakan dua buah list untuk proses pengurutannya. dua list tersebut yaitu yaitu sorted list dan unsorted list.
Pada kondisi awal, semua bilangan yang hendak diurutkan berada dalam kondisi “unsorted list”. Lalu, index “0” dari unsorted list dipindahkan ke sorted list. Kemudian berlanjut ke index “1” dan seterusnya. Lalu, index “0” dan “1” yang sudah dipindahkan akan dibandingkan berdasarkan nilai terkecil. Index yang memiliki terkecil itu selanjutnya akan menjadi index 0 atau index paling awal. Begitu juga yang terjadi pada index seterusnya, dimana tiap index yang baru saja dimasukan dari unsorted list ke sorted list akan dibandingkan dengan semua index yang sudah duluan masuk ke sorted list. Proses ini akan berulang sampai semua index yang ada di unsorted list berpindah ke sorted list dan dibandingkan. Barulah kita dapat melihat hasil pengurutan tersebut.
Untuk mempermudah pemahaman Anda, algoritma insertion sort kita analogikan dengan pengurutan kartu. Anggaplah Anda hendak mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang bernilai paling besar. Berikut penganalogiannya:
- Semuanya dimulai dari posisi tangan kosong dan semua kartu masih tersimpan di atas meja. Anggap saja Anda hendak menyusun kartu ke tangan kiri Anda.
- Anda lalu mengambil kartu pertama dari meja dan menyimpannya di tangan kiri.
- Kemudian, Anda mengambil kartu kedua dari meja. Lalu, Anda membandingkan kartu tersebut dengan kartu yang ada di tangan kiri.
- Jika kartu yang baru saja diambil dari meja memiliki nilai yang lebih kecil daripada kartu di tangan kiri, maka kartu tersebut akan diletakan di depan kartu pembanding
- Kartu yang telah dibandingkan akan bergeser mundur.
- Proses ini akan terus berlangsung sampai semua kartu terurut dengan benar sesuai kriteria pengurutannya.
- Setelah semua kartu terurut, satu set kartu yang sudah terurut akan disimpan kembali ke meja.
Berikut adalah contoh algoritma insertion sort jika dituliskan:
Insertion_Sort(A)
- Deklarasi Array A
- Deklarasi Elemen
- Input elemen array A
- Input nilai elemen-elemen array A
- For i=1 sampai i < elemen
- While i > 0
- If A[i-1] > A[i]
- Tukar A[i-1] dengan A[i]
- i-1
- end if
- end while
- end for
Algoritma di atas bisa digambarkan dalam sebuah flowchart. Fungsi flowchart pada pemrograman adalah untuk memudahkan perancangan sebuah program. Dan berikut ini adalah flowchart dari algoritma insertion sort:
Flowchart lainnya untuk bahan latihan bisa Anda lihat di artikel kami seputar contoh flowchart program.
Pada artikel kali ini, kami akan memberikan beberapa contoh algoritma insertion sort. Mari kita simak contoh-contoh berikut ini:
- Contoh 1
Langkah 1. Terdapat array dengan 5 elemen seperti di bawah ini:
Selanjutnya data pada index 0 dan 1 akan dipindahkan ke sorted list. Setelahnya, data pada index 0 dan 1 di sorted list akan dibandingkan untuk mencari index yang memiliki nilai terkecil. Dari data di atas, terlihat bahwa nilai pada index 0 lebih kecil dari nilai index 1. Maka pada sorted list, tidak terjadi perubahan posisi. Hasilnya dapat dilihat pada gambar di bawah ini :
Langkah 2. Data pada index 2 dipindahkan ke sorted list. Lalu, data tersebut dibandingkan dengan data-data pada index 0 dan 1. Pada contoh kali ini, hasilnya data pada index 2 memiliki nilai lebih kecil ketimbang data di index 0 dan 1. Hasilnya, data yang baru masuk sortde list tersebut diposisikan ke index 0 dan data-data sebelumnya bergerak mundur. Hasil komparasinya akan seperti gambar berikut:
Langkah 3. Data pada index 3 masuk ke sorted list dan dibandingkan dengan data-data yang sudah ada di sorted list. Karena nilai data pada index 3 lebih kecil daripada nilai data di index 0 sampai 2, maka data pada index 3 diposisikan ke index 0 dan data-data lainnya bergerak mundur. Jadinya akan seperti berikut:
Langkah 4. Langkah terakhir adalah memasukkan data pada index 4 di unsorted list ke dalam sorted list. Setelah dibandingkan, nilai pada data index 4 lebih kecil ketimbang nilai data pada index 1 sampai 3. Hasilnya, data index 4 akan diposisikan ke index 2 dan data setelahnya akan bergerak mundur. Maka, hasilnya akan seperti gambar di bawah ini:
Dengan hasil tersebut, maka proses pengurutan dengan metode insertion sort sudah selesai.
- Contoh 2
Data awal: [5, 2, 4, 6, 1, 3]. Jumlah index adalah 6, dimulai dari 0 sampai 5. Anggaplah index adalah “I”, dimana untuk setiap proses pengurutan, perbandingan data akan dimulai dari index kedua (dalam hal ini i=1)
Proses I:
i=1, x=1; j=0
x<j à2<5? — true =2, 5, 4, 6, 1, 3
Proses II
i=2, j=1, x=2
x<j à 4<5 — true = 2, 4, 5, 6, 1, 3; j=j-1. Artinya jika proses benar, maka “x=x-1”
x<j à4<2 — false = 2, 4, 5, 6, 1, 3
Proses III
I=3, j=2, x=3
x<j à6<5 — false = 2, 4, 5, 6, 1, 3; j=j-1. Artinya jika sebuah proses bernilai false, maka proses tersebut tidak akan dilanjutkan, karena semua data yang ada di sebelah kiri sudah terurut dengan benar secara otomatis .
Proses IV
i=4, j=3, x=4
x<j à1<6 — true = 2, 4, 5, 1, 6, 3; j=j-1, jika benar maka x=x-1
x<j à 1<5 — true = 2, 4, 1, 5,6, 3; j=j-1, jika benar maka x=x-1
x<j à1<4 — true = 2, 1, 4, 5,6, 3; j=j-1, jika benar maka x=x-1
x<j à 1<2 — true = 1, 2, 4, 5,6, 3
Proses V
i=5, j=4, x=5
x<j à3<6 — true = 1, 2, 4, 5,3, 6 j=j-1, jika benar maka x=x-1
x<j à3<5 — true = 1, 2, 4, 3, 5, 6 j=j-1, jika benar maka x=x-1
x<j à3<4 — true = 1, 2, 3, 4, 5, 6 j=j-1, jika benar maka x=x-1
x<jà3<2 — false = 1, 2, 3, 4, 5, 6 j=j-1
Berikut adalah penerapannya di dalam program menggunakan bahasa pemrograman C++:
#include<iostream>
#include <conio.h>
int main()
{
int data[]={5, 2, 4, 6, 1, 3};
cout<<“sebelum disorting: “;
for(int i=0; i<6; i++)
cout<<data[i] <<“, “;
cout<<endl <<endl;
for(int i=1; i<6; i++)
{
int j=i;
while(data[j]<data[j-1])
{
int tmp=data[j];
data[j]=data[j-1];
data[j-1]=tmp;
j–;
}
}
cout<<“Setelah disorting: “;
for(int i=0; i<6; i++)
cout<<data[i] <<“, “;
getch();
}
Setelah program di atas dieksekusi, maka hasilnya akans seperti gambar di bawah:
- Contoh 3
Contoh algoritma insertion sort dalam sebuah program dengan bahasa pemrograman C#:
Sintaks:
using System;
using System.Text;
namespace tester
{
class Insertion
{
public void InsertionSort()
{
Console.Clear();
Console.WriteLine(“Masukkan Banyak Elemen : “);
/* Deklarasi variabel untuk input jumlah elemen array yg akan diurutkan */
string Input=Console.ReadLine();
int Elements;
if(int.TryParse(Input, out Elements))
{
Elements = Convert.ToInt32(Input);
}
else
{
Console.WriteLine(“Maaf input yang Anda masukkan salah. Silahkan tekan Enter untuk mengulang”);
Console.ReadLine();
InsertionSort();
}
/* Deklarasi array untuk menampung angka-angka yang akan diurutkan dan elemen array
berdasarkan input user (variabel Elements) */
int[] Angka = new int[Elements];
Console.WriteLine(“—————————————————-“);
/* Metode untuk input angka yang akan disimpan pada masing-masing element di Array */
for (int i = 0; i < Elements; i++)
{
Console.WriteLine(“Masukkan angka untuk mengisi elemen ” + i + “:”);
string Input_Temp = Console.ReadLine();
int angka;
if(int.TryParse(Input_Temp, out angka))
{
Angka[i] = Convert.ToInt32(angka);
}
else
{
Console.WriteLine(“Maaf input yang Anda masukkan salah. Silahkan tekan Enter untuk mengulang”);
Console.ReadLine();
InsertionSort();
}
}
/* Metode Insertion Sort */
for(int i=1; i < Elements; i++) { while(i>0)
{
if(Angka[i-1] > Angka[i])
{
int Temp = Angka[i-1];
Angka[i-1] = Angka[i];
Angka[i] = Temp;
i–;
}
else
{
break;
}
}
}
/* Menampilkan hasil pengurutan */
Console.WriteLine(“”);
Console.WriteLine(“Hasil pengurutan nilai : “);
for (int i = 0; i < Elements; i++)
{
Console.WriteLine(“Elemen” + i + “:”);
Console.WriteLine(Angka[i]);
}
}
static void Main(string[] args)
{
Insertion I = new Insertion();
I.InsertionSort();
}
}
}
Hasil eksekusi program:
Sekian artikel kami kali ini seputar contoh algoritma insertion sort. Semoga artikel kami ini dapat menjadi materi pembelajaran Anda untuk belajar programming dasar. Untuk contoh algoritma pemrograman dasar lainnya, Anda bisa membacanya di situs ini.
Sumber gambar: loserbombti.blogspot.co.id
