Definisi Pencarian dan Pengurutan Data dalam arti lain ialah pengurutan struktur data agar pencarian lebih mudah dan lebih cepat.
Pengurutan adalah upaya mengatursekumpulan data berdasar pada urutan (naik atau turun). Pencarian adalah upaya mencari/mendapatkan satu atau lebih objek dari sekumpulan data
STRUKTUR DATA.
Sorting Pengurutan data dalam struktur data sangat penting untuk data yang bertipe data numeric ataupun karakter. Pengurutan dapat dilakukan secara ascending(urut naik) dan descending (urut turun),
Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusundengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.
Contoh:
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25
Descending : 25 10 8 6 5 3 1
Macam-macam Sorting
1. Selection Sort (Ascending) adalah Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari idimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1. Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah :
a. Mencari data terkecil dari data pertama sampai data terakhir, kemunian ditukar posisinya dengan data pertama.
b. Mencari data terkecil dari data kedua sampai data terakhir, kemudian di tukar dengan posisinya dengan data kedua.
c. Mencari data terkecil dari data ketiga sampai data terakhir, kemudian di tukar
posisinya dengan data ketiga
d. Dan seterusnya sampai semua data turut naik. apabila terdapat n buah data
yang akan di urutkan, maka membutukan (n - 1) langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu di urutkan karena hanya tinggal satu satunya.
2. Bubble Sort, Konsep Buble Sort Merupakan algoritma pengurutan paling tua dengan metode pengurutan paling sederhana. Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung. Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat contoh kasus bubble sort.
3. Insertion sort Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan.
Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian
diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagianarray yang belum diurutkan.
4. Metode Penggabungan (Merge Sort) Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table sehingga dalam keadaan urut.
5. Quick Sort Algoritma sortir yang efisien yang ditulis oleh C.A.R. Hoare pada 1962. Dasar strateginya adalah “memecah dan menguasai”. Quicksort dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai ini, yang disebut tumpuan (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.
6. Metode Shell (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
7. Radix sort adalah Ide dasar dari metode Radix sort ini adalah mengkategorikan data- data menjadi sub kumpulan subkumpulan data sesuai dengan nilai radix-nya, mengkonkatenasinya, kemudian mengkategorikannya kembali berdasar nilai radix
8. Bucket Sort adalah algoritma sorting yang bekerja dengan partisi array ke dalam jumlah terbatas sort. Setiap kotak ini kemudian diurutkan secara individual, baik menggunakan algoritma sorting yang berbeda, atau dengan rekursif menerapkan algoritma bucket sort. Sebuah variasi dari metode ini disebut semacam hitungan tunggal buffered lebih cepat dari jenis cepat dan membutuhkan waktu sekitar waktu yang sama untuk berjalan pada set data.
9. Heap Sort Merupakan satu bentuk dari selection sort yang memiliki kompleksitas
algoritma O (n log(n) ) yang menggunakan struktur data heap. Heap sort bekerja
dengan menentukan elemen terbesar (atau terkecil) dari sebuah susunan elemen, dan
diletakkan pada akhir (atau awal) dari daftar tersebut. Algoritma:
a. Buat suatu heap.
b. Ambil isi dari root masukkan kedalam sebuah array.
c. Hapus element root dengan mempertahankan properti heap.
d. Ulangi sampai tree menjadi kosong
10. ExchangeSort merupakan metode pengurutan data yang hampir mirip dengan Bubble
Sort ( Mirorr-Nya buble sort), bahkan mungkin juga metode Bubble Sort sama dengan Exchange Sort. 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 atau
sesudahnya, kemudian elemen tersebut itu Untuk setiap proses, akan dilakukan
dengan mencari elemen dari posisi yang belum diurutkan dan kemudian memilih
elemen yang memiliki nilai terkecil atau terbesar yang akan ditukarkan ke posisi yang tepat di dalam array.
Teknik pencarian data dari array yang paling mudah adalah dengan cara sequential search dimana data dalam array dibaca 1 demi satu, diurutkan dari index terkecil ke index yang terbesar,maupun sebaliknya. Teknik selanjutnya adalah binary search. Pada metode pencarian ini data harus diurutkan terlebih dahulu. Pada metode pencarian ini data dibagi menjadi dua bagian (secara logika), untuk setiap tahap pencarian.
Algoritma binary search : pertama data diambil dari posisi 1 sampai posisi akhir N,
kemudian cari posisi data tengah dengan rumus : (posisi 1+ posisi akhir)/2. Kemudian data yang dicari di bandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar. Jika lebih besar maka proses pencarian dicari dengan posisi awal adalah posisi tenganh +1, jika lebih kecil posisi tengah -1. Jika data sama berarti ketemu.
Interpolation search adalah metode pencarian mirip binary search data harus di urutkan
terlebih dahulu. Metode ini menebak letak data yang dicari, dengan perhitungan. Jika
data[posisi]>data yang dicari, high=pos-1. Jika data[posisi]<data yang dicari,low=pos+1.
Algoritma pencarian merupakan langkah-langkah dalam suatu proses pencarian data tertentu dalam sekumpulan data yang mempunyai tipe yang sama. Algoritma pencarian dengan data yang dicari lebih dari satu, maka pencarian selesai bila salah satu data sudah ditemukan.
Algoritma pencarian linier adalah proses pencarian dengan membandingkan atau mencari data satu persatu secara linier. Algoritma pencarian linier tidak bagus untuk volume data yang besar.
