MAKALAH STRUKTUR DATA
"BUBBLE SORT"
Di
SUSUN OLEH:
SHELLY OCTAVIANI KURNIAWAN
PROGRAM
STUDI TEKNIK INFORMATIKA
JURUSAN
TEKNOLOGI INFORMASI
UNIVERSITAS
TADULAKO
2016/2017
BAB I
PENDAHULUAN
1.1
LATAR BELAKANG
Pengurutan dalam pengolahan data dirasakan sangat penting dalam Teknologi Informasi. Kita tahu bahwa pemecahan permasalahan pengolahan data dapat menjadi lebih efektif dan efisien bila data sudah dalam keadaan terurut. Pengurutan adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu. Urutan objek tersebut dapat menaik (ascending) atau menurun (descending). Adanya kebutuhan terhadap proses pengurutan memunculkan bermacam-macam metode pengurutan. Di antara banyak algoritma pengurutan terdapat pengurutan data dengan menggunakan metode Bubble Sort atau pengurutan dengan proses pengurutannya dengan melakukan pembandingan antardata, yang kemudian diikuti dengan pertukaran data bila tidak sesuai dengan syarat tertentu.
BAB II
LANDASAN TEORI
2.1 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.
2.2 Konsep Bubble Sort
* 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.
* 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. Artinya Algoritma ini
akan menggeser nilai yang terkecil atau
terbesar (sesuai dengan jenis pengurutan, ascending atau descending) ke posisi
ujung dari daftar. Demikian seterusnya hingga semua daftar dalam keadaan
terurut. Proses dasar yang terjadi dalam algoritma ini adalah proses pertukaran
nilai (swapping).
2.3 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.
BAB III
PEMBAHASAN
Untuk membentuk data yang tidak urut menjadi data yang urut terdapat berbagai algoritma yang bisa digunakan. Dalam pengurutan data terdapat istilah ascending (pengurutan data dari kecil ke besar) dan descending (pengurutan data dari kecil ke besar). Untuk lebih jelasnya bisa dilihat gambar berikut :
Metode bubble sort merupakan metode tersederhana untuk melakukan
pengurutan data, tetapi memiliki kinerja terburuk untuk data yang besar.
Pengurutan dilakukan dengan membandingkan sebuah bilangan dengan seluruh
bilangan yang terletak sesudah bilangan tersebut. Penukaran dilakukan kalau
suatu kriteria dipenuhi. Sebagai contoh, terdapat kumpulan data seperti berikut :
5 12 1 15 19 13 25 40
Dari data diatas, maka kita dapat mengurutkannya
dengan membandingkan bilangan yang berada di sebelah kanan, apabila lebih kecil
dari bilangan di sebelah kirinya maka bilangan tersebut akan ditukar hingga
menghasilkan bilangan yang berurut.
Awal
: 5 12 1 15 19 13 25 40
Tahap 1 : 5 12 1 15 13 19 25 40
Tahap 2 : 5 12 1 13 15 19 25 40
Tahap 3 : 5 1
12 13 15 19 25 40
Tahap 4 : 1 5
12 13 15 19 25 40
Dari data diatas, diurutkan naik (ascending) dari
bilangan terkecil hingga bilangan terbesar dengan 4 tahap. Pada tahap pertama,
angka 13 (kanan) lebih kecil dari angka 19 (kiri) sehingga posisi kedua angka
tersebut ditukar. Kemudian pada tahap kedua, angka 13 dan 15 juga demikian.
Lalu pada tahap ketiga dan keempat, angka 1 (kanan) lebih kecil dari angka
disebelah kirinya maka terjadi perubahan posisi angka, sehingga data angka
tersebut akan terurut.
BAB IV
KESIMPULAN
Metode bubble sort merupakan metode paling simple yang
digunakan untuk mengurutkan data dan juga metode yang paling mudah dipahami
algoritmanya. Namun, metode bubble sort tidak efisien, karena akan mengalami
kelambatan pada saat mengurutkan data yang banyak dikarenakan setiap
data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.
DAFTAR PUSTAKA
Tidak ada komentar:
Posting Komentar