Algoritma bubble sort (pengurutan apung) terinsipari dari gelmbung sabun yang berada diatas permukaan air. Apabila kita ingin larik terurut menaik, maka elemen larik yang berharga paling kecil “diapungkan”, artinya diangkat ke “atas” (keujung kiri larik) melalui proses pertukaran.
Contoh : Pengurutan Bubble sort dengan data sebagai beriktu :
23
|
34
|
8
|
5
|
50
|
15
|
1
|
2
|
3
|
4
|
5
|
6
|
<-- arah pembandingan
Proses 1 :
| |||
Elemen yang dibandingkan
|
Pertukaran ?
|
Hasil sementara
| |
L[6] < L[5] ? (15 < 50 ?)
|
Ya
|
23, 34, 8, 5, 15, 50
| |
L[5] < L[4] ? (15 < 5 ?)
|
Tidak
|
23, 34, 8, 5, 15, 50
| |
L[4] < L[3] ? (5 < 8 ?)
|
Ya
|
23, 34, 5, 8, 15, 50
| |
L[3] < L[2] ? (5 < 34 ?)
|
Ya
|
23, 5, 34, 8, 15, 50
| |
L[2] < L[1] ? (5 < 23 ?)
|
Ya
|
5, 23, 34, 8, 15, 50
|
Hasil akhir proses 1 :
5
|
23
|
34
|
8
|
15
|
50
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 2 :
| |||
Elemen yang dibandingkan
|
Pertukaran ?
|
Hasil sementara
| |
L[6] < L[5] ? (50 < 15 ?)
|
Tidak
|
5, 23, 34, 8, 15, 50
| |
L[5] < L[4] ? (15 < 8 ?)
|
Tidak
|
5, 23, 34, 8, 15, 50
| |
L[4] < L[3] ? (8 < 34 ?)
|
Ya
|
5, 23, 8, 34, 15, 50
| |
L[3] < L[2] ? (8 < 23 ?)
|
Ya
|
5, 8, 23, 34, 15, 50
|
Hasil akhir proses 2 :
5
|
8
|
23
|
34
|
15
|
50
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 3 :
| |||
Elemen yang dibandingkan
|
Pertukaran ?
|
Hasil sementara
| |
L[6] < L[5] ? (50 < 15 ?)
|
Tidak
|
5, 8, 23, 34, 15, 50
| |
L[5] < L[4] ? (15 < 34 ?)
|
Ya
|
5, 8, 23, 15, 34, 50
| |
L[4] < L[3] ? (15 < 23 ?)
|
Ya
|
5, 8, 15, 23, 34, 50
|
Hasil akhir proses 3 :
5
|
8
|
15
|
23
|
34
|
50
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 4 :
| |||
Elemen yang dibandingkan
|
Pertukaran ?
|
Hasil sementara
| |
L[6] < L[5] ? (50 < 34 ?)
|
Tidak
|
5, 8, 15, 23, 34, 50
| |
L[5] < L[4] ? (34 < 23 ?)
|
Tidak
|
5, 8, 15, 23, 34, 50
|
Hasil akhir proses 4 :
5
|
8
|
15
|
23
|
34
|
50
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 5 :
| |||
Elemen yang dibandingkan
|
Pertukaran ?
|
Hasil sementara
| |
L[6] < L[5] ? (50 < 34 ?)
|
Tidak
|
5, 8, 15, 23, 34, 50
|
Hasil akhir proses 5 :
5
|
8
|
15
|
23
|
34
|
50
|
1
|
2
|
3
|
4
|
5
|
6
|
Hasil akhir proses 5 menyisakan satu elemen (yaitu 50) yang tidak perlu diurutkan lagi, maka pengurutan selesai.
Procedure Bubblesort (input/output L : Larikint, input n : integer)
{Mengurutkan larik L[1..n] sehingga terurut menaik dengan metode Bubble Sort}
{I.S. : Elemen larik L sudah terdefinisi nilai-nilainya }
{F.S. : Elemen larik L terurut menaik sedemikian sehingga L[1] < L[2] < . . . < L[n] }
Kamus
I : integer {Pencacah untuk jumlah langkah}
K : integer {Pencacah, untuk Bubble pada setiap langkah}
Temp : integer {peubah bantu untuk pertukaran }
Algoritma :
For i <-- 1 to n-1 do
For k <-- n downto i +1 do
If ( L[k] < L[k-1] ) then
{ pertukarkan L[k] dengan L[k-1] }
Temp <-- L[k]
L[k] <-- L[k-1]
L[k-1] <-- temp
Endif
Endfor
Endfor
Sumber : Munir, Renaldi. (2011). Algoritma & Pemrogramman Dalam Bahasa Pascal dan C. (edisi revisi). Bandung ; INFORMATIKA.
0 komentar:
Posting Komentar