searching dan sorting adalah komponen dalam pemograman yang sangat dibutuhkan. didalam suatu perusahaan atau aplikasi, data yang ada didalamnya itu sangatlah banyak.nah disinilah peran dari searching dan sorting untuk membantu mencari data dan mengatur data.
Searching dari namanya sendiri mempunyai arti (mencari), mempunyai fungsi untuk mencari suatu data didalam sebuah coding atau storage.
ada 3 tipe searching :
1. linear search
2. Binary search
3. Interpolation search
Linear search adalah program searching yang paling mudah dipahami dan paling sederhana. kelebihan dari linear search ini adalah apabila data-data yang diinginkan berada diawal sehingga prosesnya berlangsung cepat. tetapi apabila data yang diinginkan berada diakhir, prosesnya berlangsung lama.
n : total record of array
x.
For each x[i], 0 £ i £ n-1, check whether x[i] = key.
If x[i] = key,
then the searched data is found in index=i. Finished.
If x[i] ¹ key, then continue
searching until the last data which is i = n-1.
If i= n-1
and x[i] ¹ key, it means the data is not exist in the list, and set index
= -1. Finished
Binary search adalah program searching yang dapat digunakan jika data yang ingin dicari sudah berurutan(dapat dilakukan sorting sebelum menggunakan binary search). kelebihannya itu binary search hanya membutuhkan proses yang relatif cepat. kekurangannya, binary search lebih rumit dan tidak semudah linear search untuk memahaminya
n : total record of array x.
left=0, right= n-1.
mid =(int) (left + right)/2.
If x[mid]=key then index = mid. Finished.
If x[mid]<key then left = mid+1.
If x[mid]>key then right = mid-1.
If left £ right and x[mid] ¹ key, then repeat point 3.
If x[mid] ¹ key then index = -1. Finished.
interpolation search program searching untuk mencari nilai key yang ada dalam array diindeks yang diperintahkan oleh nilai-nilai kunci. tipe searching ini didasari dari cara mencari nomor telepon pada buku telepon.
Looking for a mid
value by entering into the interpolation formula
If data[mid] > sought data,
high = mid – 1
If data[mid] < sought data,
low = mid + 1
It will be looped
until the requirements point ** are not met then return (-1), data not found
Sorting
sorting adalah salah satu bagian program yang berfungsi untuk mengurutkan data sesuai dengan apa yang diinginkan(ascending atau descending).
sorting dibagi 2 :
1. simple
2. advance
simple sendiri ada 3 jenis caranya :
1. bubble sort
2. selection sort
3. insertion sort
bubble sort
merupakan cara sorting yang paling mudah, yaitu dengan mengurutkan data-data dengan melakukan pengecekan terhadap setiap data dari awal ke paling akhir yang kemudian menempatkan data ditempat yang tepat.
void Bubble(int
*DataArr, int n)
{
int i, j;
for(i=1; i<n; i++)
for(j=n-1; j>=i; j--)
if(DataArr[j-1] > DataArr[j])
Swap(&DataArr[j-1],&DataArr[j]);
}
Selection sort
merupakan cara sorting dengan mengurutkan data melalui proses pencarian data terbesar dan terkecil baru kemudian memindahkan ketempat yang tepat.
for(i=0; i<N-1; i++){ /* N=number of
data */
Set idx_smallest equal to i
for(j=i+1; j<N; j++){
If array[ j ] <
array [ idx_smallest ] then idx_smallest = j
}
Swap array[ i ] with array[ idx_smallest ]
}
Insertion sort
merupakan cara sorting dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. cara ini bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.
for(i=1; i<n; i++) {
x = A[i], insert x to its
suitable place between A[0] and A[i-1].
}
Advance ada 3 cara :
1. Quick sort
2. Merge sort
Quick Sort
merupakan cara sorting dengan menjadikan salah satu data sebagai patokan atau pivot. setelah
menentukan pivot baru mulai mengurutkan data.
void QuickSort(int left,
int right)
{
if(left < right){
//arrange elements R[left],...,R[right] that
//producing new sequence:
R[left],...,R[J-1] < R[J] and
R[J+1],...,R[right] > R[J].
QuickSort(left, J-1);
QuickSort(J+1, right);
}
}
Merge Sort
merupakan cara sorting dengan cara membagi data menjadi beberapa kelompok, kemudian didalam
kelompok itu diurutkan (ascending atau descending) lalu di gabung dengan kelompok lain dan
diurutkan, hal ini diulang sampai semua kelompok-kelompok kecil itu menjadi satu kelompok.
sekian dari saya tentang searching dan sorting, bila ada kekurangan atau kesalahan dapat dibantu dengan menulis dikolom komentar
semoga bermanfaat
