2201744941
LP01
Pada tanggal 12 Desember 2018 saya mempelajari tentang Sorting & Searching
Tipe sorting:
-ascending
-descending
contoh-contoh sorting:
-bubble sort
-selection sort
-insertion sort
-quick sort
-merge sort
code 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]);
}
code selection sort:
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 ]
}
code insertion sort:
for(i=1;
i<n; i++) {
x =
A[i], insert x to its suitable place between A[0] and A[i-1].
}
code 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 adalah sebuah algortima sorting berdasarkan algoritma divide-and-conquer
Searching adalah aksi untuk mendapatkan informasi berdasarkan kunci tertentu dari informasi yang disimpan
tipe-tipe algoritma searching:
-linear search
-binary search
-interpolation search
code linear search:
1. n :
total record of array x.
2. For each x[i],
0 £ i £ n-1,
check
whether
x[i] = key.
3. If x[i]
= key,
then the searched data is found in index=i.
Finished.
4. If x[i]
¹
key,
then continue searching until the last data which is i
= n-1.
5. If
i=
n-1 and x[i] ¹
key, it
means the data is not exist in the list, and set
index = -1.
Finished.code binary search:
1. n
: total record of array
x.
2.
left=0, right= n-1.
3. mid
=(int)
(left + right)/2.
4. If
x[mid]=key
then index
= mid.
Finished.
5. If
x[mid]<key
then left
= mid+1.
6. If
x[mid]>key
then right
=
mid-1.
7. If
left
£
right and x[mid] ¹
key,
then repeat point 3.
8. If
x[mid]
¹
key then index
= -1.
Finished.
code interpolation search:
1.In
the interpolation search, we'll split the data according to the following
formula:
●
2.If data[mid]
= sought
data,
data has
been found, searching
is stopped and return mid.
3.If data[mid]!=
sought data, repeat
point **
4.**Searching
is continued while sought data
> data[min] and sought
data
< data[max].
5.Looking
for a mid value by entering into the interpolation formula
6.If
data[mid]
> sought data, high = mid – 1
7.If
data[mid]
< sought data, low = mid + 1
8.It
will be looped until the requirements point ** are not met then return
(-1),
data not found
