Wednesday, March 13, 2013

Algoritma Metode Pengurutan Bubble Sort

Metode Pengurutan
Pengurutan adalah menyusun kembali sekumpulan data yang ada sehingga data tersebut menjadi urut. Berdasarkan urutannya, maka pengurutan ada 2 jenis, yaitu pengurutan ascending, yaitu urutan menaik dari kecil ke besar; dan pengurutan descending, yaitu urutan menurun dari besar ke kecil.
Metode yang digunakan untuk mengurutkan data disebut metode pengurutan. Terdapat banyak sekali metode pengurutan, namun dalam tulisan ini hanya dibicarakan 3 metode, yaitu metode bubble (gelembung), selection (seleksi), dan insertion (penyisipan). Metode ini yang kita pelajari karena metode ini merupakan metode yang mudah dipelajari dan mendasar. Dalam tulisan ini, semua metode yang disajikan adalah metode pengurutan secara ascending. Mengenai metode pengurutan descending diserahkan pada pembaca sebagai latihan.


1. Metode Pengurutan Bubble (Bubble Sort)

Ide dasar dari metode ini adalah
1. membawa data terkecil dari data ke-1 s/d ke-n menjadi data[1]
2. membawa data terkecil dari data ke-2 s/d ke-n menjadi data[2]
3. ...
4. membawa data terkecil dari data ke-(n-1) s/d ke-n menjadi data[n-1]


Untuk melakukan langkah pertama dilakukan dengan cara berikut:

1. bandingkan data ke-1 dengan data ke-2, jika data[1] > data[2], maka tukar.
2. bandingkan data ke-1 dengan data ke-3, jika data[1] > data[3], maka tukar.
3. ...
4. bandingkan data ke-1 dengan data ke-n, jika data[1] > data[n], maka tukar.
Setelah melakukan langkah ini, maka data[1] merupakan data terkecil dari data ke-1 s/d data ke-n

.
Untuk melakukan langkah ke-2 dilakukan dengan cara berikut:
1. bandingkan data ke-2 dengan data ke-3, jika data[2] > data[3], maka tukar.
2. bandingkan data ke-2 dengan data ke-4, jika data[2] > data[4], maka tukar.
3. ...
4. bandingkan data ke-2 dengan data ke-n, jika data[2] > data[n], maka tukar.
Setelah melakukan langkah ini, maka data[2] merupakan data terkecil dari data ke-2 s/d data ke-n.
Lakukan langkah ke-3 dengan pola yang sama hingga langkah ke-(n-1). Maka data akan terurut secara ascending


Perhatikan bahwa langkah-langkah di atas dapat disimpulkan menjadi berikut:
1. Untuk k = 1, lakukan
a. jika data[1] > data[2], maka tukar
b. jika data[1] > data[3], maka tukar
c. ...
d. jika data[1] > data[n], maka tukar
2. Untuk k = 2, lakukan
a. Jika data[2] > data[3], maka tukar
b. Jika data[2] > data[4], maka tukar
c. ...
d. Jika data[2] > data[n], maka tukar
3. ...
4. Untuk k = n-1, lakukan
a. Jika data[n-1] > data[n], maka tukar
Perhatikan bahwa untuk masing-masing nilai k, kita melakukan proses perbandingan data[k] dengan data[m] dengan nilai m adalah dari k+1 s/d n.
Perhatikan contoh berikut ini:
Misalkan kita mempunyai data berikut: 2, 7, 3, 1, 5, 4