Makalah Sorting - Tugas 1 Setelah Uts.docx

MAKALAH PENGURUTAN ( SORTING )

DOSEN PEMBIMBING DZIKY RIDHWANULLAH , S KOM DISUSUN OLEH : AGUS ICHSANUDIN (17.5.00040) BAGASTIAN WAHYU KISARA (14.5.00030) ARMIANTO YUDHA SAPUTRO (17.5.00049) MARSAM ASMORO (17.5.00016) STMIK SINAR NUSANTARA TEKNIK INFORMATIKA 2017/2018

KATA PENGANTAR Alhamdulillahi Robbil ‘Alami, Segala puji bagi Allah SWT Tuhan Semesta Alam. Atas segala karunia nikmatNya sehingga kami dapat menyusun makalah ini dengan sebaik-baiknya. Makalah yang berjudul “Pengurutan (Sorting)” disusun dalam rangka memenuhi salah satu tugas mata pelajaran Struktur Data yang diampu oleh Bapak Dziky Ridhwanullah , s kom Makalah ini berisi tentang materi – materi dalam pengurutan (Sorting) yang merupakan materi yang harus diketahui dalam MataKuliah Struktur Data. Dalam penyusunannya melibatkan berbagai pihak, baik dari dalam kampus maupun luar kampus. Oleh sebab itu kami mengucapkan banyak terima kasih atas segala kontribusinya dalam membantu penyusunan makalah ini. Meski telah disusun secara maksimal, namun penulis sebagai manusia biasa menyadari bahwa makalah ini masih jauh dari sempurna. Karenanya penulis mengharapkan kritik dan saran yang membangun dari pembaca sekalian. Besar harapan kami makalah ini dapat menjadi sarana membantu mahasiswa dalam pemahaman materi pengurutan (Sorting) dalam mata kuliah Struktur Data Demikian apa yang bisa kami sampaikan, semoga pembaca dapat mengambil manfaat dari karya ini. Surakarta, 7 Desember 2018 Penulis

BAB 1 PENDAHULUAN Latar Belakang Dalam penyajian data kita sering kali mendapati data data yang tersusun secara acak . Hal ini menyebabkan proses pendataan yang terjadi di dalam nya kurang efisien dan

efektik untuk di kerjakan . Pada Struktur Data kita dapat mengetahui solusi dalam masalah ini. Masalah ini dapat di selesaikan dengan menggunakan cara Pengurutan ( Sorting ) data. 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. Rumusan Masalah : 1. Metode apa saja yang bisa dipakai dalam penguruan data ? 2. Bagaimana peng-impementasiannya kepada sebuah program 3. Apa keuntungan setelah dilakukkannya pengurutan data Tujuan : 1. Dapat Mengetahui Metode – metode dalam Pengurutan Data 2. Dapat mengetahui bagaimana cara pengimpementasiannya ked alam program 3. Dapat Mengetahui manfaat setelah menggunakan Pengurutan ( Sorting )

Bab 2 PEMBAHASAN

Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu. Disini akan dijelaskan 5 metode sorting yaitu : a. Metoda Shell sort b. Metoda Quick sort c. Metoda Heap sort d. Metoda Merge sort e. Metoda Common sort A. Metoda Shell sort Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959,

sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut : Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2). Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4). Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah Algoritma metode Shell dapat dituliskan sebagai berikut : 1. Jarak = N 2. Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9 3. Jarak = Jarak / 2. Sudah = false 4. Kerjakan baris 4 sampai dengan 8 selama Sudah = false 5. Sudah = true 6. j = 0 7. Selama (j < N – Jarak) kerjakan baris 8 dan 9 8. Jika (Data[j] > Data[ j + Jarak] maka tukar Data[j], Data[j + Jarak]. Sudah = true 9. j = j + 1 Berikut implementasi program shell sort

Hasil

B. Metoda Quick Sort Quick sort merupakan suatu metode pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Cara mengurutkan data dengan Quick sort : 1. Pertama siapkan angka yang ingin diurutkan dengan metode Quick sort Seandainya 1 12 5 26 7 14 3 7 1 2. Pilih elemen sementara atau pivot value, contohnya 7, elemen sementara ini berguna sebagai patokan selesainya partisi. Karena hanya sementara, jadi kalau partisinya sudah mencapai elemen sementara tersebut maka partisi selesai dan harus memilih elemen sementara yang lain sebagai patokan 1 12 5 26 7 14 3 7 2 pivot value = 7 Pivot value 3. Setelah ditentukan eleme sementaranya, kita pilih angka pertama dan terakhir. Karena angka pertama sudah benar posisinya yaitu angka 1 lebih kecil dari angka 7 (elemen sementara), maka kita geser satu angka dari angka pertama yaitu angka 12. Angka terakhir belum benar dan mesti dicocokan jadi tidak harus menggeser ke angka sebelahnya terlebih dahulu. Lalu setelah itu, angka 12 dan angka 2 kita tukar karena 2 lebih kecil dari angka elemen sementara tadi yaitu 7 dan angka 12 lebih besar dari angka 7, yang lebih kecil dari elemen dasar letaknya di kiri dan yang lebih besar di kanan. 1 12 5 26 7 14 3 7 2

12 ≥ 7 ≥ 2, swap 12 and 2

4. Dilanjutkan dengan angka 5 dan 7, karena angka 5 sudah benar letaknya karena lebih kecil dari 7 (elemen dasar) maka geser 1 angka ke angka 26, karena 7 sama dengan 7 (elemen dasar) maka tetap Lalu tukar angka 26 dengan angka 7 1 2 5 26 7 14 3 7 12 26 ≥ 7 ≥ 7,swap 26 and 7

5. Kemudian giliran angka 7 (Elemen sementaranya) dengan angka 3, caranya masih sama dengan yang tadi karena 3 lebih kecil dari 7 dan 7 lebih besar jadi ditukar.,m1 2 5 7 7 14 3 26 12 7 ≥ 7 ≥ 3,swap and 3

6. Karena sudah mencapai elemen sementara tadi yaitu 7, maka partisi dengan elemen sementara angka 7 tadi selesai dan mendapatkan hasil seperti ini

1 2 5 7 3 14 7 26 12

i > j, stop partition

7. Ulangi seperti langkah-langkah sebelumnya dengan elemen sementara yang baru sampai angka-angkanya terurut. 1 2 5 7 3 14 7 26 12 run quick sort recursively 8. Maka angka akan urut. 1 2 3 5 7 7 12 14 26 sorted

Berikut implementasi program Quick sort

Hasil

C. Metoda Heap Sort

Pengertian Heap Sort merupakan salah satu dari 6 jenis metode sort atau sorting (melakukkan pengurutan). Heap sort ini menggunakan teknik sorting dengan menggunakan teknik heap. Teknik tersebut tersebut merupakan teknik pengelolaan data yang menggunakan binary tree. Data yang dikelola maksudnya adalah bagaimana data yang sudah terstruktur akan di organisir kembali jika kita memasukkan data baru atau meng-insert data baru, atau pula menghapus data. Teknik itulah yang diterapkan di metode heap sort. Inti dari pengurutan secara heap adalah pengerjaannya yang dilakukkan dengan pengurutan ascending dan descending, jadi ada dua kali pengurutan. Lebih lengkapnya akan dijelaskan di bagian metode. Perlu diingat dalam melakukkan pengurutan dengan heap sort, usahakan untuk membawa coret-coretan bagi yang bingung buat mempermudah pembelajaran. Bagi yang sanggup mencerna metodenya di luar kepala cukup dengan membaca metode dan langkahnya di bagian metode. Metode Metode Heap sort akan dijelaskan dibawah ini. Seperti biasa, kita akan mengurutkan secara ascending suatu himpunan baris data berikut. 5239 Kita punya 6 data yang masih berantakan dan tidak teratur, sekarang kita akan mengurutkannya dengan metode Heap sort. Sebelum kita urutkan secara ascending, terlebih dahulu kita memasukkannya ke heap mode. Bagaimana caranya? Perhatikan gambar berikut.

Penjelasan

1. Pertama kita masukkan rangkaian data ke heap tree. Masukkan data pertama yaitu 5 menjadi parent. 2. Masukkan data berikutnya yaitu 2 menjadi child dari 5. Masukkan ke bagian kiri terlebih dahulu. 3. Masukkan data berikutnya yaitu 3 ke child bagian kanan. 4. Masukkan data berikutnya yaitu 9 menjadi child dari 2. Nah karena data 9 lebih besar dari data 2 maka letaknya kita tukar. 5. Sekarang data 9 menjadi child kiri dari data 5. Karena 9 masih lebih besar dari 5, letaknya kita tukar. 6. Sekarang 9 menjadi parent yang memiliki child kiri 5 dan child kanan 3. Mengapa Begitu? Karena kita ingin mengurutkan data secara ascending, maka yang kita lakukkan pada tree adalah melakukkan descending yaitu kebalikannya. Karena sekarang nilai terbesar yaitu 9 sudah pada posisi parent kita keluarkan dari heap dan letakkan ke paling kanan baris dan sudah terhitung fully sorted (sudah tersusun). 7. Karena data 9 sudah keluar dari heap, maka data paling kanan dari heap maju menjadi parent. Kali ini data 3 menjadi parent. 8. Lalu posisi heap sekarang adalah data 3 sebagai parent memiliki child kiri 5 yang memiliki child kiri 2. Sekarang kita bandingkan kembali, 9. Karena 5 lebih besar dari 3 maka posisi kita tukar. 10. Sekarang 5 menjadi parent dengan child 3, dan 3 memiliki child 2. Pada posisi sekarang karena 3 sudah lebih besar dari 2 maka tidak kita tukar. 11. Berikutnya kita keluarkan data 5 dari heap dan letakkan di sebelah kiri data 9 yang sudah tersusun tadi. Jadikan fully sorted. 12. Data 3 berubah menjadi parent dan karena tidak ada perubahan posisi maka data 3 kita keluarkan dan taruh di kiri data 5 sebagai fully sorted. 13. Data terakhir yang tersisia yaitu data 2 kita keluarkan dari heap dan kita letakkan di kiri data 3 sehingga sekarang semua data sudah tersortir.

Implementasi

Hasil

D. Metoda Merge sort Mergesort adalahmetode pengurutan lanjut, sama dengan metode Quick Sort. Metode ini juga juga menggunakan konsep devide and conquer yang membagi data S dalam 2 kelompok yaitu S1 dan S2 yang tidak beririsan (disjoint). Proses pembagian data dilakukan secara rekursif sampa data tidak dapat dibagi lagi atau dengan kata lain data dalam sub bagian mnjadi tunggal Setelah data tidak dapat dibagi lagi, proses penggabungan (merging) dilakukan antara sub-sub bagian dengan memperhatikan urutan data yang diinginkan (ascending/kecil ke besar atau descending/besar ke kecil). Proses penggabungan ini dilakukan sampai semua data tergabung dan terurut sesuai urutan yang diinginkan. Kompleksitas algoritma merge sort adalah O (n log n). Secara umum algoritma merge sort dapat diimplementasikan secara rekursif. Fungsi rekursif adalah sebuah fungsi yang didalam implementasinya memanggil dirinya sendiri. Pemanggilan diri sendiri ini berakhir jika kondisi tertentu terpenuhi (terminated condition is true). Pada contoh berikut ini, terminated condition dari proses rekursif mergesort akan berakhir jika data tidak dapat dibagi lagi (data tunggal telah diperoleh). Dengan kata lain, proses pembagia data dilakukan terus selama S.size > 1 (belum tunggal).

Illustrasi dari algoritma merge sort adalah sebagai berikut :

Algoritma mergesort(S,C) Input: n elemen dari data S dan comparator C Output: data S terurut berdasarkan C if S.size()>1 (S1,S2) ← partisi(S.n/2) mergesort(S1,C) mergesort(S2,C) S ← merge(S1,S2)

Fungsi merge berfungsi untuk menggabungkan hasil pengurutan dari sub bagian S1 dan S2 berdasarkan urutan tertentu (ascending atau descending order). Kompleksitas proses penggabungan ini (merging) adalah O(n). Algoritma dari proses penggabungan adalah : Algoritma merge(S1,S2) Input: data S1 dan S2 dengan n/2 elemen per data Output: data terurut dari penggabungan S1 S2 S ← data kosong while not S1.empty() and not S2.empty() if S1.first().elemen() < S2.first().elemen() S.insert(S1.remove(S1.first()) else S.insert(S2.remove(S2.first()) while not S1.empty() S.insert(S1.remove(S1.first()) while not S2.empty() S.insert(S2.remove(S2.first()) return S

Illustrasi Algoritma Merge Sort

Mengurutkan data berikut menggunakan metode merge sort 40 75 12 68 72 9 56 18 60 5 20 65 2 Impleentasi Merge Sort :

Hasil

E. Metoda Common Sort Common sort termasuk juma dalam katagori Exchange sort. Algoritma dari metode ini adalah dengan membandingkan elemen ke-i dengan elemen ke-i +1, sedangkan i mulai dari 1 hingga ke n-1 elemen. Bila elemen ke-i +1 > elemen ke-i, maka lakukan pertukaran tempat. Lakukan poroses tersebut berulang dari awal sampai tidak terjadi lagi pertukaran tempat. Contoh data awal : 6, 7, 3, 4, 8 Pass 1,

Pass 2,

Pass 3,

Proses 1 menghasilkan

: 6, 7, 3, 4, 8

Proses 2 menghasilkan

: 6, 3, 7, 4, 8

Proses 3 menghasilkan

: 6, 3, 4, 7, 8

Proses 4 menghasilkan

: 6, 3, 4, 7, 8 (putaran 1 masih ada pertukaran)

Proses 1 menghasilkan

: 3, 6, 4, 7, 8

Proses 2 menghasilkan

: 3, 4, 6, 7, 8

Proses 3 menghasilkan

: 3, 4, 6, 7, 8

Proses 4 menghasilkan

: 3, 4, 6, 7, 8 (putaran 2 masih ada pertukaran)

Proses 1 menghasilkan

: 3, 4, 6, 7, 8

Proses 2 menghasilkan

: 3, 4, 6, 7, 8

Proses 3 menghasilkan

: 3, 4, 6, 7, 8

Proses 4 menghasilkan

: 3, 4, 6, 7, 8 (putaran 3 tidak ada pertukaran)

Dan banyak lago teknik-teknik sortir yang lain. Yang mana yang terbaik tidak dapat ditentukan secara pasti, tergantung dari banyak data posisi (urutan pemasukan) data, dan kapasitas memori. Namun sedikit banyaknya bisa dilakukan dengan cara menghitung kompleksitas waktu algoritmanya.

Metode Common sort Pengurutan dilakukan dengan memilih elemen terbesar dan menempatkan pada posisinya, kemudian mencari element terbesar berikutnya dan menempatkan pada tempatnya, dan seterusnya

BAB 3 PENUTUP Kesimpulan Dari penjelasan di atas menyatakan bahwa kesimpulan nya adalah metode shellsort sangat efektif digunakan pada tabel dengan range yang besar, Untuk quicksort ada beberapa yang membuat quick sort menjadi unggul : 1. Secara umum memiliki kompleksitas O(n log n). 2. Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien. 3. Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti merge sort dan heap sort. 4. Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori. 5. Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter). Namun terdapat pula kelemahan quick sort: 1. Sedikit kesalahan dalam penulisan progran program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai). 2. Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n2). 3. Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).

4. Pada penerapan secara rekursif ( memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program. Untuk pengurutan heap sort dapat disimpulkan bahwa metode heap sort memiliki keunggulan yaitu terletak pada kompleksitas waktu asimptotiknya yang sangat baik. Meskipun kebih lambat dari pengurutan data yang lain, heap sort memiliki kelebihan ketika menangani data dalam skala yang besar/massive. Karena metode ini memiliki kelebihan tidak menggunakan banyak tabel, tetapi hanya satu tabel yang dipakai untuk menyimpan hasil dari pengurutan tersebut Untuk merge sort, Metode ini adalah metode pengurutan data dengan cara data dibagi menjadi subkumpulan-subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali dengan metode merging. Untuk metoda common sort hampir sama dengan quick sort namun perbedaannya pada data yang di pisahkan data pertama dan data kedua.

Daftar Pustaka http://www.materi-it.com/2015/03/source-code-merge-sorting-java-netbeans.html https://andihartono.net/2011/12/21/program-quicksort-dengan-java/ https://dinda-dinho.blogspot.com/2013/07/sorting-dengan-metode-quick-sort.html?m=1 http://otatechnime.blogspot.com/2017/03/pengertian-heap-sort.html https://www.sanfoundry.com/java-program-implement-heap-sort/ http://nuradiarah62.blogspot.com/2016/10/makalah-sorting.html https://codereview.stackexchange.com/questions/176340/common-sorting-algorithms