Sorting and Searching

Algorithm and Programming class
Session 29
December 12, 2018

#Sorting and Searching

~Sorting

Sorting diperlukan untuk mempermudah proses pencarian.
Tipe-tipe sorting:
  • Ascending
  • Descending

+Bubble Sort

Bubble Sort akan membandingkan ataupun menukar dua nilai yang bersebelahan.
Source kode 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

Algorithm:
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

Algorithm:
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 adalah sorting berdasarkan algorithm divide and conquer.

#Searching

Searching adalah proses pencarian elemen array tertentu.

+Linear Search

Linear search membandingkan setiap elemen array dengan search key.
•Algorithm:
   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.

+Binary Search

Binary search bagus untuk array yang kecil atau yang belum tersort.
•Algorithm:
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.

+Interpolation Search

•Algorithm:
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

Sekian rangkuman untuk materi yang saya dapatkan pada sesi 29 kelas Algorithm and
Programming tanggal 12 Desember 2018, atas perhatiannya terima kasih.


Greecelia Wongsi
2201758253
CB01-CL/LR01-LEC
skyconnectiva.com


Comments

Post a Comment