Sorting & Searching

Sorting

Sorting adalah proses yang mengatur sekumpulan data sehingga nilainya itu dapat tersusun secara runtut. Sorting ada 2 yaitu : sorting naik(ascending) dan sorting turun (descending).

Sorting di dalam Algortima ada 2 yaitu :

1. Internal Sorting 

semua data yang ada diurutkan dan kemudian disimpan di dalam RAM

2. External Sorting 

Sorting menggunakan memori lain atau memori kedua

Sorting(simple) dibagi menjadi beberapa macam yaitu : Bubble Sort , Selection Sort , dan Insertion Sort.

Sorting (Intermediate) dibagi menjadi beberapa macam yaitu: Quick Sort , Merge Sort

Bubble Sort: membanding 2 nilai , jika terpenuhi syarat maka akan diswap(ditukar posisi)

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 : Membanding 2 jenis data , kemudian data jenis yang pertama digunakan sebagai acuan untuk membandingkan data berikutnya.

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 : Membandingkan 2 jenis data , kemudian data yang dianggap lebih kecil disimpan terlebih dahulu dalam temporary , kemudian data yang lebih besar diletakan di depan data yang lebih kecil.

for(i=1; i<n; i++) {

     x = A[i], insert x to its suitable place between A[0] and A[i-1].

}

Quick Sort: Algoritma pengurutan yang dapat dilakukan sangat cepat dengan tipe penyelesaian divide dan conquer , dapat digunakan untuk mengurutkan data dalam jumlah besar.

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 :  dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali.

Searching

Pencarian adalah tindakan untuk mengambil informasi berdasarkan kunci tertentu dari beberapa informasi yang disimpan.Kunci digunakan untuk melakukan pencarian rekaman yang diinginkan dari satu set daftar data. Kunci harus unik, artinya tidak boleh ada kunci yang sama dalam data(agar terhindar dari ambiguitas nama data)

searching dibagi menjadi 3 yaitu :
1. Linear Search : Membandingkan setiap elemen array dengan kata kunci pencarian.
contoh Linear Search

n : total record of array x.

 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.

2. Binary Search : Metode pencarian Binary digunakan untuk mencari Array besar karena lebih cepat dan efektif dibandingkan linear search

n : total record of array x.

 left=0,  right= n-1.

 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.

3. Interpolation Search: Teknik pencarian ini dilakukan pada data yang telah diurutkan , teknik ini dilakukan dengan perkiraan lokasi data.

Formula interpolation search :

kunci - data [min]/data[max]-data[min].(max-min)+min