KATA PENGANTAR
“Assalamu’alaikum Wr. Wb.”
Segala puji bagi Allah SWT yang telah melimpahkan rahmat dan hidayah-Nya,
sehingga penulisan makalah yang berjudul “METODE PENGURUTAN SHELL SORT” ini
dapat diselesaikan. Penulis mengucapkan terima kasih kepada seluruh pihak-pihak
yang telah membantu dalam pembuatan makalah ini baik secara langsung maupun
tidak langsung.
Penulisan makalah ini dalam rangka untuk memenuhi tugas Sistem Berkas dan
diharapkan dengan adanya makalah ini pembaca dapat menambah wawasan tentang Metode Pengurutan Shell
Sort.
Penulis menyadari dalam penulisan makalah ini masih kurang sempurna. Oleh
karena itu, segala kritik yang bersifat membangun akan penulis terima dengan
tangan terbuka.
“Wassalamua’alaikum
Wr. Wb.”
Gresik, 04-Januari-2014
Penulis
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:
a)
pengurutan:
merangkai benda yang sejenis, sekelas, dll, dalam urutan yang teratur.
b)
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 penulis
adalah sebagai berikut :
a)
Apa
pengertian algoritma sorting?
b)
Apa saja
bagian-bagian algoritma sorting?
c)
Apa
fungsi dari bagian-bagian algoritma sorting tersebut ?
1.3
Tujuan
Dari rumusan masalah diatas, adapun tujuan kami adalah
sebagai berikut:
a)
Untuk
mengetahui pengertian algoritma sorting?
b)
Untuk
mengetahui bagian-bagian algoritma sorting?
c)
Memahami lebih dalam tentang Shell Sort?
BAB II
PEMBAHASAN
2.1 Pengertian Sorting
Sorting
didefinisikan sebagai pengurutan sejumlahdata berdasarkan nilai kunci tertentu.
Pengurutan dapat dilakukan dari nilai terkecil ke nilai terbesar (ascending)
atau sebaliknya (descending).Algoritma Sorting termasuk salah satu contoh
yangkaya akan solusi. Dalam makalah ini, hanya akan dibahas lima algoritma
sorting yang populer dipakai didunia informatika.
2.2 Sorting
a.
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.
b.
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
c.
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.
d.
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.
e. 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.
f.
Heap Sort
Heapsort adalah metode mengurutkan dengan memanfaatkan
sifat yang dimiliki oleh struktur data heap. Heap sendiri adalah sebuah “binary
search tree” dengan sifat parent memiliki nilai >= nilai yang ada di
anaknya. Meski dikatakan ia adalah sebuah binary search tree, namun heap lebih
diarahkan ke konsepsi / menganggap suatu array memiliki sifat heap.
g. Shell Sort
Metode ini
disebut juga dengan metode pertambahan menurun (diminishing increment
short). Metode ini dikembangkan oleh Donald L.shell pada tahun
1959,sehingga sering disebut dengan metode shell short.
Metode ini mengrutkan data dengan cara membandingkan suatu data lain yang memiliki jarak tentu sehingga membentuk sebuah sub-list-, kemudian dilakukan penukaran apabila diperlukan.
Jarak yang dipakai didasarkan pada increment value atau sequence number K.Misalnya sequence number yang dipakai adalah 5,3,1. tidak ada pembuktianya disini bahwa bilangan tersebut adalah sequence number terbaik.
Setiap sup-list berisi setiap element ke-K dari kumpulan element yang asli.
Metode ini mengrutkan data dengan cara membandingkan suatu data lain yang memiliki jarak tentu sehingga membentuk sebuah sub-list-, kemudian dilakukan penukaran apabila diperlukan.
Jarak yang dipakai didasarkan pada increment value atau sequence number K.Misalnya sequence number yang dipakai adalah 5,3,1. tidak ada pembuktianya disini bahwa bilangan tersebut adalah sequence number terbaik.
Setiap sup-list berisi setiap element ke-K dari kumpulan element yang asli.
Sebagai contoh :
Jika K=5 maka sub-list adalah sebagai berikut :
- s[0] s[5] s[10]…
- s[1] s[6] s[11]…
- s[2] s[7] s[12]…
- dst
o Begitu juga K=3 maka sub-listnya adalah :
- s[0] s[3] s[6]…
- s[1] s[4] s[7]…
- dst
Proses shell short
- urutkan sekumpulan element dibawah ini, misalnya diberikan sequence number : 5,3,1
Jika K=5 maka sub-list adalah sebagai berikut :
- s[0] s[5] s[10]…
- s[1] s[6] s[11]…
- s[2] s[7] s[12]…
- dst
o Begitu juga K=3 maka sub-listnya adalah :
- s[0] s[3] s[6]…
- s[1] s[4] s[7]…
- dst
Proses shell short
- urutkan sekumpulan element dibawah ini, misalnya diberikan sequence number : 5,3,1
Contoh lain dari proses Sorting dengan menggunakan metode
Shell Sort :
Dalam Procedure Pascal :
Procedure Shell(Var Temp : Data; JmlData :
Integer);
Var I,J, Jarak : Integer;
Begin
Jarak :=
JmlData Div 2;
While
Jarak > 0 Do
Begin
For I:=1 To JmlData-Jarak Do
Begin
J := I +
Jarak;
If Temp[I] >
Temp[J] Then
SWAP(Temp[I],
Temp[Lok]);
End;
Jarak := Jarak Div 2;
End;
End;
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 bias menjadi infirasi 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.
0 komentar:
Posting Komentar