Sorting and Searching

Sorting and Searching

Sorting

Sorting pada program adalah suatu fungsi yang akan merapikan atau menata sebuah value yang dari terkecil ke terbesar atau sebaliknya

·       Tipe Sorting

1.       Ascending

Mengurutkan dari value terkecil ke terbesar.

2.        Descanting

Mengurutkan dari value terbesar ke terkecil.

·       Sorting algorithm

1.       Internal sorting

Semua data doi sorting didalam RAM

2.       External sorting

Sorting menggunakan secondary storage seperti harddisk

·       Tipe Tipe Sorting

·       Bubble sort

Membandjngkan data yang ada disebelahnya dengan cara kerja membandingkan lalu tukar

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

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

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

void merging(int low, int mid, int high) {

   int l1, l2, i;

   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {

      if(a[l1] <= a[l2])

         b[i] = a[l1++];

      else

         b[i] = a[l2++];

   }

   while(l1 <= mid)   

      b[i++] = a[l1++];

   while(l2 <= high)  

      b[i++] = a[l2++];

   for(i = low; i <= high; i++)

      a[i] = b[i];

}

Searching

Searching pada program adalah melakukan pencarian suatu value yang dinginkan.

·       Tipe tipe searching

1.       Linear search

Linear search membandingkan tiap 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.

2.       Binary search

Melakukan search dengan cara mengambil value tengah dan akan melihat ada dibagian kiri atau kanan. (Hanya dapat digunakan jika data sudah di “sort”.

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.

3.       Interpolation search

Hampir sama seperti binary search tetapi jika binary cari dalam semua data sedangkan Interpolation search mencari pada lokasi yang diinginkan missal mencari nama Tjo ia akan ke lokasi ber value T dan tidak pada Z atau nilai tengah.

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