Sorting & Searching

Ruben Marton Rezer
2201744941
LP01

Pada tanggal 12 Desember 2018 saya mempelajari tentang Sorting & Searching

Tipe sorting:
-ascending
-descending

contoh-contoh sorting:
-bubble sort
-selection sort
-insertion sort
-quick sort
-merge sort

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

}

code selection sort:

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 ]

}

code insertion sort:

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

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

}

code quick sort:

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 adalah sebuah algortima sorting berdasarkan algoritma divide-and-conquer

Searching adalah aksi untuk mendapatkan informasi berdasarkan kunci tertentu dari informasi yang disimpan

tipe-tipe algoritma searching:
-linear search
-binary search
-interpolation search

code linear search:

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.

code binary search:

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.

code interpolation search:

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

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