BAB I
PENDAHULUAN
1.1.
Latar
Belakang
Dalam matematika dan
komputasi, algoritma merupakan kumpulan perintah untuk menyelesaikan
suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari
awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk
setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum
menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi
awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering
mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika
Boolean dan perbandingan) sampai tugasnya selesai.
Desain dan analisis algoritma
adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik
dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari
implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari
secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang
digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan
kriteria yang sama.
Kompleksitas dari
suatu algoritma merupakan ukuran seberapa banyak komputasi yang
dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal,
algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat
memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu
lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.
Sedangkan sorting adalah
sebuah proses merangkai benda dalam urutan tertentu dan/atau dalam himpunan
yang berbeda, dan oleh karena itu dia memiliki dua arti umum yang berbeda:
1. Pengurutan:
merangkai benda yang sejenis, sekelas, dll, dalam urutan yang teratur.
2. Kategorisasi: pengelompokan dan pemberian
label kepada benda dengan sifat yang serupa.
sorting terdiri dari
beberapa algoritma seperti Bubble sort, Quick sort, Selection Sort,
Insertion Sort, dan Merge Sort yang dimana setiap
jenis sorting ini memiliki perbedaan satu sama lainnya.
1.2. Rumusan
Masalah
Dari latar belakang diatas
adapun permasalahannya adalah sebagai berikut :
1.2.1. Apa pengertian sorting?
1.2.2. Apa saja bagian-bagian sorting?
1.2.3. Apa fungsi dari
bagian-bagian sorting tersebut ?
1.3. Tujuan
Dari rumusan masalah diatas,
adapun tujuan nya adalah sebagai berikut:
1.3.1. Untuk mengetahui pengertian sorting
1.3.2. Untuk
mengetahui bagian-bagian sorting
1.3.3. Untuk
mengetahui fungsi dari bagian-bagian sorting tersebut
BAB II
PEMBAHASAN
Sorting didefinisikan sebagai pengurutan sejumlah data
berdasarkan nilai kunci tertentu. Pengurutan dapat dilakukan dari nilai
terkecil ke nilai terbesar (ascending) atau sebaliknya (descending). Sorting
termasuk salah satu contoh yangkaya akan solusi. Dalam makalah ini, hanya akan
dibahas lima algoritma sorting yang populer dipakai didunia informatika.
2.1. Bubble Sort
Bubble Sort merupakan cara
pengurutan yang sederhana. Konsep dari ide dasarnya adalah seperti “gelembung
air” untuk elemen struktur data yang semestinya berada pada posisi awal. Cara
kerjanya adalah dengan berulang-ulang melakukan traversal (proses looping)
terhadap elemen-elemen struktur datayang belum diurutkan. Di dalam traversal
tersebut, nilai dari dua elemen struktur data dibandingkan. Jika ternyata
urutannya tidak sesuai dengan “pesanan”, maka dilakukan pertukaran (swap).
Algoritma sortingini disebut juga dengan comparison sort dikarenakanhanya
mengandalkan perbandingan nilai elemen untuk mengoperasikan elemennya.
Algoritma bubble sort dapat diringkas
sebagai berikut, jika N adalah panjang elemen struktur data, dengan
elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:
1. Lakukan
traversal untuk membandingkan dua elemen berdekatan. Traversal ini dilakukan
dari belakang.
2. Jika
elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak,
lanjutkan ke proses traversal berikutnya sampai bertemu dengan bagian struktur
data yang telah diurutkan.
3. Ulangi
langkah di atas untuk struktur data yang tersisa.
Pseudocode dari bubble Sort adalah sebagai berikut;
For I = 0 to N - 2
For J = 0 to N - 2
If (A(J) > A(J + 1)
Temp = A(J)
A(J) = A(J + 1)
A(J + 1) = Temp
End-If
End-For
End-For
2.2. Selection Sort
Selection Sort adalah sort
yang melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur
data. Untuk sorting ascending (menaik), elemen yang paling kecil di antara
elemen-elemen yang belum urut, disimpan indeksnya, kemudian dilakukan
pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang
paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun),
elemen yang paling besar yang disimpan indeksnya kemudian ditukar.
Algoritma selection sort dapat
dirangkum sebagai berikut:
1. Temukan
nilai yang paling minimum (atau sesuai keinginan) di dalam struktur data. Jika
ascending, maka yang harus ditemukan adalah nilai yang paling minimum. Jika
descending, maka temukan nilai yang paling maksimum.
2.
Tukar nilai tersebut dengan nilai pada posisipertama di bagian struktur data
yang belum diurutkan.
3. Ulangi langkah di atas untuk bagian struktur
datayang tersisa.
Pseudocode dari selection Sort adalah sebagai berikut;
For I = 0 to N-1 do:
Smallsub = I
For J = I + 1 to N-1 do:
If A(J) < A(Smallsub)
Smallsub = J
End-If
End-For
Temp = A(I)
A(I) = A(Smallsub)
A(Smallsub) = Temp
End-For
2.3. Insertion
Sort
Metode pengurutan pada insertion sort adalah metode dengan cara menyisipkan elemen larik pada
posisi yang tepat.Cara kerja insertion sort, Pertama-tama, dilakukan
iterasi, dimana di setiap iterasi insertion sort memindahkan nilai
elemen,kemudian menyisipkannya berulang-ulang sampai ketempat yang tepat.
Begitu seterusnya dilakukan. Dari proses iterasi, seperti biasa,
terbentuklah bagian yang telah di-sorting dan bagian yang belum di-sorting.
Algoritma Insertion Sort dapat
dirangkum sebagai berikut:
1. Simpan nilai Ti kedalam variabel sementara,
dengan i = 1.
2. Bandingkan
nilainya dengan elemen sebelumnya.
3. Jika elemen
sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan
nilai Ti-1 tersebut. Decrement i (kurangi nilainya dengan 1).
4. Lakukan terus
poin ke-tiga, sampai Ti-1 ≤ Ti.
5. Jika Ti-1 ≤ Ti
terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan
sebelumnya.
6. Ulangi langkah dari
poin 1 di atas dengan i di-increment (ditambah satu).
Pseudocode dari Insertion Sort adalah sebagai berikut;
procedure insertion;
var i,j,v: integer;
begin
for i:=2 to N do
begin
v:=a[i];j:=1;
while a[j1] > v do
begin a[j]:=a[j1]; j:=j1 end;
a[j]:=v;
end
end;
2.4. Merge Sort
Algoritma Merge
Sort ditemukan oleh John vonNeumann di tahun 1945. Merge Sort termasuk
paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi).
Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum
kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide
utama sebagai berikut,
1. Sebuah list yang kecil membutuhkan langkah
yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
2. Untuk membentuk sebuah list terurut dari
duabuah list terurut membutuhkan langkah yangl ebih sedikit daripada membentuk
sebuah list terurut dari dua buah list tak terurut. Contoh:hanya diperlukan
satu kali traversal untuk masing-masing list jika keduanya sudahterurut.
Algoritma Merge Sort
sederhananya, dapat ditulis berikut:
1. Bagi
list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang
satu elemen.
2. Bagi
masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan
ukuran 1.
3. Gabung
2 sublist kembali menjadi satu list terurut.
Berikut
ini adalah tiga proses di dalam menggunakan algoritma Merge Sort :
Divide :
Bagi array A[l..r] dengan jumlah elemen n menjadi dua subarray
dengan jumlah elemen masingmasing subarray sebanyak n/2.
Conqueror :
Urutkan masing-masing subarray secara rekursif menggunakan prosedur merge
sort
Combine :
Satukan subarray untuk menghasilkan elemen array A[l..r] yang
terurut.
Berikut ini adalah algoritma untuk Merge Sort array A[l..r]:
Merge-Sort (A,l,r)
1. if l < r
2.
then q := [(l+r) /2]
3.
Merge-Sort(A,l,q)
4.
Merge-Sort(A,q+1,r)
5.
Merge(A,p,q,r)
Sedangkan algoritma untuk prosedure Merge adalah sebagai berikut :
MERGE ( A, l, q, r)
1. n1 ← q − l + 1
2. n2 ← r − q
3. create arrays L[1 . .
n 1 + 1] and R[1 . . n 2 + 1]
4. for i ← 1 to n 1
5.
do L[i] ← A[ l + i − 1]
6. for j ← 1 to n 2
7.
do R[ j ] ← A[q + j ]
8. L[n 1 + 1] ← ∞
9. R[n 2 + 1] ← ∞
10. i ← 1
11. j ← 1
12. for k ← l to r
13.
do if L[i] ≤ R[ j ]
14.
then A[k] ← L[i]
15.
i ←i +1
16.
else A[k] ← R[ j ]
17.
j ← j +1
2.5. Quick Sort
Quick Sort adalah
algoritma sorting yang terkenal yang dirancang oleh C.A.R. Hoare pada tahun
1960 ketika bekerja untuk perusahaan manufaktur komputer saintifik kecil,
Elliott Brothers. Algoritma ini rekursif, dan termasuk paradigma
algoritma divide and conquer.
Algoritma ini terdiri dari 4
langkah utama:
1. Jika struktur data terdiri dari 1 atau 0
elemen yang harus diurutkan, kembalikan struktur data itu apa adanya.
2. Ambil
sebuah elemen yang akan digunakansebagai pivot point (poin poros).
(Biasanya elemen yang paling kiri.)
3. Bagi
struktur data menjadi dua bagian – satu dengan elemen-elemen yang lebih besar
daripada pivot point, dan yang lainnya dengan elemen-elemen yang lebih kecil
dari pada pivot point.
4. Ulangi
algoritma secara rekursif terhadap kedua paruh struktur data.
Berikut adalah tiga proses di dalam metode divide dan conqueror
untukalgoritma Quick Sort:
Divide : Bagi
array A[l..r] menjadi dua subarray A[l..pivot-1] dan A[pivot+1..r]
sehingga setiap elemen di dalam sub array A[l..pivot1] bernilai
lebih kecil atau sama dengan A[pivot]. Untuk menghitung
nilai pivot merupakan bagian dari prosedur partition.
Conqueror : Urutkan subarray A[l..pivot1] dan
A[pivot+1..r] secara rekursif ke prosedur quicksort
Combine : Karena subarray sudah terurut, maka array A[l..r] sudah terurut.
Pseudocode dari algoritma quick sort adalah sebagai berikut:
procedure quicksort(l,r:integer);
var pivot: integer;
begin
for r > l then
begin
pivot:=partition(l,r);
quicksort(l,pivot1);
quicksort(pivot+1,r);
end
end;
Algoritma dari partisi array A[l..r] adalah :
x := A[r]
i := l-1
for j := l to r-1
do if A[j] <= x
then i := i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i+1
BAB III
PENUTUP
3.1. Kesimpulan
Algoritma yang mudah dalam hal
implementasi adalah Bubble Sort, Selection Sort, dan Insertion Sort. Ketiganya
memiliki kompleksitas O(n2). Di antara algoritma ini, yang paling effisien
adalah Insertion Sort. Algoritma yang lebih mangkus adalah MergeSort dan
Quick Sort dengan kompleksitasnya adalah O(n log n). Adapun yang paling mangkus
dari lima algoritma ini adalah Quick Sort.
3.2. Saran
Dengan disusunya makalah ini,
semoga makalah ini bisa menjadi inspirasi dalam kehidupan sehari-hari, secara
tidak sengaja sering kita malakukan prosedur semacam ini di kehidupan
sehari-hari seperti melakukan langkah mencuci baju, menjalankan sepeda
motor.itu semua adalah algoritma yang dilakukan dalam kehidupan sehari-hari. Begitu
juga dalam computer atau didalam bahasa pemrograman. Jika langkah-langkah dalam
kehidupan sehari-hari kita amati, hampir tidak jauh beda dengan langkah-langkah
pemrograman.
DAFTAR PUSTAKA
http://en.wikipedia.org/wiki/Sorting_algorithm
lecturer.eepisits.edu/~entin/Struktur%20Data/Minggu%2011/Minggu%2011%20Quick.pdf
http://www.informatika.org/~rinaldi/Stmik/2006/Makalah2006/MakalahStmik2006-27.pdf
http://lecturer.ukdw.ac.id/anton/strukdat.php
http://blog.binadarma.ac.id/andri/?p=65#
http://acieee.wordpress.com/2010/03/10/algoritma-sorting/
http://id.wikipedia.org/wiki/Algoritma_sorting
