loha, balik lagi sama abang TS. Di kelas kemarin kami diajarkan tentang sorting dan searching. Nyok disimak…

Sorting
– Sorting adalah metode pengurutan data yang memudahkan kita dalam pekerjaan.
– Tipe-tipe sorting
1. Simple
a. Bubble sort :
- Adalah pengurutan data dengan membandingkan data di sebelahnya sampai ampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Bisa mengurutkan data dari yang terbesar ke yang terkecil atau sebaliknya (Ascending atau Descending).
- Syntax :
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]);
b. Selection sort :
- Adalah pengurutan data dengan membandingkan indeks yang ada dan data ditukar menurut indeks yang ada. Menggunakan temp sebagai tempat menyimpan data terkecil.
- Syntax :
for(i=0; i<=N-2; i++){ /* N=number of data */
for(j=i; j<=N-1; j++){
Note the index of smallest value between A[j] s/d A[N-1],
Save it in variable k.
Swap A[i] with A[k].
}
}
c. Insertion sort :
- Adalah pengurutan data dengan metode penyisipan dan membandingkan data, namun dalam putaran pengurutan tidak menentukan nilai terkecilnya.
- Syntax :
void Insertion(int *Arr, int n){
int i, k, y;
for(k=1; k < n; k++) {
y = Arr[k];
for(i=k-1; i >= 0 && y < Arr[i]; i–)
Arr[i+1] = Arr[i];
Arr[i+1] = y;
}
}
2. Intermediate
a. Quick sort :
- Adalah pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort.
- Metode cukup sulit bagi amatiran, namun efektif dalam pekerjaannya.
- Syntax :
void QuickSort(int L,int R) {
int j,k;
if(L < R){
j = L; k = R + 1;
do{
do{ j=j+1;} while(Arr[j] < Arr[L]);
do{ k=k-1;} while(Arr[k] > Arr[L]);
if(j < k) Swap(&Arr[j],&Arr[k]);
}while(j <= k);
Swap(&Arr[L],&Arr[k]);
QuickSort(L,k-1);
QuickSort(k+1,R);
}
}
b. Merge sort :
- Adalah pengurutan data dengan membaginya menjadi beberapa bagian, baru digabungkan kembali dengan pengsortiran.
Searching
– Dapat digunakan lebih efektif saat data sudah disortir dengan metode diatas.
– Berfungsi untuk mencari data yang ingin digunakan para pengguna/pekerja.
– Memakai kata kunci.
– Jenis searching :
1. Linear Search :
- Memakai teknik barbar.
- Pemakaian metode ini tak efektif untuk data besar.
- Algoritma :
- 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 setindex = -1.
- Finished.
int linearSearch(const int array[], int key, int size) {
int n; /* counter */
/* loop through array */
for (n=0; n<size; ++n){
if (array[n] == key){
return n; /* return location of key */
}
}
return -1; /* key not found */
}
2. Binary search :
- Efektif penggunannya dalam data kecil dan belum disortir.
- Algoritma :
- 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.
int binarySearch(const int b[], int searchKey, int low, int high)
{
int middle; /* variable to hold middle element of Array */
/* loop until low subscript is greater than high subscript*/
while (low <= high){
middle = ( low + high ) / 2
printRow (b, low, middle, high)
if (searchKey < b[middle]) high = middle -1;
else if (searchKey > b[middle]) return middle;
else low = middle + 1;
}
return -1; /* searchKey not found */
}
3. Interpolation search :
- Efektif jika data sudah disortir dan lokasi pencarian data mendetail.
- Algoritma :
- In the interpolation search, we’ll split the data according to the following formula:
- If data[mid] = sought data, data has been found, searching is stopped and return mid.
- If data[mid]!= sought data, repeat point ** (**Searching is continued while sought data > data[min] and sought data < data[max].)
- 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 thenreturn (-1), data not found
int InterpolationSearch(int x[], int key, int n) {
int mid, min = 0, max = n-1;
while(x[min] < key && x[max] > key) {
mid = min + ((key-x[min])*(max-min)) / (x[max]-x[min]);
if(x[mid] < key)
min = mid + 1;
else if(x[mid] > key)
max = mid – 1;
else return mid;
}
if (x[min] == key) return min;
else if(x[max] == key) return max;
return -1; // data not found
}
TERIMA KASIH…