Quick Sort Implementation

Quick sort employs a divide-and-conquer strategy to sort elements. The algorithm selects a pivot element (typically the middle value) and partitions the array into two sections - elements less than the pivot and elements greater than the pivot. This process repeats recursively until the entire array is sorted.

#include <iostream>
using namespace std;

const int MAX_SIZE = 100010;

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    
    int pivot = arr[(left + right) / 2];
    int i = left - 1, j = right + 1;
    
    while (i < j) {
        do i++; while (arr[i] < pivot);
        do j--; while (arr[j] > pivot);
        if (i < j) swap(arr[i], arr[j]);
    }
    
    quickSort(arr, left, j);
    quickSort(arr, j + 1, right);
}

int main() {
    int n, nums[MAX_SIZE];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> nums[i];
    
    quickSort(nums, 0, n - 1);
    
    for (int i = 0; i < n; i++) cout << nums[i] << " ";
    return 0;
}

Merge Sort Implementation

Merge sort divides the aray into halves, recursively sorts each half, and then merges them back together. The merging process compares elements from both halves and combines them in order.

#include <iostream>
using namespace std;

const int MAX_SIZE = 100010;
int temp[MAX_SIZE];

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;
    
    int mid = (left + right) >> 1;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    
    int k = 0, i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    for (i = left, j = 0; i <= right; i++, j++) 
        arr[i] = temp[j];
}

int main() {
    int n, nums[MAX_SIZE];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> nums[i];
    
    mergeSort(nums, 0, n - 1);
    
    for (int i = 0; i < n; i++) cout << nums[i] << " ";
    return 0;
}

Binary Search Techniques

Integer Binary Search

Binary search requires a sorted array and finds elements by repeatedly dividing the search interval in half. There are two main variations:

// Finding first occurrence
int findFirst(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left < right) {
        int mid = (left + right) >> 1;
        if (arr[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left;
}

// Finding last occurrence  
int findLast(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left < right) {
        int mid = (left + right + 1) >> 1;
        if (arr[mid] <= target) left = mid;
        else right = mid - 1;
    }
    return left;
}

Floating Point Binary Search

This variation is used for finding roots of equations or other continuous value searches:

#include <iostream>
#include <cmath>
using namespace std;

double cubeRoot(double n) {
    double epsilon = 1e-8;
    double left = -10000, right = 10000;
    
    while (right - left > epsilon) {
        double mid = (left + right) / 2;
        if (mid * mid * mid >= n) right = mid;
        else left = mid;
    }
    return left;
}

int main() {
    double num;
    cin >> num;
    printf("%.6lf", cubeRoot(num));
    return 0;
}

Practical Applications

Counting Inversions

Merge sort can be modified to count inversions by tracking swaps during the merge process:

long long countInversions(int arr[], int left, int right) {
    if (left >= right) return 0;
    
    int mid = (left + right) >> 1;
    long long count = countInversions(arr, left, mid) + 
                     countInversions(arr, mid + 1, right);
    
    int k = 0, i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else {
            temp[k++] = arr[j++];
            count += mid - i + 1;
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    for (i = left, j = 0; i <= right; i++, j++) 
        arr[i] = temp[j];
        
    return count;
}

Classroom Allocation Problem

Binary search combined with difference arrays can efficiently solve allocation problems:

bool validateRequests(int n, int m, int rooms[], vector<tuple<int,int,int>>& requests, int day) {
    vector<int> diff(n + 2, 0);
    
    for (int i = 0; i <= day; i++) {
        auto [d, s, t] = requests[i];
        diff[s] += d;
        diff[t + 1] -= d;
    }
    
    for (int i = 1; i <= n; i++) {
        diff[i] += diff[i - 1];
        if (diff[i] > rooms[i - 1]) return false;
    }
    return true;
}