Sesi 29 (Sorting and Searching)

Sorting adalah mengurutkan data dari terbesar atau terkecil sorting juga berguna untuk mempercepat pencaharian.

Algoritma sorting ada 2 yaitu:

1. Internal Sorting, yang mana semua data di sorting dimuat dalam RAM.

2. External Sorting, yang mana proses sorting menggunakan penyimpanan kedua.

Sorting ada 5 jenis yaitu:

1. Bubble Sort

     Sorting ini cara kerjanya adalah membandingkan masing-masing item dalam suatu list secara berpasangan, dan mengulanginya sampai akhir list secara berurutan, sehingga tidak ada lagi item yang dapat ditukar.

2. Selection Sort

     Sorting ini memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen - 1.

3. Insertion Sort

     Sorting ini memilah data yang akan diurutkan menjadi 2 bagian, yang belum diurutkan dan yang sudah diurutkan. elemen pertama diambil dari bagian array yang belum diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

4. Quick Sort

sorting ini berdasar pada pola divide-and-conquer.

     a. Divide

          Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

     b. Conquer

          Mengurutkan elemen pada sub-rangkaian secara rekursif. Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

5. Merge Sort

     Sorting ini dirumuskan dalam 3 langkah berpola, yaitu:

1. Devide, memilah elemen-elemen dari rangkaian data menjadi 2 bagian

2. Conquer, Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif

3. Kombinasi, mengombinasi dua bagian tersebut secara rekursif untuk mendapatkan rangkaian              data yang berurutan

     Proses rekursif akan berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Searching adalah mencari data yang kita dibutuhkan.

Searching ada 3 jenis yaitu:

1. Linear Search / Sequential Search

     Merupakan metode pencarian data dalam array dengan cara membandingkan data yang dicari dengan data yang ada di dalam array secara berurutan. Pencarian data dengan Metode Sequential Search efektif untuk mencari data yang dalam posisi yang tidak terurut atau acak.

     *Algoritma Linear Search

• Menentukan data yang dicari
• Membaca data array satu per satu secara sekuensial
• Mulai dari data pertama sampai dengan data terakhir, kemudian data yang dicari tadi dibandingkan dengan masing-masing data yang ada di dalam array.
• Jika data yang dicari ditemukan maka kita dapat membuat statement bahwa data telah temukan.
• Jika data yang dicari tidak ditemukan maka kita dapat membuat statement bahwa data telah temukan.

     *Kelebihan dan Kekurangan Linear Search:

• Kelebihan Sequential Searching bisa dikatakan lebih mudah dalam implementasinya dalam pemrograman.
• Kekurangannya jika data yang terdapat dalam suatu array itu sangat banyak, maka akan diperlukan waktu yang lebih lama untuk membandingkan data yang dicari dengan jumlah data yang sangat banyak dalam suatu array.

     Dapat disimpulkan bahwa sequential search, akan mencari data dengan cara membandingkannya satu-persatu dengan data yang ada. Prosesnya tentu saja akan singkat jika data yang diolah sedikit, dan akan lama jika data yang diolah banyak. Disarankan proses ini digunakan pada jumlah data yang sedikit saja.

2. Binary Search

     Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu. Jika terdapat N buah data yang akan diolah, data yang dicari akan dibandingkan dengan data ke-N jika data ke-N lebih besar dari data yang dicari maka akan dilakukan pembagian data menjadi dua bagian. Kemudian ujung data pada setiap bagian dibandingkan lagi dengan nilai yang akan dicari.

     *Algoritma Binary Search:

     #Proses Binary Search yang urutan datanya ascending:

• Pertama buat perulangan lalu menentukan posisi low yaitu posisi yang menandakan index paling rendah kemudian menentukan posisi high. Kemudian mencari posisi mid = (high + low)/2
• Lalu membandingkan data yang dicari dengan nilai yang ada di posisi mid.
• Jika data yang dicari sama dengan nilai yang ada di posisi mid berarti data ditemukan.
• Jika data yang dicari lebih kecil dari nilai yang ada di posisi mid maka pencarian data akan dilakukan dibagian kiri mid dengan melakukan pembandingan. dengan kondisi posisi high berubah yaitu (mid - 1) dan posisi low tetap.
• Jika data yang dicari lebih besar dari nilai yang ada mid  maka pencarian data akan dilakukan di bagian kanan dari mid dengan posisi low yang berubah yaitu (mid + 1) dan posisi high tetap.

     *Kelebihan dan Kekurangan Binary Search:

• Kelebihannya yaitu tidak perlu membandingkan data yang dicari dengan seluruh data array yang ada, cukup melalui titik tengah kemudian kita bisa menentukan ke mana selanjutnya mencari data yang ingin dicari.
• Kekurangannya, implementasi agak sedikit lebih rumit karena tidak bisa digunakan pada data array yang masih acak. Jadi harus melakukan sorting terlebih dahulu dalam implementasinya.

3. Interpolation Search

     Proses pencarian data ini hampir sama dengan proses pencarian binary search, pencarian ini juga dilakukan pada kumpulan data yang sudah urut. Akan tetapi jika pada binary search kita membagi data menjadi 2 bagian tiap prosesnya, pada interpolation search kita akan membagi data menurut rumus sebagai berikut: 

Posisi = ( kunci – data[low] / data[high] – data[low] ) * ( high – low ) + low.

Contoh sehari-harinya yaitu: jika kita mencari kata dalam KBBI dengan awalan M, kita tidak perlu mencari dari awal kamus. Tapi, kita dapat langsung mencari pada bagian tengah kamus tersebut.