HPK taruh disini
Mei
2015
Soal.
1.Jelaskan proses konversi bilangan 8229(10) kedalam bentuk bilangan Biner, Heksadesimal, dan Oktal.
2.Buatlah penjelasan untuk tipe data signed integer (bilangan bertanda) untuk prosesor yang memiliki jumlah 8 bit.
3.Terdapat empat operasi logika yang dapat digunakan untuk memodifikasi pola bit yaitu complementing, setting, unsetting, dan flipping. Buat penjelasan proses untuk mendapatkan hasil dari angka desimal berikut ini:
210(10) XOR 237(10)
4.Algoritma adalah serangkaian langkah-langkah yang jelas untuk mendapatkan hasil dalam waktu yang terbatas. Jelaskan langkah-langkah untuk mengurutkan deretean angka dengan metode bubble sort.
1.Jelaskan proses konversi bilangan 8229(10) kedalam bentuk bilangan Biner, Heksadesimal, dan Oktal.
2.Buatlah penjelasan untuk tipe data signed integer (bilangan bertanda) untuk prosesor yang memiliki jumlah 8 bit.
3.Terdapat empat operasi logika yang dapat digunakan untuk memodifikasi pola bit yaitu complementing, setting, unsetting, dan flipping. Buat penjelasan proses untuk mendapatkan hasil dari angka desimal berikut ini:
210(10) XOR 237(10)
4.Algoritma adalah serangkaian langkah-langkah yang jelas untuk mendapatkan hasil dalam waktu yang terbatas. Jelaskan langkah-langkah untuk mengurutkan deretean angka dengan metode bubble sort.
Jawab:
A. Bilangan Biner
Konversi
bilangan biner adalah dengan membagi bilangan desimal dengan 2 dan menyimpan
sisa bagi per setiap pembagian terus hingga hasil baginya < 2. Hasil
konversi adalah urutan sisa bagi dari yang paling akhir hingga paling awal.
Proses konversi bilangan 8229(10) kedalam bentuk bilangan
Biner
HASIL
PEMBAGI
|
PEMBAGI
|
SISA
BAGI
|
8229
|
2
|
1
|
4114
|
2
|
0
|
2057
|
2
|
1
|
1028
|
2
|
0
|
514
|
2
|
0
|
257
|
2
|
1
|
128
|
2
|
0
|
64
|
2
|
0
|
32
|
2
|
0
|
16
|
2
|
0
|
8
|
2
|
0
|
4
|
2
|
0
|
2
|
2
|
0
|
1
|
2
|
1
|
Konversi
bilangan biner dari 8229(10) adalah: 10000000100101
B. Bilangan Octal
Konversi bilangan octal adalah
dengan membagi bilangan desimal dengan 8 dan menyimpan sisa bagi per setiap
pembagian terus hingga hasil baginya < 8. Hasil konversi adalah urutan sisa
bagi dari yang paling akhir hingga paling awal. Proses konversi bilangan 8229(10) kedalam
bentuk bilangan octal
HASIL
BAGI
|
PEMBAGI
|
SISA
BAGI
|
8229
|
8
|
6
|
1028
|
8
|
5
|
128
|
8
|
0
|
16
|
8
|
0
|
2
|
8
|
2
|
Konversi
bilangan octal dari 8245(10) adalah : 20056(8)
C. 8229(10) Dikonversi Ke bilangan
Heksadesimal
Konversi
bilangan Heksa desimal adalah dengan membagi bilangan desimal dengan 16 dan
menyimpan sisa bagi per seitap pembagian terus hingga hasil baginya < 16.
Hasil konversi adalah urutan sisa bagi dari yang paling akhir hingga paling
awal. Apabila sisa bagi diatas 9 maka
angkanya diubah, untuk nilai 10 angkanya A, nilai 11 angkanya B, nilai 12
angkanya C, nilai 13 angkanya D, nilai 14 angkanya E, nilai 15 angkanya F
Hasil bagi
|
Pembagi
|
Sisa bagi
|
8229
|
16
|
5
|
514
|
16
|
6
|
32
|
16
|
0
|
2
|
16
|
2
|
Hasil
konversi bilangan heksadesimal dari 8245(10) adalah: 2065(16)
2. Tipe Data
Sign Integer (Bilangan Bertanda ) untuk prosessor 8 bit
Representasi data merupakan cara untuk meletakkan sebuah nilai
dalam memory komputer. Representasi data ini terdiri dari
beberapa bilangan yang biasa disebut tipe data dalam pemograman.
Tipe data yang biasa kita kenal dan kita gunakan dalam
memprogram sebuah aplikasi adalah tipe data Integer, Float, Char, Double. Untuk
tipe data integer dan char, terdiri
dari dua yaitu Unsigned dan Signed.
Tipe data Char atau Integer yang diikuti dengan kata Unsigned
akan menghasilkan
nilai positif semua karena tipe data ini tidak mengenal tanda
didepannya (-).
Sedangkan tipe data Chat atau Integer yang diikuti oleh signed,
(biasanya tidak dituliskan) akan terdapat nilai negative nya karena bilangan
ini mengenal tanda yang ada didepan nilai (-).
Tipe data Char dan integer menghasilkan bilangan bulat (tidak
berkoma). Sedangkan tipe data Float dan Double menghasilkan bilangan berkoma.
Signed integer
(bilangan bertanda)
Signed" berarti
bahwa salah satu dari bit-bit tersebut menandakan apakah sebuah angka yang
dimaksud adalah negatif atau positif.
Karena
prosesor memiliki 8 bit, maka ia dapat menyimpan hingga 2
pangkat 8 nilai yang
berbeda (tepatnya 512) Nilai-nilai tersebut
dapat dibagi hampir sama rata antara bilangan positif dan negatif.
3. Gerbang OR akan berlogika 1 apabila salah satu atau semua
inputan yang dimasukkan bernilai 1 dan apabila keluaran yang di inginkan
berlogika 0 maka inputan yang dimasukkan harus bernilai 0 semua.
Tabel Kebenaran
Tabel Kebenaran
Input A
|
Input B
|
Output
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
4. 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 dapatdilihat 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 penggeseranpaling 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 jumlahpenggeseran 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.
Soal.
1.Jelaskan proses konversi bilangan 8229(10) kedalam bentuk bilangan Biner, Heksadesimal, dan Oktal.
2.Buatlah penjelasan untuk tipe data signed integer (bilangan bertanda) untuk prosesor yang memiliki jumlah 8 bit.
3.Terdapat empat operasi logika yang dapat digunakan untuk memodifikasi pola bit yaitu complementing, setting, unsetting, dan flipping. Buat penjelasan proses untuk mendapatkan hasil dari angka desimal berikut ini:
210(10) XOR 237(10)
4.Algoritma adalah serangkaian langkah-langkah yang jelas untuk mendapatkan hasil dalam waktu yang terbatas. Jelaskan langkah-langkah untuk mengurutkan deretean angka dengan metode bubble sort.
1.Jelaskan proses konversi bilangan 8229(10) kedalam bentuk bilangan Biner, Heksadesimal, dan Oktal.
2.Buatlah penjelasan untuk tipe data signed integer (bilangan bertanda) untuk prosesor yang memiliki jumlah 8 bit.
3.Terdapat empat operasi logika yang dapat digunakan untuk memodifikasi pola bit yaitu complementing, setting, unsetting, dan flipping. Buat penjelasan proses untuk mendapatkan hasil dari angka desimal berikut ini:
210(10) XOR 237(10)
4.Algoritma adalah serangkaian langkah-langkah yang jelas untuk mendapatkan hasil dalam waktu yang terbatas. Jelaskan langkah-langkah untuk mengurutkan deretean angka dengan metode bubble sort.
Jawab:
A. Bilangan Biner
Konversi
bilangan biner adalah dengan membagi bilangan desimal dengan 2 dan menyimpan
sisa bagi per setiap pembagian terus hingga hasil baginya < 2. Hasil
konversi adalah urutan sisa bagi dari yang paling akhir hingga paling awal.
Proses konversi bilangan 8229(10) kedalam bentuk bilangan
Biner
HASIL
PEMBAGI
|
PEMBAGI
|
SISA
BAGI
|
8229
|
2
|
1
|
4114
|
2
|
0
|
2057
|
2
|
1
|
1028
|
2
|
0
|
514
|
2
|
0
|
257
|
2
|
1
|
128
|
2
|
0
|
64
|
2
|
0
|
32
|
2
|
0
|
16
|
2
|
0
|
8
|
2
|
0
|
4
|
2
|
0
|
2
|
2
|
0
|
1
|
2
|
1
|
Konversi
bilangan biner dari 8229(10) adalah: 10000000100101
B. Bilangan Octal
Konversi bilangan octal adalah
dengan membagi bilangan desimal dengan 8 dan menyimpan sisa bagi per setiap
pembagian terus hingga hasil baginya < 8. Hasil konversi adalah urutan sisa
bagi dari yang paling akhir hingga paling awal. Proses konversi bilangan 8229(10) kedalam
bentuk bilangan octal
HASIL
BAGI
|
PEMBAGI
|
SISA
BAGI
|
8229
|
8
|
6
|
1028
|
8
|
5
|
128
|
8
|
0
|
16
|
8
|
0
|
2
|
8
|
2
|
Konversi
bilangan octal dari 8245(10) adalah : 20056(8)
C. 8229(10) Dikonversi Ke bilangan
Heksadesimal
Konversi
bilangan Heksa desimal adalah dengan membagi bilangan desimal dengan 16 dan
menyimpan sisa bagi per seitap pembagian terus hingga hasil baginya < 16.
Hasil konversi adalah urutan sisa bagi dari yang paling akhir hingga paling
awal. Apabila sisa bagi diatas 9 maka
angkanya diubah, untuk nilai 10 angkanya A, nilai 11 angkanya B, nilai 12
angkanya C, nilai 13 angkanya D, nilai 14 angkanya E, nilai 15 angkanya F
Hasil bagi
|
Pembagi
|
Sisa bagi
|
8229
|
16
|
5
|
514
|
16
|
6
|
32
|
16
|
0
|
2
|
16
|
2
|
Hasil
konversi bilangan heksadesimal dari 8245(10) adalah: 2065(16)
2. Tipe Data
Sign Integer (Bilangan Bertanda ) untuk prosessor 8 bit
Representasi data merupakan cara untuk meletakkan sebuah nilai
dalam memory komputer. Representasi data ini terdiri dari
beberapa bilangan yang biasa disebut tipe data dalam pemograman.
Tipe data yang biasa kita kenal dan kita gunakan dalam
memprogram sebuah aplikasi adalah tipe data Integer, Float, Char, Double. Untuk
tipe data integer dan char, terdiri
dari dua yaitu Unsigned dan Signed.
Tipe data Char atau Integer yang diikuti dengan kata Unsigned
akan menghasilkan
nilai positif semua karena tipe data ini tidak mengenal tanda
didepannya (-).
Sedangkan tipe data Chat atau Integer yang diikuti oleh signed,
(biasanya tidak dituliskan) akan terdapat nilai negative nya karena bilangan
ini mengenal tanda yang ada didepan nilai (-).
Tipe data Char dan integer menghasilkan bilangan bulat (tidak
berkoma). Sedangkan tipe data Float dan Double menghasilkan bilangan berkoma.
Signed integer
(bilangan bertanda)
Signed" berarti
bahwa salah satu dari bit-bit tersebut menandakan apakah sebuah angka yang
dimaksud adalah negatif atau positif.
Karena
prosesor memiliki 8 bit, maka ia dapat menyimpan hingga 2
pangkat 8 nilai yang
berbeda (tepatnya 512) Nilai-nilai tersebut
dapat dibagi hampir sama rata antara bilangan positif dan negatif.
3. Gerbang OR akan berlogika 1 apabila salah satu atau semua
inputan yang dimasukkan bernilai 1 dan apabila keluaran yang di inginkan
berlogika 0 maka inputan yang dimasukkan harus bernilai 0 semua.
Tabel Kebenaran
Tabel Kebenaran
Input A
|
Input B
|
Output
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
4. 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 dapatdilihat 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 penggeseranpaling 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 jumlahpenggeseran 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.
Soal.
1.Jelaskan proses konversi bilangan 8229(10) kedalam bentuk bilangan Biner, Heksadesimal, dan Oktal.
2.Buatlah penjelasan untuk tipe data signed integer (bilangan bertanda) untuk prosesor yang memiliki jumlah 8 bit.
3.Terdapat empat operasi logika yang dapat digunakan untuk memodifikasi pola bit yaitu complementing, setting, unsetting, dan flipping. Buat penjelasan proses untuk mendapatkan hasil dari angka desimal berikut ini:
210(10) XOR 237(10)
4.Algoritma adalah serangkaian langkah-langkah yang jelas untuk mendapatkan hasil dalam waktu yang terbatas. Jelaskan langkah-langkah untuk mengurutkan deretean angka dengan metode bubble sort.
1.Jelaskan proses konversi bilangan 8229(10) kedalam bentuk bilangan Biner, Heksadesimal, dan Oktal.
2.Buatlah penjelasan untuk tipe data signed integer (bilangan bertanda) untuk prosesor yang memiliki jumlah 8 bit.
3.Terdapat empat operasi logika yang dapat digunakan untuk memodifikasi pola bit yaitu complementing, setting, unsetting, dan flipping. Buat penjelasan proses untuk mendapatkan hasil dari angka desimal berikut ini:
210(10) XOR 237(10)
4.Algoritma adalah serangkaian langkah-langkah yang jelas untuk mendapatkan hasil dalam waktu yang terbatas. Jelaskan langkah-langkah untuk mengurutkan deretean angka dengan metode bubble sort.
Jawab:
A. Bilangan Biner
Konversi
bilangan biner adalah dengan membagi bilangan desimal dengan 2 dan menyimpan
sisa bagi per setiap pembagian terus hingga hasil baginya < 2. Hasil
konversi adalah urutan sisa bagi dari yang paling akhir hingga paling awal.
Proses konversi bilangan 8229(10) kedalam bentuk bilangan
Biner
HASIL
PEMBAGI
|
PEMBAGI
|
SISA
BAGI
|
8229
|
2
|
1
|
4114
|
2
|
0
|
2057
|
2
|
1
|
1028
|
2
|
0
|
514
|
2
|
0
|
257
|
2
|
1
|
128
|
2
|
0
|
64
|
2
|
0
|
32
|
2
|
0
|
16
|
2
|
0
|
8
|
2
|
0
|
4
|
2
|
0
|
2
|
2
|
0
|
1
|
2
|
1
|
Konversi
bilangan biner dari 8229(10) adalah: 10000000100101
B. Bilangan Octal
Konversi bilangan octal adalah
dengan membagi bilangan desimal dengan 8 dan menyimpan sisa bagi per setiap
pembagian terus hingga hasil baginya < 8. Hasil konversi adalah urutan sisa
bagi dari yang paling akhir hingga paling awal. Proses konversi bilangan 8229(10) kedalam
bentuk bilangan octal
HASIL
BAGI
|
PEMBAGI
|
SISA
BAGI
|
8229
|
8
|
6
|
1028
|
8
|
5
|
128
|
8
|
0
|
16
|
8
|
0
|
2
|
8
|
2
|
Konversi
bilangan octal dari 8245(10) adalah : 20056(8)
C. 8229(10) Dikonversi Ke bilangan
Heksadesimal
Konversi
bilangan Heksa desimal adalah dengan membagi bilangan desimal dengan 16 dan
menyimpan sisa bagi per seitap pembagian terus hingga hasil baginya < 16.
Hasil konversi adalah urutan sisa bagi dari yang paling akhir hingga paling
awal. Apabila sisa bagi diatas 9 maka
angkanya diubah, untuk nilai 10 angkanya A, nilai 11 angkanya B, nilai 12
angkanya C, nilai 13 angkanya D, nilai 14 angkanya E, nilai 15 angkanya F
Hasil bagi
|
Pembagi
|
Sisa bagi
|
8229
|
16
|
5
|
514
|
16
|
6
|
32
|
16
|
0
|
2
|
16
|
2
|
Hasil
konversi bilangan heksadesimal dari 8245(10) adalah: 2065(16)
2. Tipe Data
Sign Integer (Bilangan Bertanda ) untuk prosessor 8 bit
Representasi data merupakan cara untuk meletakkan sebuah nilai
dalam memory komputer. Representasi data ini terdiri dari
beberapa bilangan yang biasa disebut tipe data dalam pemograman.
Tipe data yang biasa kita kenal dan kita gunakan dalam
memprogram sebuah aplikasi adalah tipe data Integer, Float, Char, Double. Untuk
tipe data integer dan char, terdiri
dari dua yaitu Unsigned dan Signed.
Tipe data Char atau Integer yang diikuti dengan kata Unsigned
akan menghasilkan
nilai positif semua karena tipe data ini tidak mengenal tanda
didepannya (-).
Sedangkan tipe data Chat atau Integer yang diikuti oleh signed,
(biasanya tidak dituliskan) akan terdapat nilai negative nya karena bilangan
ini mengenal tanda yang ada didepan nilai (-).
Tipe data Char dan integer menghasilkan bilangan bulat (tidak
berkoma). Sedangkan tipe data Float dan Double menghasilkan bilangan berkoma.
Signed integer
(bilangan bertanda)
Signed" berarti
bahwa salah satu dari bit-bit tersebut menandakan apakah sebuah angka yang
dimaksud adalah negatif atau positif.
Karena
prosesor memiliki 8 bit, maka ia dapat menyimpan hingga 2
pangkat 8 nilai yang
berbeda (tepatnya 512) Nilai-nilai tersebut
dapat dibagi hampir sama rata antara bilangan positif dan negatif.
3. Gerbang OR akan berlogika 1 apabila salah satu atau semua
inputan yang dimasukkan bernilai 1 dan apabila keluaran yang di inginkan
berlogika 0 maka inputan yang dimasukkan harus bernilai 0 semua.
Tabel Kebenaran
Tabel Kebenaran
Input A
|
Input B
|
Output
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
4. 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 dapatdilihat 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 penggeseranpaling 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 jumlahpenggeseran 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.
