- Back to Home »
- Belajar Bahasa C , Mahir Bahasa C , Materi Bahasa C , Menguasai Bahasa C , Pemrograman Bahasa C »
- Metoda Pengurutan Bubble Sort Dengan Bahasa C
Posted by : ClownMan
Saturday, August 1, 2015
Sekarang kita akan menginjak
ke sesuatu yang sedikit lebih kompleks, yaitu mengurutkan array. Ada banyak
metoda pengurutan array, namun setidaknya ada dua metoda yang cukup populer,
yaitu Bubble Sort dan Quick Sort. Pada pembahasan kali ini terlebih dahulu kita
akan mendiskusikan tentang pengurutan array dengan metoda Bubble Sort.
Untuk
mempermudah Anda dalam mempelajari Bubble Sort ini, terlebih dahulu akan
diberikan suatu contoh ilustrasi.
Misalnya Anda
memiliki empat buah angka yang ingin diurutkan dari yang terkecil hingga yang
terbesar (Ascending). Proses Bubble Sort akan membagi proses pengurutan menjadi
beberapa tahap.
Tahap pertama adalah
pembandingan bilangan yang pertama dengan tiga bilangan yang lainnya. Apabila
ditemukan bilangan yang lebih kecil daripada bilangan yang pertama tadi, maka
bilangan tersebut akan ditukar tempatnya sehingga sekarang bilangan yang lebih
kecil tersebut akan menempati posisi pertama. Proses pembandingan tersebut akan
berlangsung tiga kali karena terdapat tiga bilangan yang lain. Pada akhir
proses pembandingkan, maka pada posisi yang pertama akan didapatkan bilangan
yang nilainya paling kecil.
Pada tahap kedua,
bilangan yang terletak pada posisi pertama (setelah penukaran tadi) diabaikan,
karena posisinya sudah benar. Jadi sekarang bilangan yang kedua akan
dibandingkan dengan bilangan yang ketiga dan keempat, sehingga ada dua kali
pembandingan. Apabila dalam proses pembandingan tersebut ditemukan bilangan
yang nilainya lebih kecil daripada bilangan yang kedua, maka akan dilakukan
tukar tempat, sehingga bilangan yang lebih kecil tersebut sekarang akan
menempati posisi kedua.
Pada tahap
ketiga, bilangan pada posisi pertama dan kedua (setelah penukaran pada tahap
kedua tadi) diabaikan karena posisinya sudah benar. Sekarang tinggal
membandingkan bilangan ketiga dan keempat. Apabila bilangan keempat lebih kecil
daripada bilangan ketiga, maka dilakukan tukar tempat. Proses selesai sampai
pada tahap ini, karena apabila bilangan ketiga posisinya sudah benar, maka
bilangan keempat otomatis posisinya akan benar.
Sebagai
visualisasi tahap-tahap pengurutan tersebut, lihat gambar 1 hingga gambar 3.
Pada ketiga gambar tersebut diberikan contoh tahap-tahap pengurutan untuk
bilangan 10, 5, 7, dan 3.
Dari ilustrasi
di atas dapat dijelaskan bahwa:
·
Jumlah tahap pengurutan = jumlah bilangan –
1
·
Banyaknya perbandingan pada setiap tahap =
jumlah bilangan – no tahap
Contoh:
Untuk pengurutan
7 bilangan:
·
Jumlah tahap = 7 – 1 = 6 tahap
·
Banyaknya perbandingan:
o Tahap
1: 7 – 1 = 6
o Tahap
2: 7 – 2 = 5
o Tahap
3: 7 – 3 = 4
o Tahap
4: 7 – 4 = 3
o Tahap
5: 7 – 5 = 2
o Tahap
6: 7 – 6 = 1
Dengan memakai
pengertian tersebut maka dapat disusun sebuah flow chart yang menggambarkan
alur pemrograman pengurutan dengan metoda Bubble Sort. Flow chart tersebut
diberikan pada gambar 4. Keterangan gambar tersebut adalah sebagai berikut:
·
n = jumlah bilangan
·
i = no tahap
·
j = jumlah perbandingan
·
A[] = array yang digunakan
Sekarang,
berdasarkan flow chart tersebut, akan kita bangun suatu program untuk
pengurutan array dengan metoda Bubble Sort. Program tersebut diberikan pada
listing 1.
Listing 1. Pengurutan secara ascending dengan metoda Bubble
Sort
#include <stdio.h>
#define N 20
int bubble(int n);
int i,j,A[N];
main()
{
int jml;
clrscr();
printf("METODA BUBBLE SORT \n\n");
printf("Masukkan jumlah bilangan (maks 20) : ");
scanf("%d",&jml);
printf("\n");
// input data
for (i=0;i<jml;i++)
{
printf("Bilangan
ke %d : ",i+1);
scanf("%d",&A[i]);
}
printf("\n");
// mengurutkan data
bubble(jml);
// menampilkan data
printf("Data yang sudah terurut : \n");
for (i=0;i<jml;i++)
{
printf("%d\n",A[i]);
}
}
// fungsi bubble
int bubble(int n)
{
int temp;
for (i=1;i<=n-1;i++)
{
for
(j=i;j<n;j++)
{
if
(A[i-1]>A[j])
{
temp
= A[i-1];
A[i-1]
= A[j];
A[j]
= temp;
}
}
}
}
|
Salah satu
kemungkinan hasil run program tersebut adalah sebagai berikut:
METODA BUBBLE SORT
Masukkan jumlah bilangan (maks 20) : 4
Bilangan ke 1 : 10
Bilangan ke 2 : 5
Bilangan ke 3 : 7
Bilangan ke 4 : 3
Data yang sudah terurut :
3
5
7
10
Bandingkan
dengan gambar 5.
gambar 5
Dengan pola
pikir yang sama dapat dibuat sebuah program untuk melakukan sort secara
Descending (menurun). Program tersebut diberikan pada listing 2.
Listing 2. Pengurutan secara descending dengan metoda Bubble
Sort
#include <stdio.h>
#define N 20
int bubble(int n);
int i,j,A[N];
main()
{
int jml;
clrscr();
printf("METODA BUBBLE SORT \n\n");
printf("Masukkan jumlah bilangan (maks 20) : ");
scanf("%d",&jml);
printf("\n");
// input data
for (i=0;i<jml;i++)
{
printf("Bilangan
ke %d : ",i+1);
scanf("%d",&A[i]);
}
printf("\n");
// mengurutkan data
bubble(jml);
// menampilkan data
printf("Data yang sudah terurut : \n");
for (i=0;i<jml;i++)
{
printf("%d\n",A[i]);
}
}
// fungsi bubble
int bubble(int n)
{
int temp;
for (i=1;i<=n-1;i++)
{
for
(j=i;j<n;j++)
{
if
(A[i-1]<A[j])
{
temp
= A[i-1];
A[i-1]
= A[j];
A[j]
= temp;
}
}
}
}
|