Bubble Sorting
Assalammualaikum Wr.Wb.
Pada tulisan kali ini saya akan membahas tentang bubble sorting,dalam rangka memenuhi tugas dari dosen,mudah-mudahan selain untuk memenuhi tugas tapi juga bisa sambil berbagi ilmu kepada para pembaca baik langsung saja berikut pembahasan nya.
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.
Studi kasus :
Pada suatu kelas terdapat ada beberapa
mahasiswa yang tentunya memiliki nama yang huruf awal nya berbeda-beda,nah di
sini kita akan membuat program untuk mengurutkan nama – nama mahasiswa di kelas
tersebut sesuai huruf awal menurut abjad,di sini kita mempunyai 10 nama
misalkan :
ahmad
dani
susi
rizal
mamat
jaka
lala
budi
sinta
Kita akan membuat nama-nama tersebut
berurutan sesuai abjad
Berikut program nya :
/*
* program C untuk membaca nama , menyimpan dalam bentuk array
* dan mengurutkan dalam urutan abjad,mengeluarkan nama dan nama yang di berikan
* nama yang di urutkan dalam dua kolom berdampingan
*/
#include <stdio.h>
#include <string.h>
void main()
{
char name[10][8], tname[10][8], temp[8];
int i, j, n;
printf("Enter the value of n \n");
scanf("%d", &n);
printf("Enter %d names n", n);
for (i = 0; i < n; i++)
{
scanf("%s", name[i]);
strcpy(tname[i], name[i]);
}
for (i = 0; i < n - 1 ; i++)
{
for (j = i + 1; j < n; j++)
{
if (strcmp(name[i], name[j]) > 0)
{
strcpy(temp, name[i]);
strcpy(name[i], name[j]);
strcpy(name[j], temp);
}
}
}
printf("\n----------------------------------------\n");
printf("Input NamestSorted names\n");
printf("------------------------------------------\n");
for (i = 0; i < n; i++)
{
printf("%s\t\t%s\n", tname[i], name[i]);
}
printf("------------------------------------------\n");
}
Berikut screenshot hasil run nya :
Demikian tulisan ini saya akhiri mohon koreksinya apabila masih banyak yang kurang
Wassalammualaikum Wr.Wb
referensi : htttp://Sanfoundry.htm
Penulis : Mukhlisoh
Kampus : Eresha
NIM : 161011700376
Tidak ada komentar:
Posting Komentar