Sorting and Searching

A.      Sorting

Seperti yang sudah kita ketahui bahwa Sorting adalah proses pengaturan suatu objek atau data sesuai dengan aturan dan urutan yang ditentukan. Sorting dapat dikelompokan menjadi 2 yaitu:

-  Ascending ( dari terkecil hingga terbesar )

- Decending ( dari terbesar hingga terkecil )

Dalam pemrograman sorting juga digunakan untuk mengurutkan sebuah data-data yang tersedia secara acak, agar di urutkan sesuai dengan urutannya melalui huruf maupun angka. Berikut metode sorting yang digunakan dalam pemrograman:

·       Simple Method

o   Bubble sort

o   Selection Sort

o   Insertion Sort

·       Indermediate Method

o   Quick Sort

o   Merge Sort

Sesuai dengan method diatas dapat diartikan bahwa semakin sulit method yang digunakan, semakin sulit juga algoritma yang digunakan tetapi waktu yang digunakan untuk menyortir akan lebih singkat atau cepat.

v Bubble Sort

Metode Bubble Sort adalah membandingkan 2 nilai yang berdekatan dan menukar kedua nilai tersebut hingga semua nilai dalam data tersebut sesuai dengan urutannya.

Sorce code:

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

}

v Selection Sort

Selection sort adalah memilih nilai maksimum atau minimum kemudian menukar nilai maksimum-minimum tersebut dengan nilai terujung kiri atau kanan.

Sorce code:

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

}

v Insertion Sort

Insertion Sort adalah pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada.

Source Code:

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

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

}

v Quick Sort

Quick Sort adalah pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi

Source Code:

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

       }

}

v Merge Sort

Merge Sort adalah dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali.

B.     Searching

Searching adalah metode pencariankata kunci dalam suatu data yang tersedia, Pencarian diperlukan untuk mencari kata kunci dari data di lokasi yang pasti dari data tersebut yang sebelumnya tidak diketahui. Metode searching dapat dibagi menjadi 3 yaitu:

-        Linear Search

-        Binary Search

-        Interpolation search

v Linear Search

Linear Serach adalah searching yang dilakukan secara teratur (secara sekuensial) dari awal sampai akhir data (atau bisa juga dari akhir ke awal data).

v Binary Search

Binary Search adalah metode pencarian suatu data atau elemen di dalam suatu array dengan kondisi data dalam keadaan terurut.

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

v Interpolation Search

Interpolation Search adalah metode searching untuk mencari nilai key yang diberikan dalam array diindeks yang telah diperintahkan oleh nilai – nilai kunci.

Rumus dan algoritma yang terdapat pada metode ini adalah

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