Sorting dan Searching

Sorting dan Searching

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