Sorting dan Searching

Sorting dan Searching

Sorting adalah pengurutan data yang terdiri dari 2 jenis:
1.Ascending(dari kecil ke besar)
2.Descending(dari besar ke kecil)

Ada 5 metode dalam melakukan Sorting:

1.Bubble Sort 
adalah pengurutan data dengan membandingkan 2 data dan menukarnya jika data      memenuhi dan lanjut ke data berikutnya secara terus menerus sampai data sudah terurut.
 
Algoritma:
   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]);

    }

2.Selection Sort

adalah metode pengurutan data dengan mencari elemen-elemen yang belum terurut terkecil(Ascending)  dan yang terbesar (Dsecending) dan ditukarkan posisinya tepat di dalam array.

 7    5    1    9    2    6    4  

  1    5    7    9    2    6    4

  1    2    7    9    5    6    4

  1    2    4    9    5    6    7

  1    2    4    5    9    6    7

  1    2    4    5    6    9    7

  1    2    4    5    6    7    9 

  1    2    4    5    6    7    9    

Algoritma:

     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 ]

     }
3. Insertion Sort
 adalah  sebuah metode pengurutan data dengan menempatkan setiap elemen data pada
 posisinya dengan cara melakukan perbandingan dengan data – data yang ada.

  2    3    9    6    4    5    1

  2    3    9    6    4    5    1

  2    3    9    6    4    5    1

  2    3    6    9    4    5    1

  2    3    4    6    9    5    1

  2    3    4    5    6    9    1

  1    2    3    4    5    6    9  

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

4. Quick Sort
adalah algoritma pengurutan yang sangat cepat dengan tipe penyelesaian divide and
conquer. sehingga cocok untuk mengurutkan data dalam jumlah besar.

algoritma:

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);

       }

}

          
5. Merge Sort 
   adalah proses pengurutan data secara divide dan conquer dan rekursif.
   divide = membagi inputan menjadi 2 bagian
   rekur  = menyelesaikan masalah bagian-bagian
   conquer = menggabungkan masalah- masalah yang diselesaikan menjadi satu data yang               sudah terurut.

Searching adalah proses mencari suatu nilai elemen dalam array dengan menggunakan
key value.
Searching terdiri dari 3 metode:
1.Linear Search
2.Binary Search
3.Interpolation Search

1.Linear Search
membandingkan setiap element dalam array dengan search key.
algoritma :
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 
pencarian nilai key data element dalam array dan data harus diurutkan terlebih dahulu. 
algoritma:
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.Interpolar Search
proses ini hampir mirip dengan binary search, data harus diurutkan terlebih dahulu .
Metode ini dilakukan dengan perkiraan lokasi dari data.

algoritma:
1.In the interpolation search, we'll split the data according to the following formula:
   mid=kunci-data[min]/data[max]-data[min] *(max-min) +min
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