BAB
I
PENDAHULUAN
1.1 Latar Belakang
Pengurutan dalam
pengolahan data dirasakan sangat penting dalam Teknologi Informasi. Kita tahu
bahwa pemecahan permasalahan pengolahan data dapat menjadi lebih efektif dan
efisien bila data sudah dalam keadaan terurut. Seperti dalam proses pencarian
data (searching), algoritma pencarian tingkat lanjut yang lebih efektif
daripada cara konvensional seperti Binary Search ataupun Interpolation Search
membutuhkan data yang sudah terurut. Contoh lain di mana data terurut
dibutuhkan adalah dalam penggabungan data menggunakan metode merging.
Pengurutan adalah proses mengatur sekumpulan objek
menurut urutan atau susunan tertentu. Urutan objek tersebut dapat menaik
(ascending) atau menurun (descending). Adanya kebutuhan
terhadap proses pengurutan memunculkan bermacam-macam metode pengurutan. Tidak
ada metode yang terbaik untuk pengurutan. Kebanyakan metode pengurutan
sederhana hanya bagus untuk volume data yang kecil tetapi lambat untuk ukuran
data yang besar. Metode pengurutan yang lebih cepat pun (seperti quick sort dan
merge sort) memang bagus untuk mengurutkan data yang banyak, tetapi tidak bagus
untuk ukuran data yang sedikit karena memerlukan beban tambahan (overhead) yang
boros waktu dan memori.
Di antara banyak algoritma
pengurutan terdapat Comparison Sort atau pengurutan dengan pembandingan merupakan proses
pengurutan dengan melakukan pembandingan antardata, yang kemudian diikuti
dengan pertukaran data bila tidak sesuai dengan syarat keterurutan tertentu.
1.2
Rumusan Masalah
Berdasarkan
latar belakang diatas,
dapat ditarik beberapa rumusan masalah, yaitu sebagai berikut :
1.2.1
Apa yang dimaksud dengan Bubble Sort?
1.2.2
Bagaimana ilustrasi dari Bubble Sort?
1.2.3
Bagaimana notasi algoritmik dan kompleksitas waktu dari Bubble Sort tersebut?
1.2.4
Bagaimana kelebihan dan kelemahan dari Bubble Sort?
1.2.5
Apa yang dimaksud dengan Counting Sort Algorithm?
1.2.6
Bagaimana Implementasi Counting Sort?
1.2.7
Bagaimana algoritma dan kompleksitas waktu Counting Sort?
1.3
Tujuan
1.3.1
Untuk mengetahui apa yang dimaksud dengan Bubble Sort.
1.3.2
Untuk mengetahui bagaimana ilustrasi Bubble Sort.
1.3.3
Untuk mengetahui bagaimana notasi algoritmik dan kompleksitas waktu dari Bubble Sort tersebut.
1.3.4
Untuk mengetahui bagaimana kelebihan dan kelemahan dari Bubble Sort.
1.3.5
Untuk mengethaui pengertian Counting Sort Algorithm.
1.3.6
Untuk mengetahui bagaimana implementasi Counting Sort.
1.3.7
Untuk mengetahui bagaimana algoritma dan kompleksitas waktu Counting
Sort.
BAB II
PEMBAHASAN
2.1
Ide Dasar Bubble Sort
Algoritma bubble sort adalah salah
satu algoritma pengurutan yang paling simple, baik dalam hal pengertian maupun
penerapannya. Ide dari algoritma ini adalah mengulang proses pembandingan
antara tiap-tiap elemen array dan menukarnya apabila urutannya salah.
Pembandingan elemen-elemen ini akan terus diulang hingga tidak perlu dilakukan
penukaran lagi. Algoritma ini termasuk dalam golongan algoritma comparison
sort, karena menggunakan perbandingan dalam operasi antar elemennya.
.Diberi nama “Bubble” karena proses pengurutan
secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti
gelembung yang keluar dari sebuah gelas bersoda. Gagasan dasar dari algoritma
Bubble Sort adalah membandingkan sepasang elemen yang berurutan di dalam larik
dan mempertukarkan keduanya jika perlu. Nama bubble
sort ini berasal dari sifat elemen terbesar yang selalu naik ke atas seperti
bubble.
Ide dari bubble sort adalah sebagai berikut :
F Algoritma dimulai dari elemen paling
awal.
F 2 buah elemen pertama dari list
dibandingkan.
F Jika elemen pertama lebih besar dari
elemen kedua,dilakukan pertukaran.
F Langkah 2 dan 3 dilakukan lagi terhadap elemen kedua dan ketiga,
seterusnya sampai ke ujung elemen
F Bila sudah sampai ke ujung dilakukan lagi ke awal sampai tidak ada
terjadi lagi pertukaran elemen.
F Bila tidak ada pertukaran elemen lagi, maka list elemen sudah
terurut
Algoritma ini seolah-olah menggeser satu per satu
elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya,
ascending atau descending.
F Pengurutan Ascending : Jika elemen
sekarang lebih besar dari elemen
berikutnya maka kedua elemen tersebut ditukar (Pengurutan dari kecil ke besar).
F Pengurutan Descending : Jika elemen
sekarang lebih kecil dari elemen
berikutnya, maka kedua elemen tersebut ditukar (Pengurutan dari besar ke
kecil).
Ketika satu
proses telah selesai, maka bubble sort akan mengulangi proses, demikian
seterusnya dari 0 sampai dengan iterasi sebanyak n-1. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah
diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai
perurutan yang telah diinginkan.
2.2 Ilustrasi dari Bubble Sort
Berikut ini adalah gambaran dari
algoritma bubble sort.
Misalkan kita mempunyai sebuah array
dengan elemen-elemen “4 2 5 3 9”. Proses yang akan terjadi apabila digunakan algoritma
bubblesort adalah sebagai berikut.
Pass pertama
(4 2 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 4 3 5 9)
Pass kedua
(2 4 3 5 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
Pass ketiga
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
Dapat dilihat pada proses di atas,
sebenarnya pada pass kedua, langkah kedua, array telah terurut. Namun algoritma
tetap dilanjutkan hingga pass kedua berakhir. Pass ketiga dilakukan karena
definisi terurut dalam algoritma bubble sort adalah tidak ada satupun penukaran
pada suatu pass, sehingga pass ketiga dibutuhkan untuk memverifikasi keurutan
array tersebut.
***Kura-kura dan Kelinci pada Bubble
Sort***
Dalam algoritma Bubble Sort ini,
terdapat beberapa ciri khas yang cukup menonjol, Ciri khas dari algoritma
Bubble Sort ini adalah cepatnya elemen-elemen besar menempati posisi yang tepat
dan lambatnya elemen-elemen yang lebih kecil dalam menempati posisi yang tepat.
Hal ini dapat ditunjukkan pada contoh data “9 2 4 1” yang akan diurutkan
berikut ini menggunakan algoritma Bubble Sort.
Pass Pertama
(9 2 4 1) menjadi (2 9 4 1)
(2 9 4 1) menjadi (2 4 9 1)
(2 4 9 1) menjadi (2 4 1 9)
Pass Kedua
(2 4 1 9) menjadi (2 4 1 9)
(2 4 1 9) menjadi (2 1 4 9)
(2 1 4 9) menjadi (2 1 4 9)
Pass Ketiga
(2 1 4 9) menjadi (1 2 4 9)
(1 2 4 9) menjadi (1 2 4 9)
(1 2 4 9) menjadi (1 2 4 9)
Pass Keempat
(1 2 4 9) menjadi (1 2 4 9)
(1 2 4 9) menjadi (1 2 4 9)
(1 2 4 9) menjadi (1 2 4 9)
Dari proses pengurutan di atas,
dapat dilihat bahwa elemen terbesar, “9”, langsung menempati posisi akhir pada
pass pertama. Akan tetapi elemen terkecil, “1”, baru menempati posisi pertama
pada pass keempat, yaitu pass yang terakhir. Oleh karena itu, muncullah istilah
“kura-kura” dan “kelinci” dalam algoritma Bubble Sort. Pada contoh di atas, “1”
berperan sebagai “kura-kura”, sedangkan “9” berperan sebagai “kelinci”.
Fenomena “kura-kura dan kelinci” ini sering kali mengakibatkan proses
pengurutan menjadi lama, terutama elemen “kura-kura”. Hal ini disebabkan oleh
“kura-kura” membutuhkan satu kali pass hanya untuk bergeser posisi ke sebelah
kiri.
2.3 Notasi Algoritmik dan Kompleksitas Waktu Bubble Sort
2.3.1
Notasi
Algoritmik Bubble
Sort
|
|
2.3.2
Kompleksitas Waktu Bubble Sort
Kompleksitas Algoritma Bubble Sort dapat dilihat dari beberapa jenis
kasus, yaitu worst-case, average-case, dan best-case.
Kondisi Best-Case
Dalam kasus ini, data yang akan
disorting telah terurut sebelumnya, sehingga proses perbandingan hanya
dilakukan sebanyak (n-1) kali, dengan satu kali pass. Proses perbandingan
dilakukan hanya untuk memverifikasi keurutan data. Contoh Best-Case dapat
dilihat pada pengurutan data “1 2 3 4” di bawah ini.
Pass Pertama
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Dari proses di atas, dapat dilihat bahwa tidak terjadi penukaran
posisi satu kalipun, sehingga tidak dilakukan pass selanjutnya. Perbandingan
elemen dilakukan sebanyak tiga kali. Proses perbandingan pada kondisi ini hanya
dilakukan sebanyak (n-1) kali. Persamaan Big-O yang diperoleh dari proses ini
adalah O(n).
Kondisi Worst-Case
Dalam kasus ini, data terkecil berada pada ujung array. Contoh
Worst-Case dapat dilihat pada pengurutan data “4 3 2 1” di bawah ini.
Pass Pertama
(4 3 2 1) menjadi (3 4 2 1)
(3 4 2 1) menjadi (3 2 4 1)
(3 2 4 1) menjadi (3 2 1 4)
Pass Kedua
(3 2 1 4) menjadi (2 3 1 4)
(2 3 1 4) menjadi (2 1 3 4)
(2 1 3 4) menjadi (2 1 3 4)
Pass Ketiga
(2 1 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Pass Keempat
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Dari langkah pengurutan di atas, terlihat bahwa setiap kali
melakukan satu pass, data terkecil akan bergeser ke arah awal sebanyak satu
step. Dengan kata lain, untuk menggeser data terkecil dari urutan keempat
menuju urutan pertama, dibutuhkan pass sebanyak tiga kali, ditambah satu kali
pass untuk memverifikasi. Sehingga jumlah proses pada kondisi best case dapat
dirumuskan sebagai berikut.
Jumlah proses = n2+n
Dalam persamaan di atas, n adalah jumlah elemen yang akan diurutkan.
Sehingga notasi Big-O yang didapat adalah O(n2). Dengan kata lain, pada kondisi
worst-case, algoritma Bubble Sort termasuk dalam kategori algoritma kuadratik.
Kondisi Average-Case
Pada kondisi average-case, jumlah pass ditentukan dari elemen mana
yang mengalami penggeseran ke kiri paling banyak. Hal ini dapat ditunjukkan
oleh proses pengurutan suatu array, misalkan saja (1 8 6 2). Dari (1 8 6 2),
dapat dilihat bahwa yang akan mengalami proses penggeseran paling banyak adalah
elemen 2, yaitu sebanyak dua kali.
Pass Pertama
(1 8 6 2) menjadi (1 8 6 2)
(1 8 6 2) menjadi (1 6 8 2)
(1 6 8 2) menjadi (1 6 2 8)
Pass Kedua
(1 6 2 8) menjadi (1 6 2 8)
(1 6 2 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
Pass Ketiga
(1 2 6 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
Dari proses pengurutan di atas, dapat dilihat bahwa untuk
mengurutkan diperlukan dua buah passing, ditambah satu buah passing untuk
memverifikasi. Dengan kata lain, jumlah proses perbandingan dapat dihitung
sebagai berikut.
Jumlah proses = x2+x
Dari persamaan di atas, dapat disimpulkan bahwa notasi big-O nya
adalah O(n2). Dengan kata lain, pada kondisi average case algoritma Bubble Sort
termasuk dalam algoritma kuadratik.
2.4 Kelebihan dan Kekurangan
Algoritma Bubble Sort
Setiap algoritma memiliki kelebihan
dan kekurangannya masing-masing, demikian pula denganalgoritma Bubble Sort.
Kelebihan dan kekurangan darialgoritma Bubble Sort dapat dilihat dari karakteristik
algoritma Bubble Sort itu sendiri. Berikut ini adalah beberapa kelebihan dan
kekurangan dari algoritma Bubble Sort.
Kelebihan Bubble Sort
Beberapa kelebihan dari algoritma
Bubble Sort adalah sebagai berikut :
F
Algoritma yang simpel.
F
Mudah untuk diubah menjadi
kode.
F
Definisi terurut terdapat
dengan jelas dalam algoritma.
F
Cocok untuk pengurutan data
dengan elemen kecil telah terurut.
Algoritma yang simpel. Hal ini dilihat
dari proses pengurutan yang hanya menggunakan rekurens dan perbandingan, tanpa
penggunaan proses lain. Algoritma pengurutan lain cenderung menggunakan proses
lain, misalnya proses partisi pada algoritma Quick Sort. Mudah untuk diubah menjadi kode. Hal ini diakibatkan oleh simpelnya
algoritma Bubble Sort, sehingga kecil kemungkinan terjadi kesalahan sintax
dalam pembuatan kode.
Definisi terurut terdapat dengan jelas dalam algoritma. Definisi terurut ini adalah tidak adanya satu kalipun swap pada satu
kali pass. Berbeda dengan algoritma lain yang seringkali tidak memiliki
definisi terurut yang jelas tertera pada algoritmanya, misalnya Quick Sort yang
hanya melakukan partisi hingga hanya ada dua buah nilai yang bisa dibandingkan.
Cocok untuk pengurutan data dengan elemen kecil telah terurut. Algoritma Bubble Sort memiliki kondisi best case dengan
kompleksitas algoritma O(n).
Kekurangan Bubble Sort
Beberapa kekurangan dari algoritma
Bubble Sort adalah sebagai berikut :
F
Tidak efektif dalam pengurutan
data berskala besar.
F
Langkah pengurutan yang terlalu
panjang.
Kekurangan terbesar dari Bubble Sort
adalah kompleksitas algoritma yang terlalu besar, baik dalam average case
maupun worst case, yaitu O(n2), sehingga seringkali disebut sebagai algoritma
primitif, brute-force, maupun algoritma naïf. Untuk 1000 buah data misalnya,
maka akan terjadi proses tidak lebih dari satu juta proses perbandingan.
Kompleksitas yang besar ini juga seringkali membuat algoritma Bubble Sort
sebagai “the general bad algorithm”. Bahkan, diantara algoritma pengurutan lain
yang memiliki kompleksitas algoritma O(n2), insertion sort cenderung lebih
efisien
2.5
Ide Dasar Counting Sort
Untuk dapat melakukan pengurutan
dengan counting sort rentang
nilai untuk kumpulan data yang akan diurutkan
harus diketahui, katakanlah k.
Ide dasar dari counting sort adalah menentukan, untuk setiap elemen x, jumlah
elemen yang lebih kecil daripada
x, yang kemudian informasi ini digunakan untuk menentukan posisi x. Contoh sederhana saja, jika terdapat 12 elemen yang
lebih kecil daripada x, maka
x akan mendapatkan posisinya di posisi 13.
Tentu saja, sedikit modifikasi harus
dilakukan agar metode ini
dapat menangani kasus di mana terdapat elemen-elemen lain yang nilainya sama dengan x. Di mana tentu saja kita tidak dapat
menempatkan semua elemen
yang nilainya sama dengan x di posisi yang sama.
2.6 Implementasi Counting Sort
Misal array data yang akan
diurutkan adalah A. Counting sort membutuhkan sebuah array C
berukuran k, yang setiap elemen C[i] merepresentasikan
jumlah elemen dalam A yang nilainya adalah i. Di array inilah
penghitungan (counting) yang dilakukan dalam pengurutan ini disimpan.
Misal kita akan melakukan pengurutan pada array A sebagai berikut,
dengan n adalah 10 dan diasumsikan bahwa rentang nilai setiap A[i]
adalah 1..5 :
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
Dan array C setelah diinisialisasi
adalah :
C
|
0
|
0
|
0
|
0
|
0
|
|
1
2 3 4
5
|
Kemudian proses penghitungan pun
dimulai, proses ini linier, dilakukan dengan menelusuri array A,
Langkah
1 : pembacaan pertama mendapat elemen A[1]
dengan isi 1, maka C[1] ditambah 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1
2 3 4
5 6 7 8
9 10
|
C
|
1
|
0
|
0
|
0
|
0
|
|
1
2 3 4
5
|
Langkah
2 : pembacaan kedua mendapat elemen A[2] dengan
isi 3, maka C[3] ditambah 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
C
|
1
|
0
|
1
|
0
|
0
|
|
1
2 3 4
5
|
Langkah
3 : pembacaan ketiga mendapat elemen A[3] dengan
isi 5, maka C[5] ditambah 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
C
|
1
|
0
|
1
|
0
|
1
|
|
1
2 3 4
5
|
Langkah
4 : pembacaan keempat mendapat elemen A[4]
dengan isi 4, maka C[4] ditambah 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
C
|
1
|
0
|
1
|
1
|
1
|
|
1
2 3 4
5
|
Demikian dilakukan terus menerus
hingga semua elemen A telah diakses. Hingga setelah langkah ke 10
didapatkan array C sebagai berikut :
C
|
1
|
2
|
3
|
1
|
3
|
|
1
2 3 4
5
|
Lalu array C diproses
sehingga setiap elemen C, C[i] tidak lagi
merepresentasikan jumlah elemen dengan nilai sama dengan i, namun setiap
C[i] menjadi merepresentasikan jumlah elemen yang lebih kecil
atau sama dengan i. Dan setelah proses tersebut dilakukan didapatkan C
sebagai berikut :
C
|
1
|
3
|
6
|
7
|
10
|
|
1
2 3 4
5
|
Setelah C didapat dilakukan
proses penempatan sesuai dengan posisi yang didapat. Proses ini dilakukan
dengan menelusuri kembali A dari belakang. Mengapa dari belakang? Karena
kita mengharapkan hasil pengurutan yang stable, yang akan sangat penting
dalam pengurutan data majemuk.
Dalam proses ini kita mengakses
elemen A[i], kemudian memposisikannya di posisi sebagaimana
tercatat dalam C[A[i]], kemudian kita mengurangkan C[A[i]]
dengan 1, yang dengan jelas untuk memberikan posisi untuk elemen berikutnya
dengan yang isinya sama dengan A[i].
Proses ini memerlukan sebuah array
bantu B yang ukurannya sama dengan array A, yaitu n. Yang
pada awalnya semua B[i] diinisialisasi dengan nil.
B
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
1
2 3 4
5 6 7
8 9 10
|
Langkah
1 : elemen A[10] adalah 5, maka karena C[5]
adalah 10, maka B[10] diisi dengan 5, dan C[5] dikurangi 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
B
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
C
|
1
|
3
|
6
|
7
|
9
|
|
1
2 3 4
5
|
Langkah
2 : elemen A[9] adalah 3, maka karena C[3]
adalah 6, maka B[6] diisi dengan 3, dan C[3] dikurangi 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
B
|
-
|
-
|
-
|
-
|
-
|
3
|
-
|
-
|
-
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
C
|
1
|
3
|
5
|
7
|
9
|
|
1
2 3 4
5
|
Langkah
3 : elemen A[8] adalah 3, maka karena C[3]
adalah 5, maka B[5] diisi dengan 3, dan C[3] dikurangi 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
B
|
-
|
-
|
-
|
-
|
3
|
3
|
-
|
-
|
-
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
C
|
1
|
3
|
4
|
7
|
9
|
|
1
2 3 4
5
|
Langkah
4 : elemen A[7] adalah 2, maka karena C[2]
adalah 3, maka B[3] diisi dengan 2, dan C[2] dikurangi 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
B
|
-
|
-
|
2
|
-
|
3
|
3
|
-
|
-
|
-
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
C
|
1
|
2
|
4
|
7
|
9
|
|
1
2 3 4
5
|
Demikian proses dilakukan hingga elemen A[1]
selesai diproses, sehingga didapatkan hasil akhir
B
|
1
|
2
|
2
|
3
|
3
|
3
|
4
|
5
|
5
|
5
|
|
1
2 3 4
5 6 7
8 9 10
|
Yang telah berupa array dengan
elemen-elemennya terurut secara non-decreasing.
2.7
Algoritma dan Kompleksitas Waktu Counting Sort
Dari implementasi yang telah
dilakukan tersebut, penulis mengimplementasikannya manjadi sebuah program
menggunakan bahasa Pascal sebagai berikut :
procedure CountingSort
(A : TArray; var B : TArray);
var
C : array [1..k] of
byte;
i : integer;
begin
for i:=1 to k do
C[i] := 0;
for i:=1 to n do
C[A[i]] := C[A[i]] + 1;
for i:=2 to k do
C[i] := C[i] + C[i-1];
for i:=n downto 1 do begin
B[C[A[i]]] := A[i];
C[A[i]] := C[A[i]] - 1;
end;
end;
Waktu yang dibutuhkan untuk mengurutkan
data menggunakan counting sort bisa didapatkan dari perhitungan sebagai
berikut : Kalang pertama membutuhkan waktu O(k), kalang kedu
membutuhkan waktu O(n), kalang ketiga membutuhkan waktu O(k),
dan kalang keempat membutuhkan waktu O(n).
Jadi secara total membutuhkan waktu O(k+n),
yang seringkali dianggap k = O(n), sehingga waktu total
yang dibutuhkan menjadi O(n).
BAB
III
PENUTUP.
3.1
Kesimpulan
Gagasan
dasar dari algoritma Bubble Sort adalah membandingkan sepasang elemen yang
berurutan di dalam larik dan mempertukarkan keduanya jika perlu. Nama bubble sort ini berasal dari sifat elemen terbesar yang selalu
naik ke atas seperti bubble. Beberapa kekurangan dari algoritma Bubble Sort
adalah tidak efektif dalam pengurutan data berskala besar.serta langkah
pengurutan yang terlalu panjang.
Counting Sort adalah algoritma pengurutan efektif dan efisien yang melakukan
pengurutan dengan ide dasar meletakkan elemen pada posisi yang benar, di mana
penghitungan posisi yang benar dilakukan dengan cara menghitung (counting)
elemen-elemen dengan nilai lebih kecil atau sama dengan elemen tersebut. Dan
memiliki kompleksitas waktu linier. Walaupun tidak dapat digunakan
secara luas karena banyaknya batasan.
3.2 Saran
Hendaknya dalam pemilihan algoritma pengurutan yang tepat perlu
memperhatikan kebutuhan memori, waktu eksekusi,implementasi
algoritma/penanganan kasus-kasus tertentu. Disamping itu, perlu diadakannya penelitian
yang lebih mendalam agar mendapatkan data yang valid sebagai referensi.
DAFTAR PUSTAKA
Rinaldi.2010. Buble Sort. Terdapat pada http://www.informatika.org/~rinaldi . Diakses tanggal 16 November 2012.11.16
-.2011. Buble. Terdapat pada http://www.cs.duke.edu/~ola/papers/bubble.pdf .
diakses pada tanggal 16 November 2012.
Rinaldi.2010. Counting Sort. Terdapat
pada http://www.informatika.org/~rinaldi . Diakses tanggal 16 November
2012.11.16
0 Response to "makalah buble sort dan counting sort"
Posting Komentar