Praktikum 2 Bubble sort, selection sort, insertion sort
MODUL PRAKTIKUM STRUKTUR DATA DAN ALGORITMA BUBBLE SORT, SELECTION SORT, INSERTION SORT Deskripsi Singkat Pada praktikum ke-1, kita telah mempelajari cara untuk menghitung interval waktu untuk 2 metode searching (sekuensial dan binary). Pada praktikum ini kita akan membuat proses sorting (pengurutan) dengan menggunakan 3 algoritma sorting sederhana yaitu bubble sort, selection sort, dan insertion sort. Sorting adalah sebuah teknik pemrograman untuk mengurutkan suatu data. Teknik ini bisa menjadi langkah awal untuk melakukan pencarian karena sebuah pencarian dari data yang telah diurutkan jauh lebih cepat (seperti yang telah anda buktikan pada praktikum ke-1).
Tujuan 1. Membuat method bubbleSort, selectionSort dan insertionSort 2. Menghitung interval waktu untuk bubble sort, selection sort dan insertion sort
Materi 1 : Algoritma Bubble Sort Bubble sort merupakan algoritma sorting yang paling sederhana namun paling lambat. Namun algoritma ini merupakan awal yang baik untuk memahami proses sorting data. Algoritma bubble sort bekerja mengurutkan data dengan membandingkan elemen yang bersebelahan secara berulang dan menukar posisinya jika perlu. Kita akan menggunakan class ArrayTakTerurut pada praktikum 1 dan menambahkan method bubbleSort(). Berikut kode yang perlu ditambahkan. public void bubbleSort() { int out, in; for(out=nElems-1; out>1; out--) // outer loop (backward) for(in=0; in
a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() private void swap(int one, int two) { double temp = a[one]; a[one] = a[two]; a[two] = temp; } Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Praktikum 2 Bubble sort, selection sort, insertion sort
Kemudian buat class baru untuk menguji method bubbleSort() seperti kode program di bawah. public class BubbleSortApp { public static void main(String[] ar) { int maxSize = 100; //ukuran array //mencipta objek arraytakterurut ArrayTakTerurut arrt = new ArrayTakTerurut(maxSize); //masukkan 100 data acak ke dalam arrt for(int i=0; i<maxSize; i++) { int x = 1 + (int) (Math.random() * 1000); arrt.insert(x); } //cetak sebelum diurutkan System.out.println("Data sebelum diurutkan:"); arrt.display(); //lakukan sort dengan bubbleSort arrt.bubbleSort(); //cetak sesudah diurutkan System.out.println("Data sesudah diurutkan:"); arrt.display(); } }
Materi 2 : Algoritma Selection Sort Algoritma selection sort bekerja mengurutkan data dengan meletakkan nilai tertentu pada posisi terakhir secara berulang. Algoritma ini merupakan kombinasi proses sorting dan searching. Berikut kode method selectionSort() yang perlu anda tambahkan ke dalam class ArrayTakTerurut. public void selectionSort() { int out, in, min; for(out=0; out
Praktikum 2 Bubble sort, selection sort, insertion sort
} // end selectionSort()
Kemudian buat class baru untuk menguji method selectionSort() seperti kode program di bawah. public class SelectSortApp { public static void main(String[] ar) { int maxSize = 100; //ukuran array //mencipta objek arraytakterurut ArrayTakTerurut arrt = new ArrayTakTerurut(maxSize); //masukkan 100 data acak ke dalam arrt for(int i=0; i<maxSize; i++) { int x = 1 + (int) (Math.random() * 1000); arrt.insert(x); } //cetak sebelum diurutkan System.out.println("Data sebelum diurutkan:"); arrt.display(); //lakukan sort dengan bubbleSort arrt.selectionSort(); //cetak sesudah diurutkan System.out.println("Data sesudah diurutkan:"); arrt.display(); } }
Materi 3 : Algoritma Insertion Sort Algoritma insertion sort bekerja mengurutkan data dengan menyisipkan nilai tertentu kepada subset list yang terurut secara berulang. Proses kerjanya mirip seperti cara orang menyusun kartu dalam permainan kartu. Berikut kode method insertionSort() yang perlu anda tambahkan ke dalam class ArrayTakTerurut. public void insertionSort() { int in, out; for(out=1; out0 && a[in-1] >= temp) // until one is smaller, { a[in] = a[in-1]; // shift item right, Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Praktikum 2 Bubble sort, selection sort, insertion sort
--in; // go left one position } a[in] = temp; // insert marked item } // end for } // end insertionSort()
Kemudian buat class baru untuk menguji method insertionSort() seperti kode program di bawah. public class InsertSortApp { public static void main(String[] ar) { int maxSize = 100; //ukuran array //mencipta objek arraytakterurut ArrayTakTerurut arrt = new ArrayTakTerurut(maxSize); //masukkan 100 data acak ke dalam arrt for(int i=0; i<maxSize; i++) { int x = 1 + (int) (Math.random() * 1000); arrt.insert(x); } //cetak sebelum diurutkan System.out.println("Data sebelum diurutkan:"); arrt.display(); //lakukan sort dengan bubbleSort arrt.insertionSort(); //cetak sesudah diurutkan System.out.println("Data sesudah diurutkan:"); arrt.display(); } }
LATIHAN 1 Latihan berikut ini digunakan untuk mencari interval waktu perbedaan antara bubble sort, selection sort dan insertion sort. Gunakan class TimeInterval yang telah dibuat pada praktikum 1. Untuk mencari interval waktu ini, kita akan memulai dari array dengan maxSize=100, cek hasilnya untuk masing-masing algoritma sorting (bubble sort, selection sort dan insertion sort). Jika tidak ada perbedaan waktu, naikkan menjadi 1000, cek kembali. Naikkan kembali menjadi 10000, 100000, dan seterusnya hingga tampak perbedaan interval waktu antara ketiga algoritma tersebut. Silakan gunakan tabel di bawah untuk pedoman pencatatan waktunya. Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Praktikum 2 Bubble sort, selection sort, insertion sort
Ukuran array (maxSize) 100 1000 10000 100000 1000000 10000000
Waktu bubbleSort()
Apakah yang dapat anda simpulkan?
SOAL-SOAL 1.
Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Waktu selectionSort()
Waktu insertionSort()
