Sorting

Simple:

• Bubble Sort
• Selection Sort
• Insertion Sort

Intermediate

• Quick Sort
• Merge Sort

1. Bubble Sort

•Compare two neighboring values.

•Compare and swap (if necessary)

•Also known as exchange sort

•Source Code of Bubble 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]);

}

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

}

3. Insertion Sort

Algorithm:

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

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

       }

}

5. Merge Sort

• Merge sort adalah algoritma penyortiran yang berdasarkan algoritma divide-and-conquer
• Divide-and-conquer adalah paradigma desain algoritma umum

–Divide: membagi data input dalam dua susbet yang menguraikan.

–Recur: menyelesaikan sub problem yang terkait dengan himpunan bagian

–Conquer: gabungkan solusi untuk setiap bagian menjadi solusi

6. Linear Search

-Linear Search membandingkan setiap elemen dari array dengan kunci pencarian

-Karena array tidak dalam urutan tertentu, kemungkinan besar nilainya akan ditemukan di elemen pertama seperti yang terakhir.

-Oleh karena itu, rata-rata, program harus membandingkan kunci pencarian dengan setengah elemen dari array.

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

7. Binary Search

-Metode Linear Search berfungsi baik untuk linear kecil atau yang tidak disortir.Namun untuk pencarian linear array besar tidak efisien.

-Jika array diurutkan, teknik binary search berkecepatan tinggi dapat digunakan.

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

8. Interpolation Search

-Teknik Interpolation Search dilakukan pada data yang telah tersortir.

-Proses pencarian ini hampir mirip dengan teknik binary search

-Teknik pencarian dilakukan dengan perkiraan lokasi data.