Sorting & Searching
hello gais, pada kesempatan kali ini saya akan menjelaskan kepada kalian materi algoritma tentang sorting dan searching.
1.Sorting
sorting/mengurutukan memiliki beberapa jenis:
simple:
- Bubble Sort
- Selection Sort
- Insertion Sort
intermediate:
-Quick Sort
-Merge Sort
sorting juga memiliki 2 tipe yaitu:
- Ascending = mengurutkan dari nilai yang terkecil hingga terbesar.
- Descending = mengurutkan dari nilai yang terbesar hingga terkecil.
sorting menurut caranya dapat dibagi menjadi 2 cara:
1. Internal sorting
-semua data yang akan disorting disimpan kedalam RAM.
2. External sorting
-proses sorting menggunakan storage kedua(HDDs/SSDs).
Bubble Sort
Bubble sort memiliki ciri-ciri sebagai berikut:
- membandingkan nilai terdekat atau yang ada disebelahnya.
- membandingkan dan menukan(jika diperlukan).
- dapat disebut juga sebagai exchange sort.
contoh algoritma bubble sort:
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
selection sort = mencari nilai yang terkecil terlebih dahulu kemudian memindahkannya ke depan/paling awal dalam kumpulan suatu data.
contoh algoritma selection sort:
for(i=0;
i<N-1;
i++){
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
insertion sort = menggunakan parameter pembanding untuk mengurutkan suatu data.
contoh algoritma insertion sort:
for(i=1;
i<n; i++) {
x =
A[i], insert x to its suitable place between A[0] and A[i-1].
}
Quick Sort
quick sort = menggunakan strategi pemecahan data menjadi pratisi-pratisi. karena dapat mengurutkan data dengan sangat cepat metode ini dapat disebut quick sort/pratition exchange sort.
contoh algoritma quick sort:
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
merge sort = menggunakan strategi divide-and-conquer atau dapat dibilang merge sort ini membagi data menjadi beberapa kelompok lalu menyorting masing masing kelompok dan menggabungkan kelompok itu kembali untuk di sorting.
2.Searching
Searching adalah sebuat tindakan untuk mencari informasi berdasarkan suatu kunci dari sebuah informasi yang tersimpan.
Searching memiliki 3 jenis yaitu :
-Linear Search
-Binary Search
-Interpolation Search
Linear Search
linear search akan membandingkan setiap element di dalam array dengan search key.
selama array tidak terurut, kemungkinan nilai akan dapat ditemukan dielemen pertama seperti atau terakhir, oleh karena itu, program harus membandingkan kunci pencarian dengan setengah elemen dari array.
metode linear search dapat bekerja dengan baik jika terdapat array yang kecil atau kumpulan data yang tidak tersorting.
Binary Search
binary search atau dapat disebut juga half-intercal-search bekerja dengan baik apabila terdapat array yang sudah terurut. Pencarian ini bekerja dengan cara membandingkan nilai target ke elemen tengah dari array. jika mereka tidak sama, maka setengah array tersebut dihilangkan dan pencarian berlanjut pada setengah sisanya. cara tersebut terus diulangi sampai nilai target ditemukan.
Interpolation Search
interpolation search juga dapat bekerja dengan baik didalam data yang sudah tersorting. metode ini hampir sama dengan metode binary search. metode ini dapat diibaratkan seperti kita ingin mencari suatu kata didalam sebuah kamus.
oke mungkin sampai disini dulu informasi yang dapat saya berikan seputar tentang sorting dan searching, semoga bermanfaat untuk kalian semua. Terima kasih.
