sorting_algorithms.cpp

/*
Sorting Algorithms & Custom Comparators
Mathematical Foundation: Comparison-based sorts O(n log n), Non-comparison O(n+k)
Quick Sort: Average O(n log n), Worst O(n²), In-place
Merge Sort: O(n log n), Stable, O(n) space
Heap Sort: O(n log n), In-place, Not stable
*/

#include <bits/stdc++.h>
using namespace std;

// Quick Sort Implementation
void quickSort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);
    quickSort(a, p + 1, r);
}

int partition(vector<int>& a, int l, int r) {
    int pivot = a[r], i = l;
    for (int j = l; j < r; j++) {
        if (a[j] <= pivot) swap(a[i++], a[j]);
    }
    swap(a[i], a[r]);
    return i;
}

// Merge Sort Implementation
void mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    merge(a, l, m, r);
}

void merge(vector<int>& a, int l, int m, int r) {
    vector<int> L(a.begin() + l, a.begin() + m + 1);
    vector<int> R(a.begin() + m + 1, a.begin() + r + 1);
    int i = 0, j = 0, k = l;
    while (i < L.size() && j < R.size()) {
        a[k++] = L[i] <= R[j] ? L[i++] : R[j++];
    }
    while (i < L.size()) a[k++] = L[i++];
    while (j < R.size()) a[k++] = R[j++];
}

// Heap Sort Implementation
void heapSort(vector<int>& a) {
    auto heapify = [&](int n, int i) {
        function<void(int, int)> h = [&](int n, int i) {
            int largest = i, l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && a[l] > a[largest]) largest = l;
            if (r < n && a[r] > a[largest]) largest = r;
            if (largest != i) { swap(a[i], a[largest]); h(n, largest); }
        };
        h(n, i);
    };
    
    int n = a.size();
    for (int i = n / 2 - 1; i >= 0; i--) heapify(n, i);
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);
        heapify(i, 0);
    }
}

// Counting Sort (Non-comparison)
// LeetCode: 75. Sort Colors
// https://leetcode.com/problems/sort-colors/
void sortColors(vector<int>& a) {
    vector<int> cnt(3);
    for (int x : a) cnt[x]++;
    int idx = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < cnt[i]; j++) a[idx++] = i;
    }
}

// Dutch National Flag (3-way partition)
void sortColors3Way(vector<int>& a) {
    int l = 0, r = a.size() - 1, i = 0;
    while (i <= r) {
        if (a[i] == 0) swap(a[l++], a[i++]);
        else if (a[i] == 2) swap(a[r--], a[i]);
        else i++;
    }
}

// Custom Comparators Examples
// Sort by Multiple Criteria
// LeetCode: 56. Merge Intervals
// https://leetcode.com/problems/merge-intervals/
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res;
    for (auto& iv : intervals) {
        if (res.empty() || res.back()[1] < iv[0]) res.push_back(iv);
        else res.back()[1] = max(res.back()[1], iv[1]);
    }
    return res;
}

// Sort by Custom Lambda
// LeetCode: 1636. Sort Array by Increasing Frequency
// https://leetcode.com/problems/sort-array-by-increasing-frequency/
vector<int> frequencySort(vector<int>& a) {
    unordered_map<int,int> freq;
    for (int x : a) freq[x]++;
    sort(a.begin(), a.end(), [&](int x, int y) {
        return freq[x] == freq[y] ? x > y : freq[x] < freq[y];
    });
    return a;
}

// K Closest Points to Origin
// LeetCode: 973. K Closest Points to Origin
// https://leetcode.com/problems/k-closest-points-to-origin/
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    nth_element(points.begin(), points.begin() + k, points.end(),
        [](auto& a, auto& b) { return a[0]*a[0] + a[1]*a[1] < b[0]*b[0] + b[1]*b[1]; });
    return vector<vector<int>>(points.begin(), points.begin() + k);
}

// Top K Frequent Elements (Heap)
// LeetCode: 347. Top K Frequent Elements
// https://leetcode.com/problems/top-k-frequent-elements/
vector<int> topKFrequent(vector<int>& a, int k) {
    unordered_map<int,int> freq;
    for (int x : a) freq[x]++;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    for (auto& p : freq) {
        pq.push({p.second, p.first});
        if (pq.size() > k) pq.pop();
    }
    vector<int> res;
    while (!pq.empty()) { res.push_back(pq.top().second); pq.pop(); }
    return res;
}

// Meeting Rooms II (Interval Scheduling)
// LeetCode: 253. Meeting Rooms II
// https://leetcode.com/problems/meeting-rooms-ii/
int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<pair<int,int>> events;
    for (auto& iv : intervals) {
        events.push_back({iv[0], 1});
        events.push_back({iv[1], -1});
    }
    sort(events.begin(), events.end());
    int rooms = 0, mx = 0;
    for (auto& e : events) {
        rooms += e.second;
        mx = max(mx, rooms);
    }
    return mx;
}