“Analisis Insertion Sort”
A.
Pengertian
Insertion Sort
Insertion
Sort, Sebelum kita membahas Insertion Sort terlebih dahulu kita pelajari apa
itu Sorting ?
Sorting atau pengurutan data adalah
proses yang sering harus dilakukan dalam pengolahan data. Sort dalam hal ini
diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan
urutan tertentu baik urut menaik (ascending) dari nilai terkecil sampai dengan
nilai terbesar, atau urut menurun (descending) dari nilai terbesar sampai
dengan nilai terkecil. Sorting adalah proses pengurutan.
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.
B.
Cara Kerja
Contoh Insertion Sort:
Bagian abu-abu/dua bilangan pertama sekarang dalam
keadaan terurut secara relatif.
Berikutnya, kita perlu menyisipkan bilangan ketiga (4) ke
dalam bagian biru/abu-abu sehingga setelah penyisipan tersebut, bagian
biru/abu-abu tetap dalam keadaan terurut secara relatif;
Caranya:
pertama : Ambil bilangan ketiga (4).
Kedua : Geser bilangan kedua (10) sehingga ada ruang untuk
disisipi.
Ketiga : Sisipkan bilangan 4 ke posisi yang tepat
Sekarang, tiga bilangan pertama sudah terurut secara
relatif dan kita sisipkan bilangan keempat kepada tiga bilangan pertama tsb.
Setelah penyisipan, empat bilangan pertama haruslah dalam keadaan terurut
secara relatif.
Ulangi proses tsb sampai bilangan terakhir disisipkan
Proses Sorting.
Proses Sorting Selesai.
Program Insertion Sort
Hasil Program
C.
Perintah Dasar
C++ dalam Insertion Sort
· #include <stdio.h>
Pada setiap program harus di awali dengan preprocessor directive. preprocessor directive adalah statement program yang di awali dengan tanda # sedangkan include berfungsi sebagai alat pemanggil suatu file header yang telah di sediakan. contoh, file header yang di panggil adalah file stdio.h
· Int main() merupakan fungsi awal untuk memulai sebuah program.
· { …} merupakan sebuah tanda dimana semua yang di ketikkan di dalam lingkup kurung kurung kurawal itu merupakan isi dari program yang di buat.
· Void merupakan prosedur (procedure), fungsi ini tidak mengembalikan nilai keluaran (return output) yang didapat dari hasil proses tersebut , kenapa fungsi ini disebut void secara harfiah berarti kosong.
· Dalam bahasa pemrograman C, perintah printf dipakai untuk menampilkan teks ke layar, yakni salah satu bentuk output. Perintah printf sendiri sebenarnya bukan bagian dari inti bahasa C. Bahasa C tidak mempunyai sarana input dan output bawaan. Perintah printf berasal dari library stdio.h yang ditambahkan ke dalam kode program C. Karena itulah kita harus menulis baris #include <stdio.h> di awal setiap kode program bahasa C yang akan menggunakan perintah printf.
· For, Pernyataan pengulangan FOR berfungsi untuk melakukan pengeksekusian beberapa pernyataan secara berulang-ulang.
· Scanf, Perintah scanf, atau lebih tepatnya function scanf() adalah perintah bahasa C untuk menerima masukan ke dalam program, yakni sebagai sarana input dari pengguna. Dengan menggunakan perintah scanf, kita bisa membuat program yang lebih interaktif, yakni meminta data dari user / pengguna. Data ini nantinya bisa disimpan ke dalam variabel dan diolah lebih lanjut untuk kemudian ditampilkan kembali.
· getch(), Fungsi getch() dan getche() (get character and echo) dipakai untuk membaca sebuah karakter dengan sifat karakter yang dimasukkan tidak perlu diakhiri dengan menekan tombol ENTER, dan karakter yang dimasukan tidak akan ditampilkan di layar. File header yang harus disertakan adalah conio.h. Fungsi getch() dapat digunakan untuk menghentikan proses program secara sementara dan dilanjutkan lagi setelah menekan salah tombol keyboard. Karena itu, dalam program yang sederhana fungsi getch() selalu diletakkan baris akhir dari program.
· While, While adalah salah satu pernyataan yang berfungsi untuk mengulangi pengeksekusian substatement yang dilakukan ketika memiliki nilai benar pada conditional expression. Pernyataan pengulangan mirip seperti pernyataan penyeleksian if, pengeksekusian substatement tergantung pada nilai conditional expression. Tetapi pernyataan While akan terus mengulangi pernyataan tersebut jika conditional expression bernilai 1 (TRUE).
D.
Penjelasan Program
Insertion Sort Ascending
· Dalam pembuatan
Insertion Sort kali ini kita menggunakan 2 File header yaitu stdio.h &
conio.h untuk stdio.h berguna untuk menampilkan fungsi printf() & scanf(),
sedangkan conio.h untuk dapat menampilkan fungsi getche ().
·
Kita masuk ke dalam
fungsi utama program yaitu main().
·
Setelah simbol
statement dibuka, kita masukkan tipe data untuk tipe data int(integer) dengan
variabel L dengan batas sampai 7 . & int dengan variabel i & N yg tidak
diberi batas.
·
Setelah itu kita
definisikan fungsi menggunakan void dengan nama v_insAsc ( void insertion sort
ascending) dengan tipe data int (integer) dengan variabel A mempunyai batas 7
& N yg tidak diberi batas.
·
Agar paham bagian
program yg ingin kita kerjakan, kita berikan komentar/penanda kalau program
dibawahnya adalah program bagian input data array.
·
Selanjutnya program
akan diberi statement atau perintah untuk menampilkan tulisan diantara petik
dua (“) dengan menggunakan perintah printf().
·
Untuk baris ke 13
tentang Banyak Data kita menggunakan perintah scanf() yg didalamnya terdapat
perintah %i yg berarti digunakan untuk memasukkan data bertipe integer, lalu
&N akan menjadi variabel dari masukkan tipe data tersebut.
·
Selanjutnya untuk
blok kode, yg perlu diperhatikan adalah kondisi yang ada didalam kurung setelah
kata for.
·
Kondisi ini akan
menentukan :
o Hitungan akan dimulai dari 0 (i = 0);
o Hitungannya sampai i < N
o Lalu di setiap perulangan I akan ber +1.
·
Variabel i pada for
berfungsi untuk menyimpan nilai hitungan.
·
Selanjutnya program
mencetak Nilai Ke sesuai blok kode & memberi nomor pada Nilai Ke%i setiap
terjadi perulangan, ini terjadi karena rumus , i + 1
·
Selanjutnya Setiap
data yg masuk akan dimasukkan ke dalam ariabel L untuk diproses oleh fungsi
Void v_insAsc. Loop berakhir.
·
Selanjutnya Fungsi
dari v_insAsc akan dipanggil.
·
Mencetak tulisan
data terurut
·
Blok kode sdh
dijelaskan dibagian atas
·
Loop diakhiri
·
Cetak tulisan tekan
enter
·
Selanjutnya menahan
(pause) pada output. Dan akan kembali mengeksekusi setelah kita melakukan
inputan yg akan muncul di dalam window.
·
Proses berjalannya
procedure fungsi dari void v_insAsc. Yang mencari insertion sore ascending.
·
Mempunyai 2 tipe
data awal yaitu variabel A yg mempunyai batasan 7 dan variabel N yg tidak
diberi batas. Dan ditambah kan 3 variabel bertipe data integer di dalam
statement, dengan variabel k, X, i;
Kita masuk ke
operator operasi logika
k=1 : k
bernilai 1
saat k kurang
atau sama dengan N dikurang 1 kita masuk kedalam statement
i sama dengan
k
X sama dengan
A dari variabel i
Apakah i lebih
besar atau sama dengan 1 dan A dengan data i-1 lebih besar dari x
Kita masuk ke
dalam statement A data dari variabel I sama dengan A data dari variabel I
dikurang 1. Maka pernyataan langsug diakhiri.
Dan A variabel
dari data I sama dengan k. Pernyataan pun di akhiri.
