Pada contoh sebelumnya Anda telah belajar membuat program yang digunakan untuk mencari
nilai maksimal dan/atau minimal dari sebuah array. 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.
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;
}
}
}
}
Contoh :
BUBBLE
#include <stdio.h>
#define N 20
int bubble(int n);
int i,j,A[N];
int main()
{
int jml;
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 terurut : \n");
for (i=0;i<jml;i++);
{
printf("%d\n",A[i]);
}
system
("pause");
}
//fungsi bubble
int bubble(int n)
{
int bil;
for
(i=1;i<=n-1;i++)
{
for(j=i;j<n;j++)
{
if (A[i-1]>A[j])
{
bil=A[i-1];
A[i-1]=A[j];
A[j]=bil;
}
}
}
}
OUTPUT
Tidak ada komentar:
Posting Komentar