Sorting
adalah fungsi dalam kode untuk mengurutkan suatu bilangan.
Ada 2 tipe yaitu ascending dan descending
Simple sorting:
- Bubble sort
- Selection sort
- Insertion sort
Intermediate:
- Quick sort
- Merge sort
Bubble sort
Mengurutkan suatu data dengan cara mengecekan suatu bilangan dari awal atau akhir dan menempatkannya di tempat 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
Mengurutkan suatu data dengan cara mencari data yang terkecil atau terbesar dan memindahaknnya ketempat seharusnya.
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
for(i=1;
i<n; i++) {
x =
A[i], insert x to its suitable place between A[0] and A[i-1].
}
Quick sort
Mengurutkan suatu data dengan cara menentukan pivot dan mengurutkannya
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
Mengurutkan suatu data dengan cara membagi bagi data
Searching
Seaeching adalah kode yang digunakan untuk mencari suatu data dalam kode.
Tipe tipe:
- Linear search
- Binary search
- Interpolation search
Linear search
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
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
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 then return
(-1),
data not found
