Sorting and Searching


Sorting and Searching
Sorting : needs to speed up searching operation in a list
Type :
      1.)    Ascending
      2.)    Descending
Sorting Algorithm :
          1.      Internal sorting
     All data to be sorted are loaded to RAM
           2.      External Sorting
Sorting process using secondary storage (HDD)
Kind of sorting :
-        Bubble Sort
Compare two neighboring values.
Compare and swap (if necessary)
Also known as exchange 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]);
}
Source code of bubble 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 ]
    }  
Selection Sort



















-       
         Algorithm:
         for(i=1; i<n; i++) {
         x = A[i], insert x to its suitable place between A[0] and A[i-1].
        }
Insertion Sort









         


          Quick Sort (intermediate)
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 (intermediate) : is a sorting algorithm based on the divide-and-conquer algorithm.
o   Divide-and-conquer is a general-algorithm design paradigm
§  Divide : divide the input data in two disjoint subset
§  Recur : solve the sub problems associated with subsets
§  Conquer : combine the solutions for each subset into a solution

Searching : mau mencari key dimana harus unique.
Types :
-        Linear Search
o  
•        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

•        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.

Efficient for large arrays, if the array sorted, the high – speed binary search technique can be used.
    

-        
    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].
 


                                                                                                                                           

Compare each element of the array with the search key, since the array is not any particular order, it’s just as likely that the value will be found in the first element as in the last.
On average, therefore, the program will have to compare the search key with half the elements of the array.

















Komentar

Posting Komentar