Menghitung Inversion Pada Barisan Dengan Menggunakan Modifikasi Bubble Sort, Insertion Sort, dan Merge Sort M Iqbal Tawakal - 0706271954
Abstract
Jumlah inversion memiliki nilai maksimal pada sebuah baris bilangan ketika barisan Paper ini akan menjelaskan mengenai cara tersebut terurut terbalik, dan nilainya nol menghitung inversion dengan menggunakan ketika barisan tersebut terurut. Contoh: beberapa algoritma sorting yang dimodi2 4 3 5 1 fikasi sehingga bisa untuk menghitung jumlah inversion di dalam sebuah baris bi- Pada barisan bilangan di atas, terdapat langan. Algoritma sorting yang dimod- 5 buah inversion. Inversion terjadi pada ifikasi adalah bubble sort, insertion sort, pasangan bilangan (2,1), (4,3), (4,1), (3,1), dan merge sort. Ketiga algoritma itu dan (5,1). akan diujikan untuk menghitung jumlah inversion pada beberapa list dengan panjang yang berbeda-beda untuk kemudian Definisi Masalah dibandingkan sehingga dapat diketahui alInputnya adalah sebuah barisan bilangan goritma terbaik. yang elemen-elemennya unik satu sama lain. Output adalah sebuah bilangan jumlah inversion yang terjadi pada barisan biLatar Belakang langan tersebut. Inversion adalah kondisi pada sebuah barisan bilangan yang terjadi ketika sebuah bilangan yang letaknya lebih kiri namun memiliki nilai lebih besar dari bilangan di sebelah kanannya. Misalkan A[1..n] adalah barisan/list dari n buah angka yang berbeda, jika i < j dan A[i] > A[j], maka antara A[i] dengan A[j] terjadi inversion. Besarnya nilai inversion bisa menjadi indikator seberapa acaknya sebuah baris bilangan.
Penjelasan Algoritma Untuk menghitung inversion pada paper ini algoritma yang digunakan adalah modifikasi dari algoritma bubble sort, insertion sort, dan merge sort. Modifikasi yang dilakukan pada bubble sort adalah ditambahkan sebuah variabel untuk menghitung berapa kali dilakukan pertukaran, karena 1
jika terjadi pertukaran ketika sorting maka akan dimasukkan ke dalam sub barisan sedapat dipastikan kalau itu adalah kondisi belah kiri yang sudah terurut. inversion. Pseudo code-nya Modifikasi yang dilakukan pada merge sort adalah pada bagian merge-nya. Letak INV-BUBBLE-SORT (A) perubahannya adalah ketika dilakukan per1 inv := 0 bandingan antara nilai yang ditunjuk oleh 2 FOR i:= 0 TO length[A]-1 pointer kiri yang menunjuk elemen terke3 DO FOR j:= 0 TO length[A]-2 cil yang masih ada di sublist kiri dengan 4 DO IF A[j] > A[j+1] THEN pointer kanan yang menunjuk elemen terke5 temp := A[j] cil yang ada di sublist kanan. Jika nilai 6 A[j] := A[j+1] yang ditunjuk pointer kiri lebih besar dari 7 A[j+1] := temp yang ditunjuk pointer kanan, maka terjadi 8 inv := inv + 1 inversion. Nilai inversion-nya ditambah se9 END banyak 1 plus semua sisa elemen di sebelah 10 END kanan sublist kiri. Pseudo code-nya 11 return inv INV-MERGE-SORT(A, p, r) 1 if p < r 2 then q <- floor (p+r)/2 3 a := INV-MERGE-SORT(A,p,q) 4 b := INV-MERGE-SORT(A,q+1,r) 5 c := INV-MERGE(A,p,q,r) 6 return a+b+c 7 else 8 return 0
Modifikasi yang dilakukan pada insertion sort adalah menghitung sejauh mana setiap nilai digeser ke kanan ketika melakukan insertion, karena jika suatu elemen masih digeser ke kanan berarti terjadi kondisi inversion di sana. Pseudo code-nya
INV-INSERTION-SORT(A) 1 inv := 0; 2 FOR j := 2 TO length[A] INV-MERGE(A, p, q, r) 3 DO key := A[j] 1 n1 <- q-p+1; n2 <- r-q; inv <- 0 4 i := j-1; //create L[1..n1+1] and R[1..n2+1] 5 WHILE i > 0 and A[i] > key 2 3 for i <- 1 to n1 do L[i] <- A[p+i-1] 6 DO A[i+1] := A[i]; 4 for j <- 1 to n2 do R[j] <- A[q+j] 7 i := i-1; 5 L[n1+1] <- inf; R[n2+1] <- inf 8 inv := inv + 1; 6 i <- 1; j <- 1 9 END 7 for k <- p to r 10 A[i+1] := key 8 do if L[i] < R[j] 11 END 9 then A[k] <- L[i] 12 return inv; 10 i <- i + 1 Jika dibandingkan algoritma aslinya, pada 11 else A[k] <- R[j] modifikasi ini cukup ditambahkan incre- 12 j <-j + 1 ment ke sebuah variabel setiap terjadi 13 inv <- inv + (length(L)-i-1) pergeseran untuk meletakkan elemen yang 14 end 2
15
Hasil percobaan dapat Waktu dalam sekon. n Bubble 1000 0.002371 10000 0.02566 100000 19.58041 1000000 201
return inv
Jika dibandingkan dengan algoritma aslinya, algoritma modifikasi ini ditambahkan baris untuk menambah nilai variabel inv jika terjadi inversion dengan sebanyak elemen yang masih terdapat di sublist kiri. Karena setelah pemanggilan merge-sort, antar elemen dalam sublist yang sama pasti terurut, maka semua elemen yang ada di sebelah kanan elemen yang sekarang ditunjuk oleh pointer kiri nilainya pasti lebih besar dibandingkan elemen yang sedang ditunjuk itu. Akibatnya, pasti terjadi inversion untuk semua elemen di kanan. Karena itu cukup ditambahkan sebanyak elemen yang ada di sublist kiri, tidak perlu diperiksa satu-satu perelemennya.
dilihat di tabel. Insertion Merge 0.000633 0.0008269 0.00736 0.006524 0.214274 0.011369 22.16636 0.152429
Analisis Dari hasil percobaan penggunaan beberapa algoritma sorting yang sudah dimodifikasi untuk menghitung inversion, terlihat bahwa waktunya mengikuti kompleksitas dari algoritma sorting-nya. Bubble sort yang kompleksitas waktunya O(n2 ) performanya kalah dibandingkan insertion sort yang juga sama-sama O(n2 ) namun memiliki implementasi lebih efisien. Tetapi keduanya dibatasi batasan yang dimiliki oleh algoritma sorting by comparison yang perbandingannya dilakukan side by side (dengan angka disebelahnya). Sedangkan merge sort tidak terkena batasan itu, dan kompleksitasnya lebih bagus yaitu O(nlogn). Sehingga untuk perhitungan inversion dengan memakai merge sort jauh lebih cepat dibandingkan algoritma sorting lainnya, terutama untuk jumlah data yang banyak. Hal lain yang membuat merge sort lebih cepat dalam hal menghitung inversion adalah tidak perlu dibandingkan dengan semua elemen untuk mengetahui apakah terjadi inversion.
Percobaan Untuk percobaan perbandingan performa, semua algoritma akan diuji dengan beberapa test case. Inputnya adalah barisan bilangan yang semua elemennya unik dengan panjang bervariasi mulai dari 100, 1000, 10000, dan 100000. Contoh input dengan panjang 100: 96, 90, 10, 20, 67, 28, 25, 4, 84, 48, 93, 19, 54, 3, 14, 11, 2, 59, 92, 22, 24, 51, 70, 31, 77, 64, 99, 1, 23, 72, 29, 85, 6, 91, 98, 61, 73, 38, 62, 36, 81, 58, 9, 68, 35, 71, 42, 76, 7, 66, 78, 16, 74, 63, 52, 53, 95, 75, 45, 17, 30, 86, 15, 21, 8, 83, 12, 27, 39, 94, 37, 65, 82, 47, 60, 18, 49, 50, 87, 32, 56, 33, 13, 40, 88, 41, 89, 44, 79, 97, 100, 43, 34, 26, 46, 57, 80, 55, 69, 5 Jumlah inversion pada barisan tersebut adalah 2315.
Kesimpulan Inversion dapat dihitung dengan melakukan modifikasi terhadap beberapa algoritma sorting, dan kompleksitas penghitungannya mengikuti dari algoritma sorting mana 3
yang dipakai. Dalam paper ini, algoritma merge sort mengungguli algoritma bubble sort dan insertion sort dalam hal menghitung inversion.
Referensi Cormen, Thomas H., Leiserson, Charles E., and Rivest, Ronald L.: Introduction To Algorithm, Second Edition. MIT Press, Massachusetts (2001).
Lampiran - Source Code Program
4
import java.util.List; import java.util.ArrayList; import java.util.Date; public class DAA { public static void main(String[] args) int[] testcase = 100, 1000, 10000, 100000; for(int i=0; i
public static void cetak(int[] li) for(int i=0; i
list = new ArrayList(); for(int i=1; i<=n; i++) list.add(i);
5
for(int i=0; i
public static int invbubblesort(int[] A) int inversion = 0; for(int i=0; i A[j+1]) int temp = A[j]; A[j] = A[j+1]; A[j+1] = temp; inversion++;
return inversion; public static int invinsertionsort(int[] A) int inversion = 0; for(int j=1; j=0 && A[i] > key) A[i+1] = A[i]; i--; inversion++; A[i+1] = key; return inversion; public static int invmergesort(int[] A) return mergesort(A,0,A.length-1); public static int mergesort(int[] A, int p, int r) if(p < r) int q = (p+r)/2; 6
int a = mergesort(A,p,q); int b = mergesort(A,q+1,r); int c = merge(A,p,q,r); return a+b+c; return 0; public static int merge(int[] A, int p, int q, int r) int n1 = q-p+1, n2 = r-q; int inversion = 0; int[] L = new int[n1+2]; int[] R = new int[n2+2]; for(int i=1; i<=n1; i++) L[i] = A[p+i-1]; for(int j=1; j<=n2; j++) R[j] = A[q+j]; L[n1+1] = Integer.MAX_VALUE; R[n2+1] = Integer.MAX_VALUE; int i = 1, j = 1; for(int k=p; k<=r; k++) if(L[i] < R[j]) A[k] = L[i]; i++; else A[k] = R[j]; j++; int temp = L.length-i-1; inversion += temp;
return inversion; }
7
