Algoritma Bubble Sort

3.2. Algoritma Bubble Sort

Di antara beberapa algoritma pengurutan yang ada,

algoritma bubble sort merupakan teknik yang paling

sederhana. Proses pencarian solusi dilakukan secara

brute force, langsung ke intinya, yaitu

membandingkan elemen-elemen dalam tabel.

Elemen yang lebih kecil ditukar posisinya dengan

elemen yang lebih besar bila posisi elemen yang

lebih kecil ada di bawah elemen yang lebih besar.

Jika tabel belum terurut, proses diulang kembali

sampai elemen paling kecil berada di posisi teratas

dan elemen lainnya sudah terurut.

Pseudo-code algoritma ini sebagai berikut [1] :

procedure BubbleSort (input/output L :

TabelInt, input n : integer)

{ Mengurutkan tabel L[1..N] sehingga terurut

menaik dengan metode pengurutan bubble

sort.

Masukan : Tabel L yang sudah terdefenisi

nilai-nilainya.

Keluaran: Tabel L yang terurut menaik

sedemikian sehingga

L[1] L[2] L[N].

}

Deklarasi

i : integer { pencacah untuk jumlah

langkah }

k : integer { pencacah,untuk

pengapungan 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

Kompleksitas algoritma ini adalah O(n2).

4. Pengurutan Menggunakan Divide and

Conquer

4.1 Pengertian Divide and Conquer

Divide and Conquer adalah metode pemecahan

masalah yang bekerja dengan membagi masalah

(problem) menjadi beberapa upa-masalah (subproblem)

yang lebih kecil, kemudian menyelesaikan

masing-masing upa-masalah secara independen, dan

akhirnya menggabung solusi masing-masing upamasalah

sehingga menjadi solusi masalah

semula [1].

Algoritma divide and conquer menawarkan

penyederhanaan masalah, dengan pendekatan tiga

langkah sederhana : pembagian masalah menjadi

sekecil mungkin, penyelesaian masalah-masalah

yang telah dikecilkan, kemudian digabungkan

kembali untuk mendapat solusi optimal secara

keseluruhan.

 

 

 

 

 

 

 

 

 

5. Sorting
Gambar. data sebelum dan sesudah dilakukan proses sorting.
Beberapa metode sorting mengurutkan data yang dikenal antara lain adalah:
1. Bubble Sort (sederhana tetapi lambat)
2. Quick Sort (cepat tetapi rumit)
3. Shell Sort (agak cepat dan tidak terlalu rumit)

5.1. Bubble Sort
Teknik ini menyusun data yang diinginkan secara berurutan dengan membandingkan elemen data yang ada, misalkan kita akan meyusun data secara (ascending) cacah naik. Maka lagoritma utamanya adalah seperti ini.

SYNTAX

for i:=1 to Jumlah_data-1 do
for j:=i+1 to Jumlah_data do
if Data[i]>Data[j] then
begin
t:=Data[i];
Data[i]:=Data[j];
Data[j]:=t;
end;

Contoh.
Misal kita punya data : 5 3 8 4 1 7 6 2 , dalam program
program mengurutkandata;

uses WinCrt;
type urutkan=array [1..8] of integer;
var i,j,t:integer;
anu:urutkan;
begin
anu[1]:=5; anu[2]:= 3;
anu[3]:= 8; anu[4]:= 4;
anu[5]:= 1; anu[6]:= 7 ;
anu[7]:=6 ; anu[8]:=2 ;
for i:=1 to 7 to
begin
for j:=i+1 to 8 to
begin
if anu[i]>anu[j] then
begin
t:=anu[i];
anu[i]:=anu[j];
anu[j]:=t;
end;
end;
end;
for i:=1 to 8 do
write (anu[i], ‘ ‘)
end.

5.2. Shell sort
Prinsipnya hampir sama dengan bubble sort tetapi dioptmisisasi sehingga lebih cepat. Ditemukan oleh Donald Shell. prinsipnya adalah membandingkan data dengan jarak tertentu dalam array.
SYNTAX

for jarak:= (Jumlah_data div 2) down to 1 do
for i:=1 to Jumlah_data-jarak do
if Data[i]>Data[i+jarak] then
begin
t:=Data[i];
Data[i]:=Data[i+jarak];
Data[i+jarak]:=t;
end;

Misalkan kita punya 8 data. Langkah pertama adalah membandingkan data pertama dengan ke lima, dsb. Jarak antara data adalah (8 div 2 :=4).
Langkah iterasi:
pertama, jarak adalah 4.
5 3 8 4 1 7 6 2
ke-1 perbandingan : ^ ^ (salah urutan, tukar)
1 3 8 4 5 7 6 2
ke-2 perbandingan : ^ ^ ( urutan benar, no tukar)
ke-3 perbandingan : ^ ^ (salah urutan, tukar)
1 3 6 4 5 7 8 2
ke-4 perbandingan : ^ ^ (salah urutan, tukar)
1 3 6 2 5 7 8 4 —-> Jarak 3.
ke-5 perbandingan : ^ ^ ( urutan benar, no tukar)
ke-6 perbandingan : ^ ^ ( urutan benar, no tukar)
ke-7 perbandingan : ^ ^ ( urutan benar, no tukar)
ke-8 perbandingan : ^ ^ ( urutan benar, no tukar)
ke-9 perbandingan : ^ ^ (salah urutan, tukar)
1 3 6 2 4 7 8 5 —-> Jarak 2.
ke-10 perbandingan :^ ^ ( urutan benar, no tukar)
ke-11 perbandingan : ^ ^ (salah urutan, tukar)
1 2 6 3 4 7 8 5
ke-12 perbandingan : ^ ^ (salah urutan, tukar)
1 2 4 3 6 7 8 5
ke-13 perbandingan : ^ ^ ( urutan benar, no tukar)
ke-14 perbandingan : ^ ^ ( urutan benar, no tukar)
ke-15 perbandingan : ^ ^ (salah urutan, tukar)
1 2 4 3 6 5 8 7 —-> Jarak 1.
ke-16 perbandingan :^ ^ ( urutan benar, no tukar)
ke-17 perbandingan : ^ ^ ( urutan benar, no tukar)
ke-18 perbandingan : ^ ^ (salah urutan, tukar)
1 2 3 4 6 5 8 7
ke-19 perbandingan : ^ ^ ( urutan benar, no tukar)
ke-20 perbandingan : ^ ^ (salah urutan, tukar)
1 2 3 4 5 6 8 7
ke-21 perbandingan : ^ ^ ( urutan benar, no tukar)
ke-22 perbandingan : ^ ^ (salah urutan, tukar)
1 2 3 4 5 6 7 8

 

 

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s