Metoda Pengurutan Bubble Sort Dengan Bahasa C++

Jika kita 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.

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 #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 {    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 {    printf("%d\n",A[i]); } } // fungsi bubble int bubble(int n) { int temp; for (i=1;i<=n-1;i++) {    for (j=i;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 #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 {    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 {    printf("%d\n",A[i]); } } // fungsi bubble int bubble(int n) { int temp; for (i=1;i<=n-1;i++) {    for (j=i;j    {                if (A[i-1]                {                            temp = A[i-1];                            A[i-1] = A[j];                            A[j] = temp;                }    } } }