Sorting dan Searching

Sorting

Tipe-tipe sorting :

1. Ascending, yaitu mengurutkan dari nilai terkecil ke nilai terbesar
2. Descending, yaitu mengurutkan dari nilai terbesar ke nilai terkecil

Simple Sort:

1. Bubble Sort
2. Selection Sort
3. Insertion Sort

Intermediate Sort :

1. Quick Sort
2. Merge Sort

Bubble Sort

Membandingkan 2 nilai dengan sebelahnya.

Algorithm:

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

Algorithm :

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 algoritma yang menggunakan divide-and-conquer algoritma.

Divide yang artinya membagi input data menjadi 2 disjoint subsets

Conquer yang artinya menggabungkan solusi dari setiap subset

Searching

Searching suatu data pada sekumpulan data merupakan proses yang sangat penting. Proses pencarian 

dilakukan untuk mengetahui apakah data yang dicari terdapat pada sekumpulan data yang ada.

Jenis Searching :

1. Sequential / Linear Search

2. Binary Search

Linear/Sequential Search

Linear search dapat dilakukan pada data yang belum teruturu mau pun sudah terurut. Pencarian

dilakukan dengan melakukan penelusuran data satu-persatu kemudian dicocokan dengan data yang 

dicari.

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

Pencarian biner, hanya dapat dilakukan pada data yang sudah terurut. Bila data belum terurut dan 

akan dilakukan pencarian menggunakan metode ini, maka terlebih dahulu harus diurutkan.

Untuk data yang besar metode ini lebih efektif dibandingkan Linear Search

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.

Sekian dan terimakasih. Semoga dapat membantu teman-teman :).

Moses Stefano Christofel
moses.christofel@binus.ac.id
skyconnectiva.com
2201754766