Pada contoh sebelumnya telah belajar membuat program yang digunakan untuk mencari nilai maksimal dan/atau minimal dari sebuah array, bila belum membacanya silahkan baca di sini. Sekarang 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 tulisan kali ini terlebih dahulu akan didiskusikan tentang pengurutan array dengan metoda Bubble Sort.
Untuk mempermudah dalam mempelajari Bubble Sort ini, terlebih dahulu akan diberikan suatu contoh ilustrasi.
Misalnya : 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-gambar di bawah ini :
Pada ketiga gambar tersebut di atas 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 di bawah ini :
Keterangan gambar di atas 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 di bawah ini :
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; } } } } |
Semoga Bermanfaat dan Selamat Mencoba.