SORTING (Bubble dan Quick Sort)
A. Bubble Sort
1. Definisi Bubble Sort
Bubble
Sort ini merupakan proses pengurutan yang secara berangsur-angsur berpindah ke
posisi yang tepat karena itulah dinamakan Bubble
yang artinya gelembung. Algoritma ini akan mengurutkan data dari yang terbesar
ke yang terkecil (ascending) atau
sebaliknya (descending). Secara
sederhana, bisa didefenisikan algoritma Bubble
Sort adalah pengurutan dengan cara pertukaran data dengan data disebelahnya
secara terus menerus sampai dalam satu iterasi tertentu tidak ada lagi
perubahan. Untuk belajar algoritma Bubble
Sort ini kita hanya perlu memahami cara yang digunakan untuk mengurutkan
data, sederhananya algoritma ini menggunakan perbandingan dalam operasi antar
elemennya. Algoritma Bubble Sort
merupakan proses pengurutan yang secara berangsur-angsur memindahkan data ke
posisi yang tepat. Karena itulah, algoritma ini dinamakan “bubble” atau yang
jika diterjemahkan ke dalam Bahasa Indonesia, artinya yaitu gelembung. Fungsi
algoritma ini adalah untuk mengurutkan data dari yang terkecil ke yang terbesar
(ascending) atau sebaliknya (descending). Metode pengurutan gelembung
(Bubble Sort) ini terinspirasi oleh
gelembung sabun yang berada di permukaan air. Karena berat jenis gelembung
sabun yang lebih ringan ketimbang berat jenis air, maka gelembung sabun akan
selalu terapung ke atas permukaan. Prinsip inilah yang dipakai pada algoritma
pengurutan gelembung.
Secara
sederhana, bisa didefinisikan bahwa algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan
data di sebelahnya secara terus menerus sampai pada satu iterasi tertentu
dimana tidak ada lagi perubahan yang signifikan. Sebelum kita masuk untuk
membuat program, berikut ini adalah syarat dan langkah-langkah yang harus
diperhatikan pada metode Bubble Sort :
a. Jumlah iterasi
sama dengan banyaknya bilangan dikurang 1.
b. Di setiap iterasi,
jumlah pertukaran bilangannya sama dengan jumlah banyaknya bilangan.
c. Dalam algoritma Bubble Sort, meskipun deretan bilangan
tersebut sudah terurut, proses sorting akan tetap dilakukan.
d. Tidak ada
perbedaan cara yang berarti untuk teknik algoritma Bubble Sort Ascending dan
Descending.
1. Algoritma Buble Sort
Alg.Buble Sort(Ascending)
for(i=0;i<=n-2;i++)
{for(j=n-1;j>=i+1;j--)
{if data[j]<data[j-1]
{buble = data[j]
Data[j] = data [j-1]
Data[j-1] = buble }
}
}
2. Contoh Program
a) Listing Program
b) Hasil Running
B. Quick Sort
1. Definisi Quick Sort
Quicksort adalah
algoritma pengurutan cepat yang tidak hanya digunakan dalam dunia pendidikan,
tetapi banyak diterapkan secara prkaktik. Rata-rata, biasanya memiliki kompleksitas O (n log n),
membuat quicksort sangat cocok untuk mengurutkan volume data yang besar. Ide
dari algoritma ini cukup sederhana dan ketika kita menyadarinya, kita dapat
menulis quicksort secepat bubblesort.
Strategi divide-and-conqueror
digunakan di dalam quicksort. Di bawah ini akan dijelaskan langkah-langkahnya :
a. Pilih nilai pivot
Kita ambil nilai
di tengah-tengah elemen sebagai sebagai nilai dari pivot, tetapi bisa nilai
mana saja.
b. Partisi
Atur ulang semua
elemen sedemikian rupa, lalu semua elemen yang lebih rendah daripada pivot
dipindahkan ke sebelah kiri dari array/list dan semua elemen yang lebih besar
dari pivot dipindahkan ke sebelah kanan dari array/list. Nilai yang sama dengan pivot dapat diletakkan
di mana saja dari array. Ingat, mungkin array/list akan dibagi dalam bagian
yang tidak sama.
c. Urutkan semua
bagian (kiri/kanan)
Aplikasikan
algoritma quicksort secara rekursif pada bagian sebelah kiri dan kanan.
1) Keunggulan Quick
sort:
Secara umum
memiliki kompleksitas O(n log n).
a) Algoritmanya
sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur
mesin secara efisien.
b) Dalam prakteknya
adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan,
seperti mergesort dan heapsort.
c) Melakukan proses
langsung pada input (in-place) dengan sedikit tambahan memori.
d) Bekerja dengan
baik pada berbagai jenis input data (seperti angka dan karakter).
2) Kekurangan Quick
short
a) Sedikit kesalahan
dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak
benar atau tidak pernah selesai).
b) Memiliki
ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk
memiliki kompleksitas O(n2).
c) Secara umum
bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam
hal inputnya bernilai sama).
d) Pada penerapan
secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat
menghabiskan stack dan memacetkan program.
e) Pada bahasa
pemrograman, quicksort ada dalam pustaka stdlib.h untuk bahasa C, dan class
TList dan TStringList dalam Delphi (Object Pascal) maupun FreePascal.
2. Algoritma Quick Sort
Alg.Quick Sort(Data,left,right)
1) i=left, j=right
pivot= data[tengah] =
data[left+right/2]
2) Ketentuan partisi
a. data[i] < pivot = i++
b. data [j] > pivot = j—
i<=j = data [i] ß data[j]
i++;j—
3) Rekursif
Left < j à quicksort (data,left,j)
I < right à quicksort (data,i,right)
3) Contoh Program
a) Listing Program
b) Hasil Running
Tidak ada komentar:
Posting Komentar