Tìm hiểu thuật toán chia để trị trong lập trình, ví dụ áp dụng

#include <stdio.h>
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int left = low;
    int right = high - 1;
    while(true){
        while(left <= right && arr[left] < pivot) left++; // Tìm phần tử >= arr[pivot]
        while(right >= left && arr[right] > pivot) right--; // Tìm phần tử <= arr[pivot]
        if (left >= right) break; // Đã duyệt xong thì thoát vòng lặp
        swap(arr[left], arr[right]); // Nếu chưa xong, đổi chỗ.
        left++; // Vì left hiện tại đã xét, nên cần tăng
        right--; // Vì right hiện tại đã xét, nên cần giảm
    }
    swap(arr[left], arr[high]); //Đổi chỗ phần từ left với pivot, khi đó pivot đứng đúng vị trí
    return left; // Trả về chỉ số sẽ dùng để chia đổi mảng
}
  
/* Hàm giải thuật quicksort */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi là chỉ số nơi phần tử này đã đứng đúng vị trí
         và là phần tử chia mảng làm 2 mảng con trái & phải */
        int pi = partition(arr, low, high);
  
        // Gọi đệ quy sắp xếp 2 mảng con trái và phải
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
  
int main()
{
    int arr[] = {1, 8, 3, 9, 4, 5, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
 
    printf("Sorted array: \n");
    for (int i=0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

#include <stdio.h>
 
// Hàm tìm kiếm nhị phân 
int binarySearch(int arr[], int n, int x) {
  int r = n - 1; // chỉ số phần tử cuối
  int l = 0; // Chỉ số phần tử đầu tiên
  while (r >= l) {
    int mid = (l+r)/2; //vị trí ở giữa
  
    // Nếu arr[mid] = x, trả về chỉ số và kết thúc.
    if (arr[mid] == x)
      return mid;
  
    // Nếu arr[mid] > x, cập nhật lại right
    if (arr[mid] > x)
      r = mid - 1;
    // Nếu arr[mid] < x, cập nhật lại left
    if (arr[mid] < x)
      l = mid + 1;
  }
  
  // Nếu không tìm thấy
  return -1;
}
  
int main(void) {
  int arr[] = {2,3,4,10,40};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  int result = binarySearch(arr, n, x);
  if (result == -1)
     printf("Khong tim thay phan tu %d trong mang",x);
  else
    printf("%d xuat hien tai chi so %d", x, result);
  return 0;
}

#include<stdlib.h>
#include<stdio.h>
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    //Tạo 2 mảng tạm con
    int L[n1], R[n2];
 /* Copy dữ liệu sang các mảng tạm */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
  
    i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên
    j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai
    k = l; // Khởi tạo chỉ số bắt đầu của mảng lưu kết quả
/* Trộn hai mảng tạm vừa rồi vào mảng arr*/
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
//Lấy phần còn lại của dãy L cho vào cuối dãy arr nếu còn.
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
 //Lấy phần còn lại của dãy R cho vào cuối dãy arr nếu còn.
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}
  
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
     //Tìm chỉ số nằm giữa mảng để chia mảng thành 2 nửa:
        int m = l+(r-l)/2;
 
     // Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
 
     //Gọi hàm trộn
        merge(arr, l, m, r);
    }
}
 // Hàm xuất mảng 
void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
    printf("%d ", A[i]);
    printf("\n");
}
  
  
int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
  
    
    mergeSort(arr, 0, arr_size - 1);
    printf("\nSorted array:\n");
    printArray(arr, arr_size);
return 0;
}