berhubung ga ada ide mau nyatet apa… yaa~~~ catetan q pas kuliah q taro aja disini

(ijin ya pak dosen… emoticon3)

nah nie dia catetan na

 

Metode Pemrograman Searching dan Sorting

 

  1. Metode Searching

Pencarian (Searching) merupakan proses yang fundamental dalam pemrograman, guna menemukan data (nilai) tertentu di dalam sekumpulan data yang bertipe sama. Fungsi pencarian itu sendiri adalah untuk memvalidasi (mencocokkan) data.

Sebagai contoh, dikehendaki untuk mendapatkan mahasiswa dengan nomor urut 9834567. Hasilnya adalah rekaman yang berisi data mahasiswa tersebut; yang barangkali berisi nama, alamat, tanggal lahir, dan nama program studi. Dalam implementasi, algoritma bisa jadi memberikan nilai balik berupa sebuah rekaman yang diperoleh, tetapi bisa pula hanya memberikan pointer yang menunjuk ke sebuah rekaman.
Pencarian dapat dilakukan terhadap data yang secara keseluruhan berada dalam memori komputer ataupun terhadap data yang berada dalam pencarian eksternal (harddisk). Pencarian yang dilakukan terhadap data yang berada dalam memori komputer dikenal dengan sebutan pencarian internal, sedangkan pencarian yang dilakukan pada media penyimpanan eksternal disebut pencarian eksternal.

Metode Serching dapat dibedakan menjadi 2, yaitu :

a)      Metode Pencarian Beruntun (Sekuensial Search)

Konsep yang digunakan dalam metode ini adalah membandingkan data-data yang ada dalam kumpulan tersebut, mulai dari elemen pertama sampai elemen ditemukan, atau sampai elemen terakhir.

b)      Metode Pencarian Bagi Dua (Binary Search)

Metode ini diterapkan pada sekumpulan data yang sudah terurut (menaik atau menurun). Metode ini lebih cepat dibandingkan metode pencarian beruntun. Data yang sudah terurut menjadi syarat mutlak untuk menggunakan metode ini.
Konsep dasar metode ini adalah membagi 2 jumlah elemennya, dan menentukan apakah data yang berada pada elemen paling tengah bernilai sama, lebih dari atau kurang dari nilai data yang akan dicari. Jika bernilai sama, maka langsung data yang 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. Dan 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. Dan demikian sebaliknya untuk data yang terurut menurun. Dalam hal ini tentukan indeks paling awal dan indeks paling akhir, untuk membagi 2 elemen tersebut.

Indeks awal = i, dimana nilai i, pada awalnya bernilai 0;

Indeks akhir = j, dimana nilai j, pada awalnya bernilai sama dengan jumlah elemen

 

 

  1. Metode Sorting

Pengurutan data (Sorting) 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.

Metode Sorting dapat dibedakan menjadi beberapa bagian, yaitu :

a)      Pengurutan Berdasarkan Perbandingan (Comparison-Based Sorting)

  • Bubble Sort

Bubble Sort merupakan metode sorting termudah. Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.

Pengurutan Ascending : Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.

Pengurutan Descending : Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.

Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya, ascending atau descending. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya sampai dengan iterasi sebanyak n-1. Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

  • Exchange Sort

Sangat mirip dengan Bubble Sort. Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort. Pebedaan : dalam hal bagaimana membandingkan antar elemen-elemennya :

  • Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu.  Jadi ada elemen yang selalu menjadi elemen pusat (pivot).
  • Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.

 

b)      Pengurutan Berdasarkan Prioritas (Priority Queue Sorting Method)

  • Selection Sort

Merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

  • Heap Sort

Heap Sort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort. Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n. Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT). Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue. Algoritma pengurutan heap dimulai dari membangun sebuah heap dari kumpulan data yang ingin diurutkan, dan kemudian menghapus data yang mempunyai nilai tertinggi dan menempatkan dalam akhir dari larik yang telah terurut. Setelah memindahkan data dengan nilai terbesar, proses berikutnya adalah membangun ulang heap dan memindahkan nilai terbesar pada heap tersebut dan menempatkannya dalam tempat terakhir pada larik terurut yang belum diisi data lain. Proses ini berulang sampai tidak ada lagi data yang tersisa dalam heap dan larik yang terurut penuh. Dalam implementasinya kita membutuhkan dua larik – satu untuk menyimpan heap dan satu lagi untuk menyimpan data yang sudah terurut. Tetapi untuk optimasi memori, kita dapat menggunakan hanya satu larik saja. Yaitu dengan cara menukar isi akar dengan elemen terakhir dalam heap tree. Jika memori tidak menjadi masalah maka dapat tetap menggunakan dua larik yaitu larik masukan dan larik hasil. Heap Sort memasukkan data masukan ke dalam struktur data heap. Nilai terbesar (dalam max-heap) atau nilai terkecil (dalam min-heap) diambil satu per satu sampai habis, nilai tersebut diambil dalam urutan yang terurut.

 

c)       Pengurutan Berdasarkan Penyisipan dan Penjagaan Terurut (Insert and Keep Sorted Method)

  • Insertion Sort

Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.

  • Tree Sort / Heap Tree

Secara umum, pengertian dari heap adalah bagian dari memori yang terorganisasi untuk dapat melayani alokasi memori secara dinamis [2]. Suatu heap tree adalah Complete Binary Tree (CBT) di mana harga-harga key pada nodenodenya sedemikian rupa sehingga haga-harga key pada nodenode anaknya tidak ada yang lebih besar dari harga key pada node orang tuanya [2]. Pengertian “lebih besar” di atas tidak mutlak, untuk beberapa kasus maka dapat diganti sesuai dengan permasalahan yang dihadapi.

 

d)      Pengurutan Berdasarkan Pembagian dan Penguasaan (Devide and Conquer Method)

  • Quick Sort

Quick sort merupakan divide and conquer algorithm. Algoritma ini mengambil salah satu elemen secara acak (biasanya dari tengah) lalu menyimpan semua elemen yang lebih kecil di sebelah kirinya dan semua elemen yang lebih besar di sebelah kanannya. Hal ini dilakukan secara rekursif terhadap elemen di sebelah kiri dan kanannya sampai semua elemen sudah terurut. Algoritma ini termasuk algoritma yang cukup baik dan cepat. Hal penting dalam algoritma ini adalah pemilihan nilai tengah yang baik sehingga tidak memperlambat proses sorting secara keseluruhan. Ide dari algoritma ini adalah sebagai berikut:

  • Pilih satu elemen secara acak
  • Pindahka semua elemen yang lebih kecil ke sebelah elemen tersebut dan semua elemen yang lebih besar ke sebelah kanannya. Elemen yang nilainya sama bisa disimpan di salah satunya. Ini disebut operasi partisi
  • Lakukan sort secara rekursif terhadap sublist sebelah kiri dan kanannya.

Quick sort adalah pengembangan dari binary tree sort, yang lebih menghemat ruang. Cara perbandingannya mirip, hanya pengurutannya berbeda. dibandingkan dengan merge sort, quick sort memiliki keuntungan di kompleksitas waktu sebesar Θ(log n), dibanding dengan merge sort sebesar Θ(n). Namun quick sort tidak mampu membandingkan linked list sebaik merge sort, karena ada kemungkinan pemilihan pivot yang buruk. Selain itu pada linked list merge sort memerlukan ruang yang lebih sedikit. Berdasarkan analisis tersebut quick sort termasuk algoritma sorting yang cukup baik, namun kita pun harus bisa memilih nilai pivot yang baik agar penggunaannya bisa optmal.

  • Merge Sort

Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945. Prinsip utama yang diimplementasikan pada algoritma merge-sort seringkali disebut sebagai pecah-belah dan taklukkan (bahasa Inggris: divide and conquer). Cara kerja algoritma merge sort adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. Menurut keefektifannya, algoritma ini bekerja dengan tingkat keefektifan.

 

e)      Pengurutan Berkurang Menurun (Diminishing Increment Sort Method)

  • Shell sort (pengembangan insertion)

Shell Sort adalah salah satu algoritma pengurutan yang lebih handal dibandingkan Selection Sort dan Bubble Sort. Kehandalannya yaitu membagi deret data menjadi dua bagian. Masing-masing bagian diurutkan menggunakan Bubble Sort. Tidak menggunakan iterasi melainkan increment. Perulangan diakukan sesuai nilai increment.


Daftar Pustaka

 

http://allaboutalgoritma.blogspot.com/2009/06/metode-bubble-sort.html

http://lusiajah.wordpress.com/2009/05/30/searching-dan-sorting-di-c/

 

 

 

 

Iklan