Implementasi Algoritma Branch & Bound

Nama : Armelia Luvita Sari

Npm   : 203120157

Kelas  : IF 20B   

Implementasi Algoritma Branch & Bound Algoritma Branch and Bound 

Algoritma Branch and Bound

Sebagaimana pada algortima runut-balik, algoritma Branch & Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang Solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status. Pembentukan pohon ruang status pada algoritma B&B berbeda dengan pembentukan pohon pada algoritma runutbalik. Bila pada algoritma runut-balik ruang solusi dibangun secara Depth-First Search(DFS), maka pada algoritma B&B ruang solusi dibangun dengan skema Breadth-First Search (BFS). 

Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost). Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound). Pada prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan. 

Fungsi heuristik untuk menghitung taksiran nilai tersebut dinyatakan secara umum sebagai : (i) = (i) + (i) yang dalam hal ini,

(i) = ongkos untuk simpul i 

(i) = ongkos mencapai simpul i dari akar 

(i) = ongkos mencapai simpul tujuan dari simpul akar i (perkiraan) Nilai digunakan untuk mengurutkan pencarian. Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki  minimum (Simpul-E). Strategi memilih simpul-E seperti ini dinamakan strategi pencarian berdasarkan biaya terkecil (least cost search). 

1. Persoalan Knapsack  seorang pedagang keperluan rumah tangga keliling harus memilih barang-barang yang akan dijual setiap harinya dengan batas daya angkut gerobak yang dimilikinya. Untuk mempermudah, kita misalkan pedagang keliling tersebut hanya memiliki 4 jenis barang untuk dijual dengan berat dan keuntungan penjualan yang berbeda-beda untuk tiap jenisnya.  

Gerobak yang akan dipakai untuk mengangkut barang-barang tersebut hanya mampu menampuk beban seberat 16 kg. Berikut merupakan tebel penggambaran beratdan keeuntungan yang akan diperoleh untuk tiap penjualan barang tersebut. 

2. Persoalan Knapsack dari tiap tiap simpul anak untuk dapat menentukan simpul mana yang kelak akan dibangkitkan yaitu simpul dengan cost tertinggi dalam penelusuran pohon unutk mencapai solusi dari permasalahan ini. 

Dalam permasalahan ini, kita akan mencari simpul-simpul yang akan membawa kita pada keuntungan terbesar oleh karena itu urutan pembangkitan simpul akan ditentukan oleh simpul mana yang memiliki cost tertinggi. 

Cost dari tiap simpul akan ditentukan dengan: 

(i) = (i) + (i) yang dalam hal ini, 

(i) = cost untuk simpul i 

(i) = cost untuk sampai ke simpul I, dalam hal ini merupakan keuntungan dari simpul akar ke simpul i (i) = cost dari simpul i untuk sampai ke simpul tujuan, dalam hal ini dapat diperoleh dengan menggunakan  rumus : (P/W)max * daya angkut yang tersisa 

pada tahap awal kita akan melakukan perhitungan dengan menggunakan rumus diatas untuk memperoleh batas awal atau akar dari pohon yang juga merupakan simpul pertama. Pada keadaan ini, batas dihitung dengan pemikiran bahwa belum ada satupun barang yang dimasukan kedalam alat pengangkut maka kita dapat memilih 6 sebagai (P/W) terbesar karena belumada satu barangpun yang dimasukan kedalam alat pengangkut dan kapasitas daya angkutpun masih utuh yaitu seberat 16 kg. 

(i) = (i) + (i) 

(1) = keuntungan yang diperoleh sampai disimpul awal + (P/W)max * daya angkut yang tersisa = 0 + 6 * = 96 

Maka kita memperoleh 96 batas awal atau cost dari simpul awal. 

Bangkitkan simpul-simpul anak dari akar pohon yaitu dengan membangkitkan simpul 1, simpul 2, simpul 3 dan simpul 4 sebagai gambaran dari 4 pilihan barang yang akan dimasukan pertama kali pada alat pengangkut dengan x1 merupakan keuntungan yang akan diperoleh pada penjualan tiap barang tersebut. Kemudian kita akan menghitung cost dari tiap simpul anak yang hidup dan juga kelayakannya untuk tetap hidup atau harus dibunuh. Dalam hal ini, simpul yang jumlah dari lintasannya tidak bisa lagi dibangkitkan (jika ditambah barang lagi kedalam alat pengangkut maka beratnya akan melebihi daya angkut) akan dibunuh. 

(2) = 12 + 5*(16-2) = 82 

(3) = 15 + 6*(16-5) = 81 

(3) = 50 + 6*(16-10)=86 

(4) = 10 + 6*(16-5)=76 

Dari simpul-simpul yang telah dibangkitkan dan dihitung cost nya, maka diperoleh bahwa simpul 4 lah yang memiliki cost tertinggi oleh karena itu maka simpul 4 akan di perluas lagi. Simpul 6 ,7,8 akan dibangkitkan sebagai perluasan dari simpul 4 dengan barang yang mungkin dimasukan kedalam alat pengangkut adalah barang ke 1,2 dan 4. kemudian kita akan mengkitung cost dari simpul 6,7dan 8. 

(6) = (50+12) + 3*(16-10-2) = 74 

(7) = (50+15) + 6*(16-10-5) = 71 

(8) = (50+10) + 6*(16-10-5) = 66 

Jangan Lupa Kunjungi Link di Bawah ini : 

https://www.teknokrat.ac.id/ 

http://ftik.teknokrat.ac.id/ 

Implementasi algoritma divide and conquer pada sorting dan searching

Nama    : Armelia Luvita Sari

Npm   : 20312057

Kelas   : IF20B

Implementasi Algoritma Divide And Conquer Pada Sorting dan Searching

Komputer pada awalnya diciptakan sebagai perangkat untuk melakukan kalkulasi secara otomatis dan akurat. Meskipun awalnya hanya berfokus pada kalkukasi numerik, komputer modern yang dijumpai sekarang telah melakukan kalkulasi pada banyak hal, seperti teks ataupun gambar. Berbagai kalkulasi dan analisa yang dilakukan komputer biasanya diimplementasikan melalui perangkat lunak. Dengan semakin besarnya ruang lingkup hal-hal yang dilakukan oleh komputer, perangkat lunak yang dikembangkan juga menjadi semakin kompleks. Algoritma, sebagai bagian dari perangkat lunak yang melakukan pemrosesan, juga memerlukan berbagai teknik baru. Misalkan, untuk menghitung total jumlah dari bilangan-bilangan yang ada di dalam sebuah list, kita dapat menggunakan perulangan sederhana.

Selanjutnya kita akan membahas mengenai Algoritma Divide and Conquer, Algoritma Divide and Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent, dan akhirnya menggabungkan solusi masing-masing upa-masalah sehingga menjadi solusi dari masalah semula.

Sebuah algoritma divide and conquer (selanjutnya disebut dengan D&C) memiliki tiga langkah, yaitu:

• Divide (Memecah) pada langkah ini kita memecahkan masalah atau data ke dalam bentuk yang sama, tetapi dalam ukuran yang lebih kecil. Pemecahan langkah biasanya dilakukan dengan menggunakan algoritma rekursif, sampai ukuran data menjadi sangat kecil dan dapat diselesaikan dengan algoritma sederhana.
• Conquer (Menaklukkan) dalam langkah ini kita mencoba menyelesaikan masalah atau data yang telah dipecahkan pada langkah pertama, dengan menggunakan algoritma sederhana.
• Combine (Menggabungkan) setelah menjalankan langkah conquer, tentunya kita harus menggabungkan kembali hasil dari masing-masing pecahan yang ada, untuk mendapatkan hasil akhir kalkulasi. Langkah combine mencoba mencapai hal tersebut.

1.      Algoritma Divide And Conquer Pada Merge Sort

        Merge sort, seperti namanya, merupakan algoritma yang dirancang untuk melakukan pengurutan terhadap sekumpulan bilangan. Ide utama dari merge sort sama dengan algoritma perhitungan total, yaitu membagi-bagikan keseluruhan list menjadi komponen kecil, dan kemudian mengurutkan komponen tersebut dan menggabungkannya kembali menjadi sebuah list besar.

2.      Algoritma Divide And Conquer Pada Binary Search

    Algoritma pencarian Binary search adalah algoritma untuk mencari sebuah nilai pada tabel teurut dengan cara menghilangkan setengah data pada setiap langkah. Algoritma ini mencari nilai yang dicari dengan tiga langkah yaitu:

1. Mencari nilai tengah dari tabel (median).
2. Melakukan perbandingan nilai tengah dengan nilai yang dicari untuk menentukan apakah nilai yang dicari ada pada sebelum atau setelah nilai tengah.
3. Mencari setengah sisanya dengan cara yang sama.

3.      Algoritma Divide And Conquer Pada Insertion sort

        Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

4.      Algoritma Divide And Conquer Pada Selection sort

        Algoritma ini sangat rapat dan mudah untuk diimplementasikan. Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

5.      Algoritma Divide And Conquer Pada Quick sort

     Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut

1.  Divide

Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

2.   Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif. Pada algoritma quicksort, langkah “kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array.

6.      Algoritma Divide And Conquer Pada Counting sort

        Adalah sebuah algoritma sorting linear yang digunakan untuk mengurutkan ‘item’ ketika urutannya telah ditentukan dan memiliki panjang yang terbatas. Bilangan interval yang telah tetap, katakana k1 ke k2 adalah contoh dari ‘item’ tersebut. Counting sort sebenarnya merupakan metode pengurutan yang memanfaatkan index variabel array. Hanya effektif pada data yang nilainya kecil.

        Algoritma ini membuat 2 passover A dan passover B. Jika ukuran dari range k lebih kecil dari ukuran input n, maka time complexity = O(n). perhatikan juga bahwa algoritma ini stabil yang berarti bahwa sambungan diselesaikan dengan langsung mengabarkan element-element yang muncul pertama kali.

7.    Algoritma Divide And Conquer Pada Linear Searching

    Algoritma pencarian secara linear adalah algoritma untuk mencari sebuah nilai pada table sambarang dengan cara melakukan pass atau transversal. Transversal dari awal sampai akhir table. Ada dua macam cara pencarian pada table. Algoritma mempunyai dua jenis metode yaitu dengan Boolean dan tanpa Boolean.

8.      Algoritma Divide And Conquer Pada Radix Sort

        Radix sorting bisa digunakan ketika masing-masing universal element bisa dilihat sebagai sebuah urutan digit (atau huruf atau symbol lainnya). Sebagai contoh, kita bisa membuat masing-masing bilangan bulat antar 0 sampai 99 sebagai sebuah urutan dengan dua digit (seperti “05”). Untuk menyorting sebuah array dari angka 2-digit, algoritma ini membuat dua ‘passing’ sorting melalui array tersebut. Pada ‘passing’ pertama, element array disorting pada least significant decimal digit. Kunci utama dari radix sort adalah pada passing yang kedua. Hasilnya, setelah kedua passing melewati array tersebut, data yang terisi telah disorting.

Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

Nama   : Armelia Luvita Sari

Npm     : 20312057

Kelas     : IF20B

Sejarah Algoritma Devide dan Conquer

Pencarian biner, algoritma penurunan-dan-taklukkan di mana sub-masalah berukuran kira-kira setengah dari ukuran aslinya, memiliki sejarah yang panjang. Sementara deskripsi yang jelas tentang algoritma pada komputer muncul pada tahun 1946 dalam sebuah artikel oleh John Mauchly, gagasan untuk menggunakan daftar item yang diurutkan untuk memfasilitasi pencarian tanggal kembali setidaknya sejauh Babylonia pada 200 SM.

Algoritma penurunan-dan-taklukkan kuno lainnya adalah algoritma Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi bilangan tersebut menjadi subproblem ekuivalen yang lebih kecil dan lebih kecil, yang berasal dari beberapa abad SM.

Awal dari algoritma ini utamanya adalah pengurangan dan penaklukan - masalah asli secara berturut-turut dipecah menjadi sub-masalah tunggal, dan memang dapat diselesaikan secara berulang.

Contoh awal dari algoritma bagi-dan-taklukkan dengan beberapa subproblem adalah deskripsi Gauss tahun 1805 tentang apa yang sekarang disebut algoritma Cooley – Tukey fast Fourier transform (FFT), meskipun dia tidak menganalisis jumlah operasinya secara kuantitatif, dan FFT tidak tersebar luas sampai mereka ditemukan kembali lebih dari satu abad kemudian.

Algoritma D&C dua sub problem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan benar adalah algoritma pengurutan gabungan, yang ditemukan oleh John von Neumann pada tahun 1945.

 1.  Pengertian

Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :

1. Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
2. Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
3. Combine : Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula.

Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut, maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif (perulangan dengan memanggil dirinya sendiri). 

Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif. Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array. Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu merge sort, insert sort, quick sort, dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa dengan menggunakan algoritma brute force.

2. Penerapan Algoritma

2.1. Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer

Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma Divide and Conquer, hal ini dapat dipandang

sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:

Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).

Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1). (Basis).

Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X terbesar.

Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).

Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung da mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.

Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition), dan penelitian operasi. Divide and Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent, dan akhirnya menggabungkan solusi masing-masing upa-masalah sehingga menjadi solusi dari masalah semula.

Algoritma Divide and Conquer merupakan salah satu solusi dalam penyelesaian masalah convex hull. Algoritma ini ternyata memiliki kompleksitas waktu yang cukup kecil dan efektif dalam menyelesaikan permasalahan ini (jika dibandingkan algoritma lain). Selain itu juga, algoritma ini dapat digeneralisasi untuk permasalahan convex hull yang berdimensi lebih dari 3.

2.2. Persoalan Minimum dan Maksimum (MinMaks)

Persoalan : Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Ukuran table hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen.

Algoritma MinMaks :

1. Untuk kasus n = 1 atau n = 2,

SOLVE : Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks.

2. Untuk kasus n > 2,

DIVIDE : Bagi dua table A secSkema procedur utama Konversi dengan optimasi

Skema procedur rekursif dengan menerapkan Algoritma Divide and Conquer

Kompleksitas waktu algoritma :

T(n) = O(n/3)

dengan n menyatakan eksponen terkecil dari 2 yang mempunyai nilai 2n lebuh besar dari angka decimal

Algoritma konversi system bilangan dengan menggunakan algoritma dengan optimasi yang menerapkan algoritma Divide and Conquer lebih mangkus daripada algoritma konversi dengan metode pembagian sisa biasa jika dilihat dari segi kompleksitas waktunya. Hanya saja optimasi ini diimbangi dengan kenaikan pada kompleksitas ruangnya, meskipun pengaruhnya tidak sebesar optimasi yang kita lakukan.

2.4. Mencari Pasangan Titik yang Jaraknya Terdekat ( Closest Pair )

Persoalan : Diberikan himpunan titik, P, yang terdiri dari n buah titik, (xi,yi), pada bilangan 2-D. Tentukan jarak terdekat antara dua buah titik di dalam himpunan P. Jarak dua buah titik p1 = (x1, y1) dan p2 = (x2, y2) :

Penyelesaian dengan Algoritma Divide and Conquer :

a. Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).

b. Algoritma Closest Pair :

1. SOLVE : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus Euclidean.
2. DIVIDE : Bagi titik-titik itu ke dalam dua bagian, PLeft dan PRight, setiap bagian mempunyai jumlah titik yang sama
3. CONQUER :Secara rekursif, terapkan algoritma D-and-C pada masingmasing bagian.

Pasangan titik yang jaraknya terdekat ada tiga kemungkinan letaknya :

• Pasangan titik terdekat terdapat di bagian PLeft.
• Pasangan titik terdekat terdapat di bagian PRight.
• Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di PLeft dan satu titik di PRight.

Jika kasusnya adalah (c), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.ara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.

• CONQUER : Terapkan algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan maks dari table bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari table bagian kanan dinyatakan dalam peubah min2 dan maks2.
• COMBINE : Bandingkan min1 dan min2 untuk menentukan min table A, serta bandingkan maks1 dan maks2 untuk menentukan maks table A.

2.3. Optimasi Konversi Bilangan Desimal Ke Biner

Salah satu cara optimasi yang bias kita lakukan adalah membagi bilangan decimal yang hendak diubah dengan angka 8 ( bukan 2 ). Di sinilah prinsip algoritma Divide and Conquer kita gunakan untuk melakukan optimasi. Kita pecah-pecah angka decimal yang akan kita gunakan dengan cara membaginya dengan angka 8 secara berulang. Angka-angka sisa pembagian yang kita peroleh kemudian kita ubah ke dalam bilangan biner sebelum kita gabungkan menjadi hasil jawaban.

Karena angka pembagi yang kita pakai adalah 8 (23), maka kita dapat mengurangijumlah pembagian yang kita lakukan menjadi ± 1/3 dari jumlah semula. Hal ini tentu saja akan sangat berpengaruh pada kinerja dan waktu yang diperlukan oleh computer mengingat proses pembagian merupakan salah satu proses yang cukup rumit.

Permasalahan dalam Sorting

Nama  : Armelia Luvita Sari

Npm    : 20312057

Kelas   : IF20B

Pengertian Sorting

Pengurutan data dalam struktur data sangat penting untuk data yang bertipe data numerik ataupun karakter.

Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)

Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga dapat tersusun secara teratur menurut aturan tertentu.

Contoh :

Data Acak       : 10 3 8 7 12 18 1 

Ascending       : 1 3 6 7 8 10 12 18

Descending     : 18 12 10 8 7 6 3 1

2. Metode Pengurutan Data Berdasarkan Perbandingan (Bubble Sort)

Metode Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.

Bubble Sort merupakan cara pengurutan yang sederhana. Cara kerjanya adalah dengan berulang-ulang melakukan traversal (proses looping) terhadap elemen-elemen struktur data yang belum diurutkan. Di dalam traversal tersebut nilai dari dua elemen struktur data dibandingkan. Jika ternyata urutannya tidak sesuai dengan “pesanan”, maka dilakukan pertukaran (swap). Algoritma sorting ini disebut juga dengan comparison sort dikarenakan hanya mengandalkan perbandingan nilai elemen untuk mengoperasikan elemennya.

 Contoh :

1. Pengurutan Ascending : Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.

2.  Pengurutan Descending : Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.

3.  Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya.

4.  Ketika suatu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya dari 0 sampai dengan iterasi sebanyak n-1.

3. Kelebihan dan Kekurangan Bubble Sort

  a.  Kelebihan dari algoritma Bubble Sort adalah sebagai berikut :

·      Algoritma yang simpel.

·     Mudah untuk diubah menjadi kode.

·    Definisi terurut terdapat dengan jelas dalam algoritma.

·   Cocok untuk pengurutan data dengan elemen kecil telah terurut.

 Kekurangan dari algoritma Bubble Sort adalah sebagai berikut :

·    Tidak efektif dalam pengurutan data berskala besar.

·  Langkah pengurutan yang terlalu panjang.

·     Kompleksitas algoritma yang terlalu besar, baik dalam average case maupun worst case, yaitu O(n2), sehingga seringkali disebut sebagai algoritma primitif, brute-force, maupun algoritma naif