Bubble Sort

Algoritma Bubble Sort untuk Pengurutan (Sorting)

Pengurutan merupakan salah satu proses dasar yang sering dibahas dalam algoritma dan struktur data. Dan salah satu algoritma klasik dan paling sederhana dalam hal pengurutan (sorting) adalah algoritma Bubble Sort. Terlepas dari beberapa kekurangan yang membuat algoritma ini tidak banyak digunakan dalam proses pengurutan di aplikasi, namun tidak bisa dipungkiri, algoritma ini boleh dikatakan sebagai pionir algoritma sorting. Di dalam matakuliah Algoritma dan Struktur Data di berbagai perguruan tinggi juga bisa dipastikan memasukkan konsep pengurutan menggunakan algoritma Bubble sebagai salah satu pokok bahasan.

Untuk itulah, saya rasa tidak ada salahnya untuk sedikit membahas mengenai algoritma bubble sort ini. Tentunya disertai contoh program sederhana yang menerapkan pengurutan menggunakan algoritma bubble sort. Contoh program akan disajikan dalam Bahasa C dan PHP.

Algoritma bubble sort dalam proses pengurutan data secara sederhana bisa diibaratkan seperti halnya gelembung udara (bubble). Algoritma ini akan menggeser  nilai yang terkecil atau terbesar (sesuai dengan jenis pengurutan, ascending atau descending) ke posisi ujung dari daftar. Demikian seterusnya hingga semua daftar dalam keadaan terurut. Proses dasar yang terjadi dalam algoritma ini adalah proses pertukaran nilai (swapping).

Berikut ini algoritma Bubble Sort yang saya kutip:      

    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

Contoh penerapan Algoritma Bubble Sort dalam Bahasa C
    #include "stdio.h"
    #include "conio.h"
    #define n 7
    void main()
    {
    int A[n] = {15,10,7,22,17,5,12};
    int X, I, K;
    printf("Sebelum di-sort\n");
    for (I=0; I <= n-1; I++)
    printf("%3i", A[I]);
    printf("\n");
    
    K=0;
    while(K<=n-2)
    {
    I=0;
    while(I<=n-2 - K)
    {
    if (A[I] > A[I+1])
    {
    X = A[I];
    A[I] = A[I+1];
    A[I+1] = X;
    }
    I++;
    }
    K++;
    }
    printf("Sesudah di-sort\n");
    for (I=0; I<= n-1; I++)
    printf("%3d", A[I]);
    }

Contoh penerapan Algoritma Bubble Sort dalam PHP
    <?php
    define ("n", 7);
    $A = array(15,10,7,22,17,5,12);
    echo "<h1>Sebelum di-sort</h1>";
    for ($I=0; $I <= n-1; $I++)
    echo "$A[$I] ";
    
    $K=0;
    while($K<=n-2)
    {
    $I=0;
    while($I<=n-2 - $K)
    {
    if ($A[$I] > $A[$I+1])
    {
    $X = $A[$I];
    $A[$I] = $A[$I+1];
    $A[$I+1] = $X;
    }
    $I++;
    }
    $K++;
    }
    echo "<h1>Sesudah di-sort</h1>";
    for ($I=0; $I<= n-1; $I++)
    echo "$A[$I] ";
    ?>

Data tersebut masih dalam keadaan acak. Maka ilustrasi pengurutan dengan bubble sortnya akan terlihat seperti pada table dibawah ini :

LANGKAH 1 :
1     2     3     4     5     6     POSISI DATA
22     10     15     3     8     2     Data Awal
22     10     15     3     2     8     tukar data 5 dengan 6
22     10     15     2     3     8     tukar data 4 dengan 3
22     10     2     15     3     8     tukar data 3 dengan 2
22     2     10     15     3     8     tukar data 2 dengan 1
2     22     10     15     3     8     LANGKAH 1 SELESAI

LANGKAH 2 :
1     2     3     4     5     6     POSISI DATA
2     22     10     15     3     8     Data Langkah 1 Akhir
2     22     10     3     15     8     tukar data 4 dengan 3
2     22     3     10     15     8     tukar data 3 dengan 2
2     3     22     10     15     8     LANGKAH 2 SELESAI

LANGKAH 3 :
1     2     3     4     5     6     POSISI DATA
2     3     22     10     15     8     Data Langkah 2 Akhir
2     3     22     10     8     15     tukar data 5 dengan 6
2     3     22     8     10     15     tukar data 4 dengan 3
2     3     8     22     10     15     LANGKAH 3 SELESAI

LANGKAH 4 :
1     2     3     4     5     6     POSISI DATA
2     3     8     22     10     15     Data Langkah 3 Akhir
2     3     8     22     10     15     tukar data 5 dengan 4
2     3     8     10     22     15     LANGKAH 4 SELESAI

LANGKAH 5 :
1     2     3     4     5     6     POSISI DATA
2     3     8     10     22     15     Tukar data 5 dengan 6
2     3     8     10     15     22     TERURUT


CATATAN :
Sebelum dilakukan Proses penukaran data pada penjelasan tabel diatas, terlebih dahulu didahului oleh proses perbandingan. dimana perbandingan datanya tergantung pada jenis sort nya, pada penjelasan tabel diatas, saya menggunakan pengurutan data secara accending. sehingga, perbandinganya menjadi jika data n > data n+1 maka ditukar, selama tidak memenuhi statemen itu, maka data tidak akan ditukar.