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.
algoritma 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 permasalahan kami adalah sebagai berikut :
1.2.1. Apa
pengertian algoritma sorting?
1.2.2. Apa saja
bagian-bagian algoritma sorting?
1.2.3. Apa fungsi
dari bagian-bagian algoritma sorting tersebut ?
1.3. Tujuan
Dari
rumusan masalah diatas, adapun tujuan kami adalah sebagai berikut:
1.3.1. Untuk
mengetahui pengertian algoritma sorting?
1.3.2. Untuk
mengetahui bagian-bagian algoritma sorting?
1.3.3. Untuk
mengetahui fungsi dari bagian-bagian algoritma sorting tersebut ?
BAB II
ISI
A. Pengertian
Sorting
Pengurutan data dalam struktur data sangat penting
terutama untuk data yang beripe data numerik ataupun karakter. Pengurutan dapat
dilakukan secara ascending (urut naik) dan descending (urut turun). Pengurutan
(Sorting) adalah proses pengurutan data yang sebelumnya disusun secara acak
sehingga tersusun secara teratur menurut aturan tertentu.
Contoh:
Data Acak :
5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25
Descending : 25 10 8 6 5 3 1
B.
Deklarasi Array Sorting
Mendeklarasikan array secara global:
int data[100];
int n; //untuk jumlah data
Fungsi Tukar 2 Buah Data:
void tukar(int a,int b)
{
int tmp;
tmp = data[a];
data[a] = data[b];
data[b] = tmp;
}
Sorting merupakan suatu proses untuk menyusun kembali
himpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu
algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu
berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.
Pada dasarnya ada dua macam urutan yang biasa
digunakan dalam suatu proses sorting:
1. Urut naik (ascending) Mengurutkan dari data
yang mempunyai nilai paling kecil sampai paling besar.
2. Urut turun (descending) Mengurutkan dari data yang
mempunyai nilai paling besar sampai paling kecil.
Mengapa harus melakukan sorting data?
Ada banyak alasan
dan keuntungan dengan mengurutkan data. Data yang terurut mudah untuk dicari,
mudah untuk diperiksa, dan mudah untuk dibetulkan jika terdapat kesalahan. Data
yang terurut dengan baik juga mudah untuk dihapus jika sewaktu-waktu data
tersebut tidak diperlukan lagi. Selain itu, dengan mengurutkan data maka kita
semakin mudah untuk menyisipkan data atapun melakukan penggabungan
data.
C. Macam-Macam
Sorting
1. Bubble Sort
Memindahkan element sekarangdenganelemenberikutnya ,jikaelemensekarangitulebihbesar / lebihkecildarielemenberikutnyamaka di tukar (berpindahposisi).
1. Bubble Sort
Memindahkan element sekarangdenganelemenberikutnya ,jikaelemensekarangitulebihbesar / lebihkecildarielemenberikutnyamaka di tukar (berpindahposisi).
Ascending
- Data yang paling awaldibandingkandengan data berikutnyajikaternyatalebihbesarmakatukar.
- Data yang paling akhirdibandingkandengan data sebelumyajikaternyatalebihkecilmakatukar.
Descending
- Data yang paling awaldibandingkandengan data berikutnyajikaternyatalebihkecilmakatukar.
- Data yang paling akhirdibandingkandengan data sebelumyajikaternyatalebihbesarmakatukar.
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. Selection Sort
Memindahkanelemendengancaramembandingkanelemensekarangdenganelemen yang berikutnyasampaidenganelemen terakhir.Jikaditemukanelemen lain yang lebih kecil / lebihbesardarielemensekarangmakadicatatposisinyadankemudianditukardanbegituseterusnya.
1. Ascending
Memindahkanelemendengancaramembandingkanelemensekarangdenganelemen yang berikutnyasampaidenganelemen terakhir.Jikaditemukanelemen lain yang lebih kecil / lebihbesardarielemensekarangmakadicatatposisinyadankemudianditukardanbegituseterusnya.
1. Ascending
- Elemen yang paling besardiletakkan di akhir.
- Elemen yang paling kecildiletakkan di awal.
2. Descending
- Elemen yang paling kecildiletakkan di akhir.
- Elemen yang paling besardiletakkan di awal.
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
 |
|
Contoh Selection Sort
Ascending (UrutanNaik) |
3. Insertion Sort
Pengurutan yang dilakukandengancaramembandingkandengan data ke-2 sampai data terakhir. Jikaditemukan data yang lebihkecilataulebihbesarmaka data tersebutdisisipkankedepansesuaiposisi yang seharusnya.
Pengurutan yang dilakukandengancaramembandingkandengan data ke-2 sampai data terakhir. Jikaditemukan data yang lebihkecilataulebihbesarmaka data tersebutdisisipkankedepansesuaiposisi yang seharusnya.
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;
 |
|
Contoh Insertion Sort
Ascending (UrutanNaik) |
4. Shell Sort
Merupakan proses pengurutan data yang sebelumnyaacakmenjadi data yang terurutdengancaramenentukanjarakantarelemen yang akandibandingkan.
 |
|
Contoh Shell Sort
Ascending (UrutanNaik) |
5. Merge Sort
Merupakan proses pengurutan data yang menggunakan merging duabuah vector. Pada proses merge sort, data dibuatsepasang-sepasang, yang terdiridariduaelemen. Jika N ganjil, makaadasatu vector yang terdiridari 1 elemen. Lalukemudian data tersebut di merging sampaiterurut.
Merupakan proses pengurutan data yang menggunakan merging duabuah vector. Pada proses merge sort, data dibuatsepasang-sepasang, yang terdiridariduaelemen. Jika N ganjil, makaadasatu vector yang terdiridari 1 elemen. Lalukemudian data tersebut di merging sampaiterurut.
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
 |
|
Contoh Merge Sort
Ascending (UrutanNaik) |
6. Quick Sort
Merupakan proses penyusunanelemen yang membandingkansuatuelemen (pivot) denanelemen yang lain, danmenyusunnyasedemikianrupasehinggaelemen –elemen lain yang lebihkecildari pivot terletakdisebelahkiri pivot. Dan elemen yang lebihbesardari pivot terletakdisebelahkanan pivot.
Dengandemikianakanterbentukduasublist, yang terletakdisebelahkanandankiri pivot. Lalupadasublistkiridankananitukitaanggapsebuah list baru, dankitakerjakan proses yang samaseperti yang sebelumnya. Demikianseterusnyasampaitidakterdapatsublistlagi.
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 IV
KESIMPULAN
Penggunaan algoritma
pengurutan dalam ilmu komputer memang sangat diperlukan sebab kita tidak bisa
membuat algoritma dengan prinsip “yang penting jalan”. Bila ingin mengurutkan
data yang sedikit jumlahnya maka sebaiknya menggunakan insertion sort.
Namun bila ingin mengurutkan data yang sangat banyak, merge sortdan quick
sort akan menjadi pilihan yang baik. Bubble sort sendiri
hanya sebuah algoritma sederhana yang sebaiknya tidak diimplementasikan lagi.
Masih banyak algoritma pengurutan yang lain, dengan segala kelebihan dan
kekurangannya. Karena itu pemilihan kompleksitas waktu dan ruang sangat penting
di sini. Makalah ini tidak membahas semua algoritma pengurutan, karena untuk
membahas satu algoritma secara mendalam pun akan sangat rumit dan mungkin
menghabiskan satu makalah ini. Namun melalui tulisan ini, pembaca diharapkan
mampu menganalisa penggunaansorting algorithmic yang baik.
Daftar
Pustaka
