Algoritma Bublesort

Bubblesort adalah satu algoritma sort populer. Pekerjaan ini oleh berulang-kali menukar unsur berdekatan

itu rusak.

BUBBLESORT( A )

1 untuk aku ←  1 untuk panjang [ A ]

2 lakukan untuk j ←  panjang [ A ]  downto aku + 1

3 lakukan kalau A [ j ] <  A [ j - 1]

4 kemudian pertukaran A [ j ]  .  A [ j - 1]

a. Biar A ′  tandakan keluaran dari BUBBLESORT( A ). Untuk membuktikan bahwa BUBBLESORT adalah

benarkan, kita perlu membuktikan bahwa ini mengakhiri dan tersebut

 (2. 3 )

b. dimana n =  panjang [ A ]. Apa selain itu harus dibuktikan untuk memperlihatkan bahwa BUBBLESORT sebenarnya

berbagai?

B. UNTUK N         PANJANG [ A ]

Dua bagian berikutnya akan membuktikan ketidaksamaan( 2.3 ).

b. Menyatakan secara tepat satu karar simpal untuk untuk simpal berderet 2 - 4, dan buktikan bahwa simpal ini

pegangan karar. Buktimu harus mempergunakan struktur dari karar simpal buktikan

disajikan di bab ini.

c. Mempergunakan penghentian kondisi karar simpal dibuktikan di bagian (b ), nyatakan satu simpal

karar untuk untuk simpal berderet 1 - 4 itu akan mengijinkan kamu untuk membuktikan ketidaksamaan( 2.3 ).

Buktimu harus mempergunakan struktur dari bukti karar simpal disajikan di sini

bab.

d. Apa itu waktu berlari kasus yang terburuk dari bubblesort? Bagaimana bandingkan ini ke

waktu berlari dari berbagai pemasangan susuk?

BAB I

PENDAHULUAN

1.1  Latar Belakang

Di dalam kehidupan manusia sehari-hari, manusia selalu dihadapkan oleh berbagai macam masalah dari berbagai macam bidang. Masalah-masalah ini yang dihadapi oleh manusia tingkat kesulitan dan kompleksitasnya sangat bervariasi, mulai dari yang teramat sederhana dengan sedikit faktor-faktor yang berkaitan dengan masalah tersebut dan perlu diperhitungkan sampai dengan yang sangat rumit dengan banyak sekali faktor-faktor turut serta berkaitan dengan masalah tersebut dan perlu untuk diperhitungkan. Untuk menghadapi masalah-masalah ini, manusia mulai mengembangkan sebuah sistem yang dapat membantu manusia agar dapat dengan mudah mampu untuk menyelesaikan masalah-masalah tersebut.

Ketepatan bubblesort  ini adalah sebuah jawaban akan sebuah sistem yang manusia kembangkan untuk membantu mencari dan melakukan pengurutan atau penyortiran masalah-masalah tersebut dan dengan memperhitungkan berbagai macam factor yang ada di dalam lingkup masalah tersebut. Dengan ketepatan bubblesort, manusia dapat dengan mudah melihat mengidentifikasi dan melihat hubungan antara faktor-faktor yang mempengaruhi suatu masalah dan dapat mencari penyelesaian terbaik dengan memperhitungkan faktor-faktor tersebut. ketepatan ini juga dapat menganalisa nilai resiko dan nilai suatu informasi yang terdapat dalam suatu alternatif pemecahan masalah. Peranan pohon keputusan ini sebagai alat Bantu dalam mengambil keputusan (decision support tool) telah dikembangkan oleh manusia sejak perkembangan teori pohon yang dilandaskan pada teori graf. Kegunaan pohon keputusan yang sangat banyak ini membuatnya telah dimanfaatkan oleh manusia dalam berbagai macam sistem pengambilan keputusan.

1.2  Tujuan

Adapun tujuan dari makalah ini, yaitu :

1.      Agar dapat mengetahui cara membuat suatu algoritma ketepatan bubble sort

2.      Dapat mengetahui prinsip kerja dari algoritma ketepatan bubble sort

3.      Dapat menganalisis suatu data mengunakan bubble sort

1.3  Manfaat

Adapun manfaat dari makalah ini, yaitu :

1.      Agar penulis dan pembaca dapat menambah wawasan atau pengetahuan tentang algoritma, terutama pada algoritma ketepatan bubble sort

2.      Dengan makalah ini juga dapat mempermantap cara kita membuat suatu algoritma ketepatan bubble sort

BAB II

PEMBAHASAN

             

2.1  Bubble Sort

Ketepatan bubble sort adalah sebuah tehnik data mining paling terkenal dan paling populer yang sering digunakan, dalam penggalian informasi-informasi berharga tertentu. hal ini dikarenakan, pohon keputusan tidak memerlukan proses pengelolaan pengetahuan dari seorang pakar atau expert terlebih dahulu. selain itu, pohon keputusan dapat langsung menyelesaikan sebuah masalah pengambilan keputusan dalam dimensi yang besar, selain itu, pohon keputusan dapat langsung menyelesaikan sebuah masalah pengambilan keputusan dalam dimensi yang besar, dengan akurasi yang baik dan tepat, asalkan data training yang dipakai adalah data yang benar akurat.

       A.      Pengertian Bubble Sort

            Bubble Sort adalah salah satu algoritma untuk sorting data, atau kata lainnya mengurutkan data dari yang terbesar ke yang terkecil atau sebaliknya (Ascending atau Descending).

            Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

            Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.

Algoritma bubble sort adalah salah satu algoritma pengurutan yang paling simple, baik dalam hal pengertian maupun penerapannya. Ide dari algoritma ini adalah mengulang proses pembandingan antara tiap-tiap elemen

array dan menukarnya apabila urutannya salah. Pembandingan elemen-elemen ini akan terus diulang hingga tidak perlu dilakukan penukaran lagi. Algoritma ini termasuk dalam golongan algoritma comparison sort, karena menggunakan perbandingan dalam operasi antar elemennya. Berikut ini adalah gambaran dari algoritma bubble sort. Misalkan kita mempunyai sebuah array dengan.  Elemen-elemen “4 2 5 3 9”. Proses yang akan terjadi apabila digunakan algoritma bubblesort adalah sebagai berikut.

Pass pertama

(4 2 5 3 9) menjadi (2 4 5 3 9)

(2 4 5 3 9) menjadi (2 4 5 3 9)

(2 4 5 3 9) menjadi (2 4 3 5 9)

(2 4 3 5 9) menjadi (2 4 3 5 9)

Pass kedua

(2 4 3 5 9) menjadi (2 4 3 5 9)

(2 4 3 5 9) menjadi (2 3 4 5 9)

       (2 3 4 5 9) menjadi (2 3 4 5 9)

       (2 3 4 5 9) menjadi (2 3 4 5 9)

       Pass ketiga

                   (2 3 4 5 9) menjadi (2 3 4 5 9)

       (2 3 4 5 9) menjadi (2 3 4 5 9)

        (2 3 4 5 9) menjadi (2 3 4 5 9)

        (2 3 4 5 9) menjadi (2 3 4 5 9)

Dapat dilihat pada proses di atas, sebenarnya pada pass kedua, langkah kedua, array telah terurut. Namun algoritma tetap dilanjutkan hingga pass kedua berakhir. Pass ketiga dilakukan karena definisi terurut dalam algoritma bubblesort adalah tidak ada satupun penukaran pada suatu pass, sehingga pass ketiga dibutuhkan untuk memverifikasi keurutan array tersebut.

B.      Algoritma Bubble Sort

            1.    Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).

            2.    Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.

            3.    Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.

                             4.    Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.

Contoh Kasus Bubble Sort :

Misalkan kita punya data seperti ini: 6, 4, 3, 2 dan kita ingin mengurutkan data ini (ascending) dengan menggunakan bubble sort. Berikut ini adalah proses yang terjadi:

Iterasi ke-1: 4, 6, 3, 2 :: 4, 3, 6, 2 :: 4, 3, 2, 6 (ada 3 pertukaran)

Iterasi ke-2: 3, 4, 2, 6 :: 3, 2, 4, 6 :: 3, 2, 4, 6 (ada 2 pertukaran)

Iterasi ke-3: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 1 pertukaran)

Iterasi ke-4: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 0 pertukaran) -> proses selesai

C.      Kompleksitas Algoritma Bubble Sort

Kompleksitas Algoritma Bubble Sort dapat dilihat dari beberapa jenis kasus, yaitu worst-case, average-case, dan best-case.

Ø  Kondisi Best-Case

Dalam kasus ini, data yang akan disorting telah terurut sebelumnya, sehingga proses perbandingan hanya dilakukan sebanyak (n-1) kali, dengan satu kali pass.

Proses perbandingan dilakukan hanya untuk memverifikasi keurutan data. Contoh Best-Case dapat dilihat pada pengurutan data “1 2 3 4” di bawah ini.

Pass Pertama

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

Dari proses di atas, dapat dilihat bahwa tidak terjadi penukaran posisi satu kalipun, sehingga tidak dilakukan pass selanjutnya. Perbandingan elemen dilakukan sebanyak tiga kali. Proses perbandingan pada kondisi ini hanya dilakukan sebanyak (n-1) kali. Persamaan Big-O yang diperoleh dari proses ini adalah O(n). Dengan kata lain, pada kondisi Best-Case algoritma Bubble Sort termasuk pada algoritma

lanjar.

Ø  Kondisi Worst-Case

Dalam kasus ini, data terkecil berada pada ujung array. Contoh Worst-Case dapat dilihat pada pengurutan data “4 3 2 1” di bawah ini.

Pass Pertama

(4 3 2 1) menjadi (3 4 2 1)

(3 4 2 1) menjadi (3 2 4 1)

(3 2 4 1) menjadi (3 2 1 4)

Pass Kedua

(3 2 1 4) menjadi (2 3 1 4)

(2 3 1 4) menjadi (2 1 3 4)

(2 1 3 4) menjadi (2 1 3 4)

Pass Ketiga

(2 1 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

Pass Keempat

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

Dari langkah pengurutan di atas, terlihat bahwa setiap kali melakukan satu pass, data terkecil akan bergeser ke arah awal sebanyak satu step. Dengan kata lain, untuk menggeser data terkecil dari urutan keempat menuju urutan pertama, dibutuhkan pass sebanyak tiga kali, ditambah satu kali pass untuk memverifikasi. Sehingga jumlah proses pada kondisi best case dapat dirumuskan sebagai berikut. Jumlah proses = n2+n (3)

Dalam persamaan (3) di atas, n adalah jumlah elemen yang akan diurutkan. Sehingga notasi Big-O yang didapat adalah O(n2). Dengan kata lain, pada kondisi worst-case, algoritma Bubble Sort termasuk dalam kategori algoritma kuadratik.

Ø  Kondisi Average-Case

Pada kondisi average-case, jumlah pass ditentukan dari elemen mana yang mengalami penggeseran ke kiri paling banyak. Hal ini dapat ditunjukkan oleh proses pengurutan suatu array, misalkan saja (1 8 6 2). Dari (1 8 6 2), dapat dilihat bahwa yang akan mengalami proses penggeseran paling banyak adalah elemen 2, yaitu sebanyak dua kali.

Pass Pertama

(1 8 6 2) menjadi (1 8 6 2)

(1 8 6 2) menjadi (1 6 8 2)

(1 6 8 2) menjadi (1 6 2 8)

Pass Kedua

(1 6 2 8) menjadi (1 6 2 8)

(1 6 2 8) menjadi (1 2 6 8)

(1 2 6 8) menjadi (1 2 6 8)

Pass Ketiga

(1 2 6 8) menjadi (1 2 6 8)

(1 2 6 8) menjadi (1 2 6 8)

(1 2 6 8) menjadi (1 2 6 8)

Dari proses pengurutan di atas, dapat dilihat bahwa untuk mengurutkan diperlukan dua buah passing, ditambah satu buah passing untuk memverifikasi. Dengan kata lain, jumlah proses perbandingan dapat dihitung sebagai berikut. Jumlah proses = x2+x (4) Dalam persamaan (4) di atas, x adalah jumlah penggeseran terbanyak. Dalam hal ini, x tidak pernah lebih besar dari n, sehingga x dapat dirumuskan sebagai

Dari persamaan (4) dan (5) di atas, dapat disimpulkan bahwa notasi

big-O nya adalah O(n2). Dengan kata lain, pada kondisi average case algoritma Bubble Sort termasuk dalam algoritma kuadratik.

D.      Implementasi dalam Pseudo-Code

Setiap algoritma akan memiliki implementasi yang berbeda, tergantung dari bahasa program yang dipakai. Oleh karena itu berikut ini adalah pseudo-code dari algoritma bubblesort, untuk memudahkan implementasi bubblesort pada bahasa apapun.

procedure bubbleSort( A : list of

sortable items ) defined as:

do

swapped := false

for each i in 0 to length(A) - 2

inclusive do:

if A[i] > A[i+1] then

swap( A[i], A[i+1] )

swapped := true

end if

end for

while swapped

end procedure

E.       Kelebihan dan Kelemahan Bubble Sort

Kelebihan :

·      Metode Buble Sort merupakan metode yang paling simpel

·      Metode Buble Sort mudah dipahami algoritmanya

Kelemahan:

Meskipun simpel metode Bubble sort  merupakan metode pengurutan yang paling tidak efisien.  Kelemahan buble sort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika  data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.