7.Sorting & Searching

Sorting & Searching ABDI PANDU KUSUMA, S.KOM, M.T

Sorting ABDI PANDU KUSUMA, S.KOM, M.T

Definisi Sorting Sorting → Pengurutan Sorting → proses mengatur sekumpulan obyek menurut urutan atau susunan tertentu, dimana urutan tersebut dapat menaik (ascending) atau menurun (descending). Macam-macam sorting: ✓ Shell Sort ✓ Bubble Sort ✓ Merge Sort ✓ Selection Sort ✓ Radix Sort ✓ Insertion Sort ✓ Tree Sort ✓ Quick Sort ✓ Heap Sort

Bubble Sort  Metode ini digambarkan sebagai gelembung sabun yang berada di permukaan air.  Karena berat jenis gelembung sabun lebih ringan dibandingkan dengan berat jenis air, sehingga gelembung sabun selalu terapung di permukaan air.  Prinsip pengapungan inilah yang diterapkan ke metode ini, dimana nilai yang paling rendah berada di posisi paling atas, melalui proses pertukaran. Algoritma Bubble Sort: ▪ Untuk pengurutan menaik, lakukan perbandingan sebagai berikut : L[n] < L[n-1] ▪ Untuk pengurutan menurun, lakukan perbandingan sebagai berikut : L[n] > L[n-1]

Bubble Sort

Bubble Sort Ilustrasi Bubble Sort:

Selection Sort  Metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data larik L, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan.  Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikutsertakan pada proses pencarian data maksimum/minimum berikutnya. Algoritma Selection Sort: Tentukan jumlah iterasi, yaitu pass = n-2 Untuk setiap pass ke-I = 0,1,2, … , pass: a. Cari elemen terbesar (maks) dari elemen ke-i sampai ke-(n- 1) b. Pertukaran maks dengan elemen ke-i

Selection Sort

Selection Sort Ilustrasi Selection Sort:

Insertion Sort  Metode ini bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan.  Metode ini mengurutkan bilangan-bilangan yang telah dibaca dan berikutnya berulang akan meyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi array yang telah terurut. Algoritma Insertion Sort:

Insertion Sort

Insertion Sort Ilustrasi Insertion Sort:

Latihan 1  Urutkan bilangan (3,6,4,1,2) menggunakan Bubble Sort! Penyelesaian (analisa):

Latihan 2  Urutkan bilangan (3,6,4,1,2) menggunakan Selection Sort! Penyelesaian (analisa):

Searching ABDI PANDU KUSUMA, S.KOM, M.T

Pengantar Searching Searching (Pencarian) → ??? Searching (Pencarian) → Sebuah cara untuk melakukan validasi (pencocokan) data. Terdapat beberapa metode mencari data di dalam sekumpulan data yang bertipe sama yaitu : a) Metode Pencarian Beruntun (Sequential Search) b) Metode Pencarian Bagi Dua (Binary Search)

Sequential Searching Metode ini digunakan dengan membandingkan antar data yang ada dalam kumpulan data, mulai dari elemen pertama sampai elemen ditemukan, atau sampai elemen terakhir. Algoritma Sequential Searching

Binary Searching Metode ini dilakukan dengan cara membagi 2 jumlah elemennya, dan menentukan apakah data yang berada pada elemen paling tengah bernilai sama, maka langsung data tengah dicari ditemukan. ✓ Jika data di elemen terurut naik, maka jika data yang berada di tengah kurang dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kanan, dan begitu seterusnya sampai ketemu atau tidak sama sekali. ✓ Sebaliknya untuk nilai data yang berada di tengah lebih dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kiri, dan begitu seterusnya sampai ketemu atau tidak sama sekali.

Ilustrasi Binary Search 3 9 11 12 15 17 23 31 35 Carilah data dengan nilai 17. SOLUSI: ✓ Untuk mendapatkan nilai tengah, dengan cara menjumlahkan indeks pertama bernilai 1 dan indeks ke-9 ✓ Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2 ✓ Kemudian data yang dicari dibandingkan dengan data di tengah, apakah sama atau lebih kecil, atau lebih besar? ✓ Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah – 1 ✓ Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah + 1 ✓ Jika data sama, berarti data ditemukan.

Latihan 3  Cari nilai 1 pada deretan angka (5,2,1,5,7,9,8,3) menggunakan sequential search! Penyelesaian (Analisa):

Latihan 4  Cari nilai 17 pada deretan angka (3,9,11,12,15,17,23,31,35) menggunakan binary search! Penyelesaian (Analisa):

??? ADA PERTANYAAN ???

Tugas 4 ❖ Jelaskan beserta langkah manual pengurutan menggunakan metode: (dikerjakan dengan ditulis tangan dan discan bentuk pdf dalam 1 file). NIM Genap : Quick Sort, Shell Sort, & Heap Sort NIM Ganjil : Merge Sort, Tree Sort, & Radix Sort ❖ Buat program untuk mencari angka “8” pada bilangan- bilangan berikut menggunakan metode pencarian: NIM Genap: {4,9,1,7,5,8,2,0} => Breadth First Search NIM Ganjil : {22,5,11,6,33,7,55,8,44} => Depth First Search Tugas dikirimkan via Edlink terakhir pada tanggal 14 Juni 2022 pukul 18.00 dalam bentuk RAR dengan format ”Tugas4_NIM_Nama_Mhs_Genap/Ganjil_SK2”.