Makalah Shell Sort

“SHELL SORT”

Makalah Ini dibuat Untuk Memenuhi Tugas Pada

Mata Kuliah Struktur Data

(Darpi Supriyanto, M. Kom)

Disusun oleh :

KELOMPOK 5 :

1.      M. LUBIS

2.      BIYAN BASELA

3.      SAHRUL MADRUP

UNIVERSITAS BANTEN JAYA

FAKULTAS ILMU KOMPUTER

TEKNIK INFORMATIKA

 TAHUN AKADEMIK 2014/2015

KATA PENGANTAR

Segala puji bagi Allah SWT yang telah melimpahkan rahmat dan hidayah-Nya, sehingga penulisan makalah yang berjudul “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 Struktur Data dan diharapkan dengan adanya makalah ini pembaca dapat menambah wawasan tentang 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.

Serang, 5-Oktober-2015

Penulis

 

Daftar isi

Kata pengantar................................................................................................................. i

Daftar isi............................................................................................................................. ii

Bab I

Pendahuluan.................................................................................................................... 1

1.1       latar belakang....................................................................................................... 1

1.2       rumusan masalah................................................................................................ 2

1.3       tujuan..................................................................................................................... 2

Bab II

Pembahasan..................................................................................................................... 3

2.1      pengertian sorting................................................................................................. 3

2.2      shell sort................................................................................................................. 3

Bab III

Penutup............................................................................................................................. 8

3.1.      Kesimpulan........................................................................................................... 8

3.2.      Saran..................................................................................................................... 8

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.

1.2              Rumusan Masalah

Dari latar belakang diatas adapun permasalahan penulis adalah sebagai berikut :

a)      Apa itu sorting?

b)      Apa fungsi dari Shell Sort?

1.3              Tujuan

Dari rumusan masalah diatas, adapun tujuan kami adalah sebagai berikut:

a)        Untuk mengetahui pengertian sorting?

b)        Memahami lebih dalam tentang Shell Sort?

BAB II

PEMBAHASAN

2.1       Pengertian Sorting
Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.
Contoh:
Data Acak    : 19 7 25 15 10 3 30 5
Ascending    : 3 5 7 10 15 19 25 30
Descending  : 30 25 19 15 10 7 5 3

2.2       Shell Sort

Shell sort merupakan Metode Pertambahan Menurun yang dikembangkan oleh Donald L. Shell
(1959).Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu sehingga
dibentuk sub-list, kemudian dilakukan pertukaran jika diperlukan.
Jarak yang digunakan disebut increment value, atau sequence number k
 Misal sekuens: 5,3,1
 Pengambilan sekuens bebas, asal menurun
• Jika k=5, maka sublistnya:
  • Data[0], Data[5], Data[10], …
  • Data[1], Data[6], Data[11], …
  • Data[2], Data[7], Data[12], …
• Jika k=3, maka sublistnya:
  • Data[0], Data[3], Data[6], …
  • Data[1], Data[4], Data[7], …
  • Data[2], Data[5], Data[8], …

Pemilihan Sequence number
1. Disarankan jarak mula-mula dari data yang akan dibandingkan adalah (N/2)+1)
2. Pada proses berikutnya, digunakan jarak (N/4)+1)
3. Pada proses berikutnya, digunakan jarak (N/8)+1)
4. Demikian seterusnya sampai jarak yang digunakan adalah 1

Proses Pengurutannya
1. Untuk jarak (N/2)+1:
    - Data pertama (i=0) dibandingkan dengan data dengan jarak (N/2)+1. Apabila data pertama lebih besar    dari data ke (N/2)+1) tersebut maka kedua data tersebut ditukar.
    - Kemudian data kedua (i=1) dibandingkan dengan jarak yang sama yaitu (N/2)+1) = elemen ke-(i+N/2)+1
    - Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-i selalu lebih kecil dari pada data ke-(i+N/2)+1
2. Ulangi langakah-langkah diatas untuk jarak = (N/4)+1 kemudian lakukan pembandingan dan pengurutan sehingga semua data ke-i lebih kecil daripada data ke-(i+N/4)+1
3. Ulangi langakah-langkah diatas untuk jarak = (N/8)+1 kemudian lakukan pembandingan dan pengurutan sehingga semua data ke-i lebih kecil daripada data ke-(i+N/8)+1
4.  Demikian seterusnya sampai jarak yang digunakan adalah 1 atau data sudah terurut

Contoh Data:

Data:  19 7 25 15 10 3 30 5

Index: 0 1 2 3 4 5 6 7

Size: 8

Proses pertama, jarak=(N/2)+1=(8/2)+1=5    

 

Step I: Buat Sublist K=5

S[0]  S[5]

S[1]  S[6]

S[2]  S[7]

Step 2-3 Urutkan Sublist dan Gabungkan

S[0] > S[5]             19  3  Not OK

SORT Them  3  19

S[1] < S[6]             7  30  OK

S[2] > S[7]             25  5  Not Ok

SORT Them  5  25

Proses kedua, jarak=(N/4)+1=(8/4)+1=3

Step I: Buat Sublist K=3

S[0]  S[3]  S[6]

S[1]  S[4]  S[7]

S[2]  S[5]

Step 2-3 Urutkan Sublist dan gabungkan

S[0]  S[3]  S[6]     19  15  30  Not Ok

SORT Them  15  19  30

S[1]  S[4]  S[7]      7   10  5  Not OK

SORT Them  5  7  10

S[2]  S[5]               25  3  Not OK

SORT Them    3  25

  

Proses ketiga, jarak=(N/8)=1

 

Step I: Buat Sublist K=I

Step 2-3 Urutkan Sublist dan Gabungkan

 

Input

 Output

 

BAB III

PENUTUP

3.1.      Kesimpulan

            Dari kesimpulan diatas, dapat kita simpulkan bahwa didalam pengurutan data dalam struktur data dapat kita gunakan beberapa macam model dan terdapat langkah-langkah yang berbedaada yang melalui cara singkatdan ada juga yang melalui cara lengkap atau cara panjang. Pengurutan data yang dilakukan dapat berupa pengurutan yang terkecil ke pengurutan yang terbesar  yakni ascending. Atau pengurutan terbesar ke pengurutan terkecil yang disebut discending.

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.