Rabu, 01 Juni 2011

Algoritma Bubble Sort

  Agus Nur Ikhsan       Rabu, 01 Juni 2011
Pengertian/Konsep Buble Sort


Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.
Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.



Algoritma Bubble Sort
  1. Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).
  2. Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
  3. Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.
  4. Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.

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. 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 :

Procedure Bubble_Sort(input/output x : larik, input n : byte)

Deklarasi:
       Larik = array [1..100] 0f integer
       i,a : byte
       k : larik
       1.bantu : integer
Deskripsi

Deskripsi

for i ß 1 to n-1 do    
for j ß i+1 to n do
if x[i] > x[j] then // data sebelah kiri > kanan
tukar(x[i], x[j])
end if
end for
end for

Fungsi:
















Data awal :


[8, 4, 7, 3, 1, 2, 6, 5]


8ßà4, 4ßà3, 3ßà1


fase 1


[1, 8, 7, 4, 3, 2, 6, 5]


8ßà7, 7ßà4, 4ßà3, 3ßà2


fase 2


[1, 2, 8, 7, 4, 3, 6, 5]


8ßà7, 7ßà4, 4ßà3


fase 3


[1, 2, 3, 8, 7, 4, 6, 5]


8ßà7, 7ßà4


fase 4


[1, 2, 3, 4, 8, 7, 6, 5]


8ßà7, 7ßà6, 6ßà5


fase 5


[1, 2, 3, 4, 5, 8, 7, 6]


8ßà7, 7ßà6


fase 6


[1, 2, 3, 4, 5, 6, 8, 7]


8ßà7


fase 7


[1, 2, 3, 4, 5, 6, 7, 8]




fase 8


[1, 2, 3, 4, 5, 6, 7, 8]













Dan ini adalah contoh penerapan Algoritma Bubble Sort dalam Bahasa C++

#include "stdio.h"
#include "conio.h"
#define n 8
void main()
{
int A[n] = {8,4,7,3,1,2,6,5};
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]);
}

Naa,,, itulah programnya,,,
Dan ini gambaran hasilnya...






Na itulah hasil dari pengetahuan ku selama kuliah.,,,,









logoblog

Thanks for reading Algoritma Bubble Sort

Previous
« Prev Post

Tidak ada komentar:

Posting Komentar