Minggu, 03 April 2011

Teknik Sorting dan Searching

SORTING


Dewasa ini kita tidak perlu lagi untuk mengurutkan kumpulan data - data dengan cara manual, karena era ini sudah banyak sekali metode atau program untuk melakukan kebutuhan sorting.

Ada 5 metode dalam teknik sorting, diantaranya adalah :

1. Comparison-Based Sorting (pengurutan berdasarkan perbandingan)
# Bubble sort, exchange sort

2. Priority Queue Sorting Method (pengurutan berdasarkan prioritas)
# Selection sort, heap sort

3. Insert and Keep Sorted Method (pengurutan berdasarkan penyisipan dan penjagaan terurut)
# Insertion sort, tree sort

4. Devide and Conquer Method(pengurutan berdasarkan pembagian dan penguasaan)
# Quick sort, merge sort

5. Diminishing Increment Sort Method (pengurutan berkurang menurun)
# Shell sort


- Bubble Sort

Teknik ini dilakukan degan pola membawa nilai terbesar menjadi nilai index terakhir array. jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data.

- Exchange Sort

Teknik sorting ini dibuat dengan cara pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.

- Selection Sort

Teknik sorting ini dibuat dengan cara melakukan pengecek'an 1 persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecek'an nilai tempat yang pertama (index pertama pada array)kita bandingkan dengan semua nilai yang ada kita cari nilai minimalnya. lalu simpan index/ letak nilai minimum itu di temukan, setelah pengecekan selesai tukar index awal pengecekan dengan nilai minimum yang telah di simpan tadi. Proses ini dilakukan terus menerus sampai pada pengecekan index terakhir min 1 dengan index terakhir. beda dengan streith selection sort adalah dengan teknik ini melakukan pertukaran nilai lebih sedikit, hanya jumlah data - 1 pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.

- Heap Sort

Teknik sorting ini dibuat dengan versi yang jauh lebih efisien selection sort. Ia juga bekerja dengan menentukan elemen (atau terkecil) terbesar daftar, menempatkan bahwa pada akhir (atau awal) dari daftar, kemudian melanjutkan dengan sisa daftar, tapi menyelesaikan tugas ini secara efisien dengan menggunakan struktur data yang disebut tumpukan, tipe khusus pohon biner. Setelah daftar data telah dibuat menjadi tumpukan, simpul akar dijamin menjadi unsur (atau terkecil) terbesar. Ketika dipindahkan dan ditempatkan di akhir daftar, tumpukan adalah ulang sehingga elemen terbesar yang tersisa bergerak ke akar. Menggunakan heap, menemukan elemen terbesar berikutnya membutuhkan O (log n) waktu, bukan O (n) untuk linear scan di selection sort sederhana. Hal ini memungkinkan heapsort untuk menjalankan dalam O (n log n) waktu, dan ini juga merupakan kompleksitas kasus terburuk.

- Insertion Sort

Teknik sorting ini dibuat dengan cara menyisipkan atau memasukkan 1 persatu, bila kita akan mengurutkan data, kemudian ingin menyisipkan suatu data maka data tersebut akan otomatis masuk dimana dia berada.

- Quick Sort

Teknik sorting ini dibuat dengan cara yang menggunakan partisi. Pada teknik ini, data dibagi menjadi dua bagian, yaitu data disebelah kiri partisi selalu lebih kecil dari data disebelah kanan. Namun data pada kedua partisi belum terurut, sehingga untuk mengurutkannya, proses pengurutan dilakukan pada kedua partisi secara terpisah. Selanjutnya, data di sebelah kiri dan kanan dipartisi lagi.

- Merge Sort

Teknik sorting ini dibuat dengan cara mengambil keuntungan dari kemudahan penggabungan daftar sudah disortir ke daftar diurutkan baru. Dimulai dengan membandingkan setiap dua elemen (yaitu, 1 dengan 2, kemudian 3 dengan 4 ...) dan swapping mereka jika yang pertama datang setelah kedua. Kemudian masing-masing menggabungkan daftar yang dihasilkan dari dua ke daftar empat, kemudian menggabungkan daftar tersebut empat, dan seterusnya, sampai akhirnya dua daftar digabungkan ke dalam daftar diurutkan akhir.

- Shell Sort

Teknik sorting ini dibuat dengan cara meningkatkan atas bubble sort dan insertion sort dengan menggerakkan keluar dari elemen-elemen memesan lebih dari satu posisi pada suatu waktu. Salah satu implementasi dapat digambarkan sebagai mengatur urutan data dalam array dua dimensi dan kemudian menyortir kolom dari array menggunakan insertion sort.


SEARCHING


Teknik searching merupakan suatu proses pencarian data dari sejumlah data yang ada. Pencarian data dapat dilakukan pada sejumlah data yang sudah terurut atau juga pada data yang sama sekali belum terurut. dalam pencarian data juga terdapat beberapa jenis algoritma, tujuan dari adanya banyak algoritma yang di temukan adalah karena memiliki keuntungan-keuntungan tersendiri, seperti lebih cepatnya bila mengolah data yang jumlahnya lebih dari juta data, ada yang lebih efisien dengan jumlah kurang dari jutaan. serta ada pula yang tidak perlu untuk mengurutkan data terlebih dahulu, tetapi memakan waktu lebih lama.


Ada beberapa jenis teknik searching, sebagai berikut :


1. Line Search

Line Search adalah suatu teknik searching ini dibuat dengan cara melakukan pengecek'an 1 persatu, yaitu antara data yang di cari dengan kumpulan data yang di miliki, Keuntungan metode ini adalah kita tidak perlu mengurutkan data yang ada, bila mencari data pada kumpulan data yang tidak urut hanya terdapat metode ini yang dapat di lakukan.

2. Fibonachi Search

Fibonachi Search yaitu suatu teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data melalui pola bilangan fibonachi. Bila pada binnary search pembandingnya adalah nilai pada index tengahnya jumlah data, pada fibonachi search berbeda yaitu: bilangan fibonachi, yang bilangan fibonachinya terdekat dengan jumlah data tetapi tidak lebih besar dari jumlah data yang akan di proses. Bilangan fibonachi itu di jumlahkan dengan batas paling awal data dikurangi 1. Contohnya: jumlah data yang akan di cari adalah 15, maka batas paling bawah adalah 1 dan batas paling akhir=15 dan index pembandingnya= 13(nilai awal + dijumlahkan Bilangan fibonachi - 1) karena bilangan fibonachi terdekat dengan 15 (data ke 1- data ke 15) adalah 13 (1,2,3,5,8,13,21,34.....), bila data yang di cari lebih besar dari bilangan indeks ke tengahnya maka. batas paling bawah= tetap, batas akhir nilai tengah-1, bila data yang dicari lebih kecil maka batas bawah = nilai tengah +1 dan batas akhir tetap, sedangkan nilai tengahnya memakai fungsi tadi.

3. Sequential Search

Sequential search adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.

4. Binary Search

Binary search merupakan salah satu metode searching, binary search hanya bisa dilakukan pada data yg telah tersort ato terurut karena proses algoritmanya yg terus menerus membagi data menjadi 2 bagian hingga angka / input yg dicari ditemukan.



Sumber:
[1] http://sangadik.blogspot.com/2009/11/teknik-sortingpengurutan-data.html
[2] http://lightluna.wordpress.com/2008/10/24/prinsip-algoritma-pada-teknik-tencarian-search-engine/
[3] http://alpro.awardspace.com/tehnik.html
[4] http://mazterchez.blogspot.com/2010/04/teknik-sorting-dan-searching.html

Tidak ada komentar:

Poskan Komentar