Kelompok 13 Selection Sort & Shell Sort PDF

Preview

Summary

LAPORAN KOMPLEKSITAS ALGORITMA SELECTION SORT & SHELL SORT Disusun Oleh : Kelompok 13 Ahmad Ridhani 1615015116 Andi Baso Muhammad Fahri 1615015123 TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS MULAWARMAN SAMARINDA 2017 i KATA PENGANTAR Assalammualaikum Wr. Wb Puji...

Description

LAPORAN KOMPLEKSITAS ALGORITMA SELECTION SORT & SHELL SORT

Disusun Oleh : Kelompok 13 Ahmad Ridhani Andi Baso Muhammad Fahri

1615015116 1615015123

TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS MULAWARMAN SAMARINDA 2017

i

KATA PENGANTAR Assalammualaikum Wr. Wb Puji syukur kepada Tuhan yang Maha Esa yang telah memberi kami kesehatan dan kemudahan serta rahmat dan hidayahnya, sehingga laporan ini dapat terselesaikan dengan tepat waktu dan sebaik mungkin. Laporan ini dibuat untuk memenuhi materi dan tugas Kompleksitas Algoritma pada semester 3 (ganjil) ini . Laporan ini berjudul “SELECTION SORT DAN SHELL SORT”. Selanjutnya kami mengucapkan terima kasih kepada Ibu Masna Wati, S.Si, MT, selaku dosen pengampu mata kuliah Kompleksitas Algoritma di Fakultas Ilmu Komputer dan Teknologi Informasi. Kami menyadari dalam penyusunan laporan ini masih terdapat banyak kekurangan dan kesalahan dan apabila ada kritik maupun saran penulis berlapang dada untuk menerimanya. Akhir kata semoga laporan ini dapat memberikan manfaat untuk kita semua. Wassalammualaikum Wr. Wb

Samarinda,

November 2017

Penyusun

ii

DAFTAR ISI Halaman COVER ............................................................................................................. i KATA PENGANTAR ...................................................................................... ii DAFTAR ISI ..................................................................................................... iii BAB I . SELECTION SORT DAN SHELL SORT .................................... A. Selection Sort ................................................................................... 1. Pengertian Selection Sort ........................................................... 2. Algoritma Selection Sort ............................................................ 3. Contoh Kasus Selection Sort...................................................... 4. Kelebihan dan Kelemahan Selection Sort .................................. B. Shell Sort .......................................................................................... 1. Pengertian Shell Sort .................................................................. 2. Algoritma Shell Sort .................................................................. 3. Contoh Kasus Shell Sort ............................................................ 4. Kelebihan dan Kelemahan Shell Sort ........................................

1 1 1 1 2 3 4 4 5 5 6

BAB II. KOMPLEKSITAS WAKTU .......................................................... A. Kompleksitas Waktu ........................................................................ 1. Pengertian Kompleksitas Waktu ................................................ 2. Kompleksitas Waktu Selection Sort........................................... 3. Kompleksitas Waktu Shell Sort .................................................

7 7 7 8 9

BAB III. KOMPLEKSITAS WAKTU ASIMPTOTIK ............................. A. Pengertian Kompleksitas Waktu Asimptotik ................................... 1. Kasus Terbaik (Best Case) ......................................................... 2. Kasus Terburuk (Worst Case) ....................................................

10 10 10 10

BAB IV. KESIMPULAN .............................................................................. 12 DAFTAR PUSTAKA ....................................................................................... 13 LAMPIRAN ...................................................................................................... 14

iii

BAB I SELECTION SORT DAN SHELL SORT

A. Selection Short 1. Pengertian Selection Sort Selection Sort merupakan salah satu algoritma pengurutan yang sederhana. Ide dasarnya adalah 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. 2. Algoritma Selection Sort Selection Sort diakui karena kesederhanaan algoritmanya dan performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi tertentu. Algoritma ini bekerja sebagai berikut: 1. Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list 2. Menukarkan nilai ini dengan elemen pertama list 3. Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua. 4. Selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. 5. Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dan nilai data terbesar dimulai dari data diposisi 0 hingga diposisi N-1. Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan.

1

contoh simulasi algoritma selection sort, jika kita memiliki elemen array sbb : {5, 1, 12, -5, 16, 2, 12, 14}

Algoritma di dalam Selection Sort terdiri dari kalang bersarang. Dimana kalang tingkat pertama (disebut pass) berlangsung N-1 kali. Di dalam kalang kedua, dicari elemen dengan nilai terkecil. Jika didapat, indeks yang didapat ditimpakan ke variabel min. Lalu dilakukan proses penukaran. Begitu seterusnya untuk setiap Pass. Pass sendiri makin berkurang hingga nilainya menjadi semakin kecil. Berdasarkan operasi perbandingan elemennya. 3. Contoh Kasus Selection Sort Proses pengurutan menggunakan metode selection sort secara terurut adalah sebagai berikut: 1. Mencari data terkecil dari data pertama sampai dengan data yang terakhir. kemudian ditukar posisinya dengan data pertama.

2

2. Mencari data terkecil dari data kedua sampai dengan data terakhir, kemudian ditukar posisinya dengan data kedua. 3. Mencari data terkecil dari data ketiga sam[ai data terakhir, kemudian ditukar posisimya dengan data ketiga. 4. Begitu seterusnya sampai semua data terurut naik. Apabila terdapat n buah data yang akan diurutkan, maka membutuhkan (n-1) langkah pengurutan, dengan data terakhir, yaitu data ke n tidak perlu diurutkan karena hanya tinggal data satu-satunya.

4. Kelebihan dan Kelemahan Selection Sort Kelebihan selection sort :

➢ ➢ ➢ ➢ ➢

Algoritma ini sangat rapat dan mudah untuk diimplementasikan. Operasi pertukarannya hanya dilakukan sekali saja. Waktu pengurutan dapat lebih ditekan. Mudah menggabungkannya kembali. Kompleksitas selection sort relatif lebih kecil.

Kekurangan/kelemahan selection sort :. ➢ Sulit untuk membagi masalah. ➢ Membutuhkan method tambahan.

3

B. Shell Sort 1. Pengertian 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 : 1.

Menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2.

2.

Data pertama dibandingkan dengan data dengan jarak N / 2.

3. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. 4. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2. 5. 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 1.

4

2. Algoritma Shell Sort Algoritma metode Shell dapat dituliskan sebagai berikut : 1. 2. 3. 4. 5. 6. 7. 8.

Jarak = N Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9 Jarak = Jarak / 2. Sudah = false Kerjakan baris 4 sampai dengan 8 selama Sudah = false Sudah = true j=0 Selama (j < N – Jarak) kerjakan baris 8 dan 9 Jika (Data[j] > Data[j + Jarak] maka tukar Data[j], Data[j + Jarak]. Sudah = true 9. j = j + 1

3. Contoh Kasus Shell Sort

•

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

•

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

5

•

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

4. Kelebihan dan kekurangan shell sort Kelebihan shell sort :

➢ ➢ ➢ ➢

Operasi pertukarannya hanya dilakukan sekali saja. Algoritma ini sangat rapat dan mudah untuk diimplementasikan.. Waktu pengurutan dapat lebih ditekan. Mudah menggabungkannya kembali.

Kekurangan/kelemahan selection sort : ➢ Membutuhkan method tambahan. ➢ Sulit untuk membagi masalah.

6

BAB II KOMPLEKSITAS WAKTU

A. Kompleksitas Waktu 1. Pengertian Kompleksitas Waktu Kompleksitas waktu dari algoritma adalah mengukur jumlah perhitungan (komputasi) yang dikerjakan oleh komputer ketika menyelesaikan suatu masalah dengan menggunakan algoritma. Kompleksitas waktu merupakan hal penting untuk mengukur efisiensi suatu algoritma. Kompleksitas waktu dari suatu algoritma yang terukur sebagai suatu fungsi ukuran masalah. Kompleksitas waktu dari algoritma berisi ekspresi bilangan dan jumlah langkah yang dibutuhkan sebagai fungsi dari ukuran permasalahan. Kompleksitas ruang berkaitan dengan sistem memori yang dibutuhkan dalam eksekusi program. Pada tabel di bawah diperlihatkan kelompok algoritma berdasarkan kompleksitas waktu asimptotiknya.

7

KOMPLEKSITAS WAKTU SELECTION SORT

1. START

1

2. READ int [] angka = {8,3,4,7,2,6,5,1,10,9};

1

3. READ NAMA CLASSNYA (angka);

1

4. READ public static void Selection_Short (int [] angka)

1

5. READ for (int i=0 ; i...