SORTING & SEARCHING

SORTING

Dalam pemrograman, sorting ada banyak cara.  Akan tetapi, kali ini saya akan menunjukkan 5 jenis sorting saja yang cukup banyak dikenal.
Dari sorting-sorting ini, ada yang caranya basic dan advance.
Basic :
- Bubble sort
- Insertion sort
- Selection sort
Advance :
- Quick sort
- Merge sort

BUBBLE SORT

Caranya sangat mudah, kita hanya perlu membandingkan tiap 2 angka secara berurutan mana yang paling besar kemudian kita meletakkan diujung.

Cara tersebut diulangin sampai semuanya diletakkan dan tidak ada yg diswap lagi

Untuk jumlah pengulangan jika ada 5 angka yang akan diurutkan maka jumlah yang diulang adalah sebanyak 5 - 1 = 4 kali pengulangan.

void bubbleSort(int *arr, int n){

    int i,j;

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

    for(j = n-1; j >= i; j--)

    if(arr[j-1] > arr[j])

       swap(&arr[j-1],&arr[j]);

}

INSERTION SORT

Caranya seperti bubble, hanya saja ini versi augmentednya.
Ketika membandingkan dua angka, jika angka tersebut ternyata harus di tukar maka dia akan mengecek angka disebelahnya. Terus sampai tidak ada yang perlu diswap atau sudah sampai ujung

void insertionSort(int *arr, int n){

   int i,j,temp;

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

       temp = arr[i];

       j = i-1;

       while (j >= 0 && arr[j] > key){

           arr[j+1] = arr[j];

           j = j-1;

       }

       arr[j+1] = temp;

   }

}  

SELECTION

Caranya mirip juga dengan bubble, hanya saja hal pertama yang dilakukan adalah menyeleksi angka yang paling kecil. Angka yang paling kecil itu kemudian ditukar dengan yang paling kiri dan dikunci.
Kemudian lanjut lagi mencari bilangan terkecil kedua, disusun di sebelah kiri di sebelah bilangan yang dikunci.
Proses tersebut seterusnya dilakukan sampai semua angka telah dikunci

void selectionSort(int *arr, int n){

    int i,j,idxMin;

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

        idxMin = i;

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

          if (arr[j]<arr[idxMin])

            idxMin = j;

}

        swap(&arr[idxMin], &arr[i]);

    }

}







QUICK SORT




Sorting ini merupakan salah satu jenis sorting advance
Untuk menerapkannya membutuhkan rekursi.

Pada sorting ini, dipilih salah satu nomor yang akan
berperan sebagai pivot. (biasanya data yang di tengah)

Semua nilai yang lebih besar dari pivot di geser kanan
Semua nilai yang lebih kecil dari pivot di geser kekiri

Kemudian lakukan hal yang sama pada kumpulan nilai
yang ada di kiri dan yang ada di kanan.

Lakukan terus sampai semuanya terurut.

void quickSort(int *arr, int left, int right) {

      int i = left, j = right;

      int temp;

      int pivot = arr[(left + right) / 2]; //diambil data tengahnya

      while (i <= j){

            while (arr[i] < pivot)

               i++;

            while (arr[j] > pivot)

               j--;

            if (i <= j) {

               temp = arr[i];

               arr[i] = arr[j];

               arr[j] = temp;

               i++;

               j--;

            }

      }

      if (left < j)

         quickSort(arr, left, j);

      if (i < right)

         quickSort(arr, i, right);

}

MERGE SORT

Sorting ini sama saja seperti quick sort, sama-sama
memecahkan masalah kecil dulu dengan rekursif.

Jadi kumpulan data dipecah dulu menjadi satu-satu
kemudian tiap 2 data lakukan sorting.

Ketika 2-2 data terurut kemudian gabungkan
menjadi 4 data.

Lakukan sorting pada 4 data tersebut kemudian
setelah selesai, gabungkan lagi menjadi 8 data

Seterusnya dilakukan sampai semua data terurut

void merge(int *arr, int start, int mid, int end) {
 int temp[end - start + 1];
 int i = start, j = mid+1, k = 0;
 while(i <= mid && j <= end) {
  if(arr[i] <= arr[j]) {
             temp[k] = arr[i];
      k += 1; i += 1;
  }
  else {
             temp[k] = arr[j];
      k += 1; j += 1;
  }
 }
 while(i <= mid) {
            temp[k] = arr[i];
     k += 1; i += 1;
 }
 while(j <= end) {
     temp[k] = arr[j];
     k += 1; j += 1;
 }
 for(i = start; i <= end; i += 1) {
     arr[i] = temp[i - start]
 }
}
void mergeSort(int *arr, int start, int end) {
 if(start < end) {
  int mid = (start + end) / 2;
  mergeSort(arr, start, mid);
  mergeSort(arr, mid+1, end);
  merge(arr, start, mid, end);
 }
}

SEARCHING

Searching ada banyak cara, tapi yang saya akan jelaskan disini hanya 3 cara yaitu:
- Linear search
- Binary search
- Interpolar

LINEAR SEARCH
Pada search jenis ini, sangat simple dipahami hanya saja caranya sangat berguna jika yang dicari datanya berdekatan dengan yang paling pojok.
Misalnya, kumpulan data : 1 2 3 4 5 6 7 8 9 ... 143730292103418
Kemudian yang dicari adalah angka 3
Maka pilihan yang paling efektif adalah linear search
Pada dasarnya linear search mencari satu satu berurutan mulai dari paling kiri/kanan secara searah

BINARY SEARCH
Pada search jenis ini, kita wajib mensorting data kita kemudian kita mencari 3 poin penting dari kumpulan data itu yaitu nilai paling kecil, paling besar, dan nilai tengah.
Kemudian kita menentukan apakah data yang ingin kita cari ada di range nilai data yang kecil - tengah atau tengah-besar.
Ketika kita sudah tahu ada dimana kemudian di range itu kita melakukan hal yang sama yaitu menentukan nilai paling kecil, besar, dan tengah dan menentukan kembali ada di range mana.
Seterusnya dilakukan sampai datanya ketemu.

INTERPOLATION SEARCH
Search jenis ini merupakan pengembangan dari binary search. Nilai tengahnya ditentukan dengan menggunakan rumus.





Jika pada binary search kita menentukan nilai tengah dengan (awal+akhir)/2,
pada interpolation setidaknya nilai tengahnya tidak asal pilih, tapi ada rumusnya.
Walaupun tidak 100% akurat memilih nilai yang diinginkan akan tetapi sangat membantu dalam
pencarian.
Jadi intinya, pada jenis searching ini, metode pencariannya tidak beda jauh dengan binary search, hanya penentuan nilai tengahnya saja yang beda.

---referensi gambar---
geeksforgeeks.com
algolist.net
interviewbit.com
java67.com
miro.medium.com
ppt binus
--------------------------