Apa itu insertion sort dan contohnya?
|
Insertion Sort Show Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort. Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang "tepat" untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya ang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sorting disebut sebagai "pass"), dengan indeks dimulai dari 0. Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya. Ini hasilnya...  Ini Script/Codenya... Sengaja codenya saya kasih gambar agar kalian mengetik, karena seorang programer harus bisa ngetik ^^. Semoga bermanfaat 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 Pascalprogram 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 4. Bahasa Javapublic 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);
}
}
Apa itu insertion sort beserta contohnya?Insertion Sort merupakan sebuah teknik pengurutan dengan cara membandingkan dan mengurutkan dua data pertama pada array, kemudian membandingkan data para array berikutnya apakah sudah berada di tempat semestinya. Algorithma insertion sort seperti proses pengurutan kartu yang berada di tangan kita.
Apa yg dimaksud insertion sort?3.Insertion Sort
Algoritma insertion sort merupakan suatu metode pengurutan data dengan melakukan penempatan setiap elemen data pada posisinya dengan membandingkan dengan data-data yang telah ada.
Bagaimana cara kerja dari insertion sort?Insertion sort bekerja seperti banyak orang yang sedang mengurutkan kartu di tangan. Dimulai dari tangan kiri yang kosong dan kartunya tertumpuk di meja. Selanjutnya kita ambil satu persatu kartu di meja dan diletakkan di tangan kiri dengan posisi yang benar (terurut).
Apa perbedaan selection sort dan insertion sort?Metode selection sort menggunakan prinsip pertukaran elemen dalam proses sorting, sedangkan metode insertion sort menggunakan prinsip geser dan sisip elemen dalam proses sorting [Munir, 2011].
|
