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.

 

Pengertian, Sejarah, Jenis, Fungsi dan Cara Kerja Router

Asalamualaikum wr.wb

Pengertian Router

Router adalah sebuah alat yang mengirimkan paket data melalui sebuah jaringan atau Internet menuju tujuannya, melalui sebuah proses yang dikenal sebagai routing. Proses routing terjadi pada lapisan 3 (Lapisan jaringan seperti Internet Protocol) dari stack protokol tujuh lapis OSI.

Router memiliki fasilitas DHCP (Dynamic Host Configuration Procotol), dengan mensetting DHCP, maka kita dapat membagi IP Address, fasilitas lain dari Router adalah adanya NAT (Network Address Translator) yang dapat memungkinkan suatu IP Address atau koneksi internet disharing ke IP Address lain.

Router dapat digunakan untuk menghubungkan banyak jaringan kecil ke sebuah jaringan yang lebih besar, yang disebut dengan internetwork, atau untuk membagi sebuah jaringan besar ke dalam beberapa subnetwork  untuk meningkatkan kinerja dan juga mempermudah manajemennya. Router juga kadang digunakan untuk mengoneksikan dua buah jaringan yang menggunakan media yang berbeda (seperti halnya router wireless yang pada umumnya selain ia dapat menghubungkan komputer dengan menggunakan radio, ia juga mendukung penghubungan komputer dengan kabel UTP), atau berbeda arsitektur jaringan, seperti halnya dari Ethernet ke Token Ring.

Sejarah Router

Pada awal 1980-an, ada sepasang suami istri yaitu Len dan Sandy Bosack yang dulu bekerja di dua departemen komputer yang berbeda yang terletak di Stanford University. Pasangan ini sedang menghadapi masalah dalam membuat komputer mereka berkomunikasi satu sama lain.
Untuk mengatasi masalah ini, mereka membuat sebuah server gateway di ruang tamu mereka yang menuju cara sederhana membuat dua departemen berkomunikasi satu sama lain dengan bantuan protokol IP. Mereka mendirikan cisco Systems (dengan c kecil) pada tahun 1984, memiliki server gateway komersial kecil yang membawa sebuah revolusi dalam Networking. Nama perusahaan diubah menjadi Cisco Systems, Inc pada tahun 1992. Advanced Gateway Server (AGS) adalah produk pertama yang dipasarkan perusahaan. Setelah ini datang Mid-Range Gateway Server (MGS), Compact Gateway Server (cgs), Integrated Gateway Server (IGS) dan AGS +.

Akhirnya menciptakan router cisco 4000, 7000, 2000, dan 3000 series. Router ini masih ada dan meningkatkan setiap hari. Cisco adalah pemimpin besar dunia ketika datang ke jaringan untuk Internet. Produk perusahaan ini mengarah pada kemudahan dalam mengakses dan mentransfer informasi terlepas dari perbedaan waktu, tempat atau platform. Sertifikasi CCNA adalah sertifikat yang pertama dalam jajaran sertifikasi Cisco dan merupakan pendahulu untuk semua sertifikasi Cisco. Program CCNA dibuat untuk memberikan dasar yang kokoh yang tidak hanya untuk Cisco Internetwork Operating System (IOS) dan hardware Cisco, tetapi juga internetworking secara umum. Untuk mendapatkan Cisco Certified Internetwork Expert (CCIE) maka Ciscon membuat suatu seri sertifikasi, yaitu:

– CCNA (Cisco Certified Network Associate)
– CCNP (Cisco Certified Network Professional)

– CCIE (Cisco Certified Internetwork Expert)

Jenis – Jenis Router

Ada banyak jenis-jenis router yang dibedakan menurut fungsi dan kegunaannya. Secara umum, router dibagi menjadi dua jenis, yaitu router statis, dan router dinamis. Selain kedua jenis router itu, ada lagi pembagian router berdasarkan bentuknya yaitu router aplikasi, router hardware, dan router komputer.

1. Router statis

Router statis atau static router adalah router yang memiliki kabel routing statis yang settingannya diatur oleh administrasi jaringan secara manual.

2. Router dinamis

Sedangkan router dinamis atau dynamic router adalah router yang memiliki dan membuat tabel routing yang lebih dinamis, dengan cara mendengarkan lalu lintas jaringan router lainnya atau dengan cara berhubungan dengan router lainnya.

Selain kedua jenis router di atas, router juga dapat dibedakan menjadi tiga jenis, yaitu router aplikasi, router hardware, dan router komputer.

1. Router aplikasi

Router ini tidak memiliki bentuk fisik seperti router pada umumnya, namun berupa aplikasi yang bisa Anda install pada sistem operasi komputer. Aplikasi ini kemudian bisa menjadikan komputer yang diinstal bisa berfungsi layaknya sebuah router. Aplikasi router yang bisa Anda gunakan antara lain adalah WinGate, WinProxy, Winroute, Spygate, dan aplikasi lainnya.

2. Router hardware

Router ini adalah perangkat keras yang bentuknya seperti yang sudah familiar di masyarakat yang berfungsi untuk membagi IP address dan dapat digunakan untuk membagi koneksi internet di dalam suatu wilayah jangkauan yang biasanya disebut dengan hotspot area.

3. Router PC

Router ini adalah menyulap sebuah komputer untuk bisa berfungsi sebagai router, tetapi berbeda dengan router aplikasi yang menggunakan aplikasi untuk mengubah komputer menjadi router. Untuk menjadikan sebuah komputer sebagai router tidak dibutuhkan komputer dengan spesifikasi tinggi. Hanya dengan komputer dengan prosesor Pentium 2, hard drive 10 GB, ram 64, dan telah tersedia LAN card sudah bisa mengubah komputer menjadi router untuk membagi jaringan. Agar bisa berfungsi, komputer yang ingin dijadikan router harus diinstal dengan sistem operasi yang khusus untuk router. Saat ini sistem operasi atau OS yang populer digunakan untuk router adalah Mikrotik.

Fungsi – Fungsi Router

1. Fungsi utama router yaitu menghubungkan beberapa jaringan untuk menyampaikan data dari suatu jaringan ke jaringan yang lain. Namun router berbeda dengan Switch, karena Switch hanya digunakan untuk menghubungkan beberapa komputer dan membentuk LAN (local area network). Sedangkan router digunakan untuk menghubungkan antar satu LAN dengan LAN yang lainnya.

2. Router juga berfungsi untuk menstran misikan informasi dari satu jaringan ke jaringan lain yang sistem kerjanya seperti Bridge.

3. Router juga berfungsi untuk menhubungkan jaringa lokal kesebuah koneksi DSL biasa juga disebut DSL router. Router ini umumnya memilki fungsi firewal untuk melakukan penapisan paket berdasarkan sumber serta alamat tujuan paket tersebut, namun tidak semua router memiliki fungsi yang sama. Router yang memiliki fitur penapisan paket dapat juga disebut sebagai packet – filtering router. Fungsi umum router ini memblokir lalulintas data yang dipancarkan secara broad cast sehingga dapat mencegah adanya broad cast storm yang bisa menyebabkan kinerja jaringan melambat.

Cara Kerja Router

Fungsi utama Router adalah merutekan paket (informasi). Sebuah Router memiliki kemampuan Routing, artinya Router secara cerdas dapat mengetahui kemana rute perjalanan informasi (paket) akan dilewatkan, apakah ditujukan untuk host lain yang satu network ataukah berada di network yang berbeda.

Jika paket-paket ditujukan untuk host pada network lain maka router akan meneruskannya ke network tersebut. Sebaliknya, jika paket-paket ditujukan untuk host yang satu network maka router akan menghalangi paket-paket keluar.

Pada gambar diatas terdapat 2 buah network yang terhubung dengan sebuah router. Network sebelah kiri yang terhubung ke port 1 router mempunyai alamat network 192.168.1.0 dan network sebelah kanan terhubung ke port 2 dari router dengan network address 192.155.2.0

• Komputer A mengirim data ke komputer C, maka router tidak akan meneruskan data tersebut ke network lain.
• Begitu pula ketika komputer F mengirim data ke E, router tidak akan meneruskan paket data ke network lain.
• Barulah ketika komputer F mengirimkan data ke komputer B, maka router akan menruskan paket data tersebut ke komputer B.

Daftar Sumber:

http://akinma.blogspot.co.id/2013/10/pengertian-jenis-fungsi-dan-cara-kerja.html

http://wikarahayu34xitkj2.blogspot.co.id/2012/06/sejrah-router.html
Terima kasih
Wasallam.