Algoritma
Insertion Sort
Algoritma insertion
sort adalah sebuah algoritma pengurutan sederhana yang membangun array untuk
diurutkan dalam sebuah list yang hampir terurut. Algoritma ini lebih efisien
dari algoritma yang lebih canggih seperti quicksort, heapsort, atau merge
sort. (Erzandi, 2009) Cara kerja insertion sort sebagaimana namanya.
Pertama-tama, dilakukan iterasi, dimana di setiap iterasi insertion sort memindahkan
nilai elemen, kemudian menyisipkannya berulang-ulang sampai ke tempat yang
tepat. Begitu seterusnya dilakukan. Dari proses iterasi, seperti biasa,
terbentuklah bagian yang telah di-sorting dan bagian yang belum.
Pada
Gambar 1 diketahui elemen tabel adalah x. Elemen x akan digeser ke kanan untuk
disisipkan dengan elemen sebelumnya hingga ditemukan nilai elemen yang lebih
kecil. Variasi umum dari insertion sort, yang beroperasi pada array,
dapat digambarkan sebagai berikut:
·
Misalkan ada sebuah fungsi yang kemudian
dimasukkan ke nilai urutan awal array.
·
Pengoperasian dimulai dari urutan yang paling akhir
dan setiap satu elemen akan dibandingkan dengan elemen sebelumnya (x-1) kemudian
bergeser ke kanan hingga menemukan posisi yang tepat.
Berdasarkan
sourcecode algoritma insertion sort di atas terdapat perulangan for
dimana j adalah indeks 2 hingga panjang array A. key adalah variabel
yang menyimpan nilai j dari array A. i adalah lokasi atau indeks yang
berada di sebelah kiri indeks j. Setelah itu masuk ke perulangan while untuk
membandingkan nilai kedua indeks i dan key serta memindahkan nilai hingga ke
lokasi yang tepat. Apabila i lebih besar dari 0 dan A[i] lebih besar dari key,
maka akan dilakukan perpindahan ruang dengan dilakukan penambahan + 1 pada
indeks i. Ini menyatakan bahwa nilai indeks i berpindah ke kanan. Sementara itu
kembali indeks i untuk dilakukan komparasi (perulangan while) lagi. Jika
i – 1 sama dengan 0 maka break, lalu key menempati ruang kosong yang
berada di sebelah kiri.
Pada Gambar 3 berikut adalah contoh
dari simulasi insertion sort:
Sourcode
Insertion Sort beserta perhitungan kompleksitasnya
Berdasarkan
input yang diberikan, running time dari program adalah jumlah
dari setiap langkah yang di-eksekusi sebanyak n kali. Berikut adalah running
time dari algoritma yaitu penjumlahan running time setiap statement
yang di-eksekusi :
Dimana T(n) adalah
running time, n adalah banyaknya eksekusi pada statement, dan tj
adalah banyaknya shift (loncatan) atau perulangan while yang
diberikan.
Best case
Best
case atau kondisi terbaik yaitu dimana semua data telah terurut. Untuk
setiap j = 2,3,…..n, kita dapat menemukan A[i] kurang dari atau sama dengan key
dimana i memiliki nilai inisial (j – 1). Dengan kata lain, ketika i = j – 1,
akan selalu didapatkan key A[i] pada waktu perluangan while berjalan.
Running
time pada best case ini dapat ditunjukkan dengan an + b dimana
konstanta a dan b bergantung pada statement ci. Sehingga T(n) adalah
fungsi liniear dari n.
(𝑛)=𝑎𝑛+𝑏=𝑂(𝑛)
…………………………………(3)
Worst Case
Worst
case atau kondisi terburuk terjadi jika array diurutkan dalam urutan
terbalik yaitu, dalam urutan menurun (besar ke kecil). Dalam urutan terbalik,
selalu ditemukan A[i] lebih besar dari key pada perulangan loop.
Sehingga, harus membandingkan setiap elemen A[j] dengan seluruh urutan elemen
sub-array A[1.....j-1] dan juga tj = j untuk j = 2,3,.... n. Secara
ekuivalen, saat perulangan while keluar disebabkan i telah mencapai indeks 0.
Oleh karena itu, tj = j untuk j = 2,3,...,n dan running time worst case dapat
dihitung menggunakan persamaan sebagai berikut :
Running time pada
worst case ini dapat dinyatakan sebagai 𝑎𝑛2 + 𝑏𝑛
+ , untuk konstanta a, b dan c
bergantung pada statement 𝑐𝑖. Oleh karena
itu, T(n) adalah fungsi kuadrat dari n.
(𝑛)=𝑎𝑛2+𝑏𝑛+𝑐=𝑂(𝑛2)
……………………………..… (5)
Average Case
Average
case terjadi apabila data yang diurutkan acak. Key dalam A[i] adalah kurang
dari setengah elemen dalam A[1…..j-1] dan lebih besar dari setengah lainnya.
Hal ini berarti pada kondisi average, perulangan while harus melalui
setengah jalan melalui subarray A diurutkan [1…j-1] untuk memutuskan
dimana memposisikan key. Ini berarti tj = j/2.
Meskipun running
time average case adalah setengah dari waktu running time worst case,
average case masih memiliki fungsi kuadrat dari n.
𝑻(𝒏)=𝒂𝒏𝟐+𝒃𝒏+𝒄=𝑶(𝒏𝟐).
…………………………….…(6)
Latihan soal dan
berikanlah jawabannya :
1. Show
the results of each pass of InsertionSort applied to the list.
[
7, 3, 9, 4, 2, 5, 6, 1, 8 ]
2. Show
the results of each pass of InsertionSort applied to the list.
[
3, 5, 2, 9, 8, 1, 6, 4, 7 ]
Jawaban no 1 :
Data awal :
7
|
3
|
9
|
4
|
2
|
5
|
6
|
1
|
8
|
Step 1 :
3
|
7
|
9
|
4
|
2
|
5
|
6
|
1
|
8
|
3
|
7
|
9
|
4
|
2
|
5
|
6
|
1
|
8
|
3
|
7
|
9
|
4
|
2
|
5
|
6
|
1
|
8
|
Step 2 :
3
|
4
|
7
|
9
|
2
|
5
|
6
|
1
|
8
|
Step 3 :
2
|
3
|
4
|
7
|
9
|
5
|
6
|
1
|
8
|
Step 4:
2
|
3
|
4
|
5
|
7
|
9
|
6
|
1
|
8
|
Step 5 :
2
|
3
|
4
|
5
|
6
|
7
|
9
|
1
|
8
|
Step 6 :
1
|
2
|
3
|
4
|
5
|
6
|
7
|
9
|
8
|
Step 7:
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
Jawaban no 2 :
Data awal :
3
|
5
|
2
|
9
|
8
|
1
|
6
|
4
|
7
|
Step 1 :
3
|
5
|
2
|
9
|
8
|
1
|
6
|
4
|
7
|
Step 2 :
2
|
3
|
5
|
9
|
8
|
1
|
6
|
4
|
7
|
Step 3 :
2
|
3
|
5
|
9
|
8
|
1
|
6
|
4
|
7
|
Step 4 :
2
|
3
|
5
|
8
|
9
|
1
|
6
|
4
|
7
|
Step 5 :
1
|
2
|
3
|
5
|
8
|
9
|
6
|
4
|
7
|
Step 6 :
1
|
2
|
3
|
5
|
6
|
8
|
9
|
4
|
7
|
Step 7 :
1
|
2
|
3
|
4
|
5
|
6
|
8
|
9
|
7
|
Step 8 :
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
DAFTAR PUSTAKA
Erzandi, Muhammad O. 2007. Algoritma
Pengurutan dalam pemrograman.Bandung : ITB.
Chandrika,K.L.,
Agustin,H.Y., Ni’matul.R., Trias.N.I., (2017), Analisis
Algoritma Insertion Sort Dan Algoritma Pencocokan String Knuth-Morris-Pratt, Jurnal, Teknik Informatika, Universitas
Negeri Malang, Malang.
Komentar
Posting Komentar