Partitions, k-th statistic, quicksort , merge sort

partitions-qsort-kthstat.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

    typedef vector<int>::iterator Iterator;
    
    void merge_sort(Iterator b, Iterator e) {
        if (e - b <= 1) return;
        auto m = b + (e - b)/2;
        merge_sort(b, m);
        merge_sort(m, e);
        inplace_merge(b, m, e);
    }

// Dijekstra partition (3 segements)
// it is handy for median and for the case when there are many equal elements
int part(vector<int>& d, int l, int r) {
    int lt = l;
    int gt = r - 1;
    int i = l;
    int x = d[l];
    while (i <= gt) {
        if (x < d[i]) {
            swap(d[i], d[gt]);
            --gt;
        } else if (x > d[i]) {
            swap(d[i], d[lt]);
            ++lt;
            ++i;
        } else ++i;    
    }
    return lt;
}

// Lomuto partition
int partLomuto(vector<int>& a, int l, int r)
{
    int i = l - 1;
    int j = l;
    for (; j< r-1; ++j)
        if (a[j] <= a[r-1]) {
            ++i;
            std::swap(a[i], a[j]);
        }
    std::swap(a[i+1], a[r-1]);
    return i + 1;
}

// Hoare partition http://slideplayer.com/slide/4773930/
// This one requires the least #N operations
int partHoare(vector<int>& a, int p, int r) {
    int x=a[p], i=p-1, j=r;
    while (1) {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);
        if  (i < j)
            swap(a[i],a[j]);
        else
            return j+1;
    }
}

int findKthStat(vector<int>& d, int l, int r, int i) {
    if (l == r - 1)
        return d[l];
    int rnd = rand()%(r - l) + l;
    swap(d[l], d[rnd]);
    int q = part(d, l, r);
    int k = q - l;
    if (k < i)
        return findKthStat(d, q+1, r, k - i - 1);
    else if (k > i)
        return findKthStat(d, l, q, i);
    return d[q];
}

void qsort(vector<int>& d, int l, int r) {
    if (l < r) {
        swap(d[r-1], d[rand()%(r - l) + l]);
        int q = part(d, l, r);
        qsort(d, l, q);
        qsort(d, q+1, r);
    }
}

// find k-th largest (not recursive implementation)
int findKthLargest(vector<int>& nums, int k) {
    if (k > nums.size())
        return -1;
    k = nums.size() - k;
    int l = 0;
    int r = nums.size();
    while (l < r-1) {
        int m = rand()%(r-l) + l;
        swap(nums[m], nums[l]);
        int q = part(nums, l, r);
        if (q == k)
            return nums[q];
        if (q > k)
            r = q+1;
        else
            l = q+1;
    }
    return nums[l];
}

int main()
{
    vector<int> v = {10,11,3,2,11,4,6,7,19};
    //cout << findKthStat(v, 0, v.size(), v.size()/2 + 1);
    qsort(v, 0, v.size());
    std::for_each(v.begin(), v.end(), [](int v) {std::cout << v << " ";});
}