Sorting And Searching

Jadi ini materi sebenarnya susah-susah gampang yaaa, gampang karena tinggal ngafalin algonya aja.

Sorting tuh kita mengurutkan data baik secara menurun (dari besar ke rendah) atau sebaliknya.

Macam macam sorting ada bubble, quick, selection, insert.

Tapi disini gua fokus ke bubble sama quick aja karena bubble cocok buat kita yg masih beginner dan quick itu yang paling cepat yang paling sering dipakai didalam kasus nyata.
Apa sih itu bubble sort?? bubble sort adalah salah satu metode sorting dimana setiap array akan membandingkan dengan array sebelahnya, dan apabila array yang disebelah kiri lebih besar dari kanan maka akan di switch tempatnya.
Gua langsung ngasih codingan aja deh biar lebih gampang.
#include <stdio.h>
  
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
  
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)      
  
       // Last i elements are already in place   
       for (j = 0; j < n-i-1; j++) 
           if (arr[j] > arr[j+1])
              swap(&arr[j], &arr[j+1]);
}
  
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("n");
}
  
// Driver program to test above functions
int main()
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}
//CODINGAN INI GUA KUTIP DARI https://www.geeksforgeeks.org/bubble-sort/
Kekurangan dari bubble sort adalah waktu yang dimakan paling lama diantara
sort lainnya, karena dia harus membandingkan setiap array dan harus switch
posisi dengan array yg isi angkanya lebih besar.

Nah berikutnya adalah quick sort
Dari namanya aja udah cepet ya pastilah ini paling makan waktu dikit.
Caranya dengan menjadikan array pertama sebagai pivot untuk dibandingkan.
Berikut adalah contoh codingannya.

//CODINGAN INI GUA KUTIP DARI https://www.geeksforgeeks.org/quick-sort/
#include<stdio.h>
  
// A utility function to swap two elements
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
  
/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
    array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element
  
    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
  
/* The main function that implements QuickSort
 arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(arr, low, high);
  
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
  
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("n");
}
  
// Driver program to test above functions
int main()
{
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array: n");
    printArray(arr, n);
    return 0;
}

Cukup sekian dari gua, semoga ngerti atau gak dapat gambaran lah tentang
sorting itu apa.


Comments

Post a Comment