ALGORITMA DAN PEMOGRAMAN

ALGORITMA DAN PEMOGRAMAN

METODE BUBBLE SORT

Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara berulang kali membandingkan dua elemen data pada suatu saat dan menukar elemen data yang urutannya salah. Ide dari Bubble sort adalah gelembung air yang akan "mengapung" untuk array yang terurut menaik (ascending). Elemen bernilai kecil akan "diapungkan" (ke indeks terkecil), artinya diangkat ke "atas" (indeks terkecil) melalui pertukaran, Karena algoritma ini melakukan pengurutan dengan cara membandingkan elemen-elemen data satu sama lain, maka bubble sort termasuk ke dalam jenis algoritma comparison-based sortingProses pengurutan akan berlangsung sebanyak (n-satu) tahap/langkah, dimana n adalah jumlah elemen larik. Proses memerlukan 2 buah indeks, dimana indeks pertama (i) sebagai patokan yang bergerak dari posisi satu hingga (n-satu).

ILUSTRASI BUBBLE SORT
Indeks kedua (j), sebagai pembanding yang selalu bergerak dari posisi indeks patokan + satu (i+satu) hingga posisi n.
    Misal terdapat array satu dimensi L, yang terdiri dari 6 elemen array (n=6). Array L sudah berisi data seperti dibawah ini dan akan diurutkan secara ascending dengan algoritma Bubble Short
    L           [29     26         54         23        52        22]
    Elemen    1         2            3            4         5            6


Tahapan Bubble sort

Tahapan pertama
a.      Ambil elemen yang ke satu sebagai patokan
    Elemen yang ke satu = 29.
b.    Bandingkan nilai elemen yang kesatu dengan elemen yang kedua, ketiga, keempat, kelima dan keenam.
c.      Kalau nilai Lsatu > L2, maka tukarkan, sehingga larik menjadi sbb
     L       [26   29    54    23    52      22]   
 Elemen         1         2    3     4     5        6   



d. Bandingkan nilai Lsatu dengan L3. Kalau Lsatu       > L3, tukarkan nilai L3 dengan nilai Lsatu
        L     [26   29   54   23    52    22]   
         Elemen     1     2    3    4     5         6
e. Bandingkan nilai Lsatu dengan L4. Kalau Lsatu > L4, tukarkan nilai L4 dengan nilai Lsatu sehingga larik menjadi sbb :
        L    [23   29   54   26    52    22]   
         Elemen      1    2    3    4     5         6    
  

f. Bandingkan nilai Lsatu dengan L5. Kalau Lsatu > L5, tukarkan nilai L5 dengan nilai Lsatu
        L     [23   29   54   29    52    22]   
         Elemen     1         2         3           4         5           6
g. Bandingkan nilai Lsatu dengan L6. Kalau Lsatu > L6, tukarkan nilai L6 dengan nilai Lsatu sehingga larik menjadi sbb :
            L    [22   29   54   26    52    23]   
         Elemen      1    2    3    4     5         6    

Tahapan kedua

a.      Ambil elemen yang ke 2 sebagai patokan
    Elemen yang ke 2 = 29.
b.    Bandingkan nilai elemen yang kedua dengan ketiga, keempat, kelima dan keenam.
    Kalau nilai L2 > L3, maka tukarkan
            L    [22   29   54   26    52    23]   
             Elemen     1    2    3    4     5        6    
c.    Bandingkan nilai elemen yang kedua dengan nilai elemen yang keempat


Kalau nilai L2 > L4, maka tukarkan, sehingga larik menjadi sbb :
            L    [22   26   54   29    52    23]   
         Elemen     1    2    3    4     5      6
d.    Bandingkan nilai elemen yang kedua dengan nilai elemen kelima
    Kalau nilai L2 > L5, maka tukarkan, tetapi

e. Bandingkan nilai elemen L2 dengan nilai elemen L6. Kalau L2 > L6, maka tukarkan L6 dengan L2 sehingga larik menjadi sbb :

                L    [22   23   54   29    52    26]   
        Elemen     1     2    3    4     5      6


Tahapan ketiga


a.      Ambil elemen yang ke 3 sebagai patokan
    Elemen yang ke 3 = 54.
b.    Bandingkan nilai elemen yang tiga dengan nilai yang keempat, kelima dan keenam.
    Kalau nilai L3 > L4, maka tukarkan L4 dengan L3, larik menjadi sbb :
               L    [22   23   29   54    52    26]   
        Elemen     1    2    3    4     5      6

c.     Bandingkan nilai elemen yang ketiga dengan nilai elemen yang kelima. L3 < L5, tidak terjadi                  pertukaran.
d.    Bandingkan nilai elemen yang tiga dengan nilai elemen yang keenam. L3 > L6, tukarkan L3 dengan L6, larik menjadi :
            L    [22   23   26   54    52    29]   
        Elemen     1         2         3       4         5           6

Tahapan keempat

 a.     Ambilelemen yang ke 4 sebagai patokan
    Elemen yang ke 4 = 54.
 b.     Bandingkan nilai elemen yang keempat dengan nilai elemen yang kelima. L4 > L5
    tukarkan L4 dengan L5,  larik menjadi sbb
           L      [22   23   26   52    54    29]   
        Elemen       1    2    3    4     5      6

 b.     Bandingkan nilai elemen yang keempat dengan nilai elemen yang keenam. L4 > L6
    tukarkan L4 dengan L6,  larik menjadi sbb
           L      [22   23   26   29    54    52]   
        Elemen       1    2    3    4     5      6

Tahapan kelima

a.      Ambil elemen yang ke 5 sebagai patokan
    Elemen yang ke 5 = 54.
b.     Bandingkan nilai elemen yang kelima dengan nilai elemen yang keenam. L5 > L6

    tukarkan L5 dengan L6,  larik menjadi sbb
            L      [22   23   26   29    52    54]   
         Elemen       1    2    3    4     5      6
    Larik sudah terurut.
Algoritma Bubble
Deklarasi
    int n=6;
    int L[n];
    int i, j,X;
Deskripsi
 {Input/masukkan isi Larik}
    for (i= 1 to n step 1)
        write (“input elemen ke “, i)
        read (L[i];
    endfor

{proses sort}
    for (i=1 to n-1 step 1)
        for (j=i+1 to n step 1)
{bila L[i] > L[j],  maka tukarkan}
            if (L[i] > L[j]) then
            X = L[i];
            L[i] = L[j];
            L[j] = X;
             endif
        endfor
    endfor

{tampilkan isi larik}
for (i=1 to n step 1)
        write L[i];
    endfor

Posted in: ALGORITMA DAN PEMOGRAMAN