Various algorithms

kth.cpp

// Order Statistic
// https://stepik.org/lesson/12564/step/8?unit=2992
#include <utility>
#include <vector>

template <typename T>
T kth(std::vector<T>& v, size_t k) {
    size_t L = 0, R = v.size();    
    
    while (L + k < R) {
        auto pivot = v[(L + R) / 2];

        auto eq = L, gt = R;
        for (auto current = L; current < gt; ++current) {
            if (v[current] == pivot) continue;
            if (v[current] < pivot) {
                if (eq != current) {
                    std::swap(v[eq], v[current]);
                }
                ++eq;
                continue;
            }
            // v[current] > pivot
            while (--gt > current && v[gt] > pivot) {}
            if (current >= gt) break;
            std::swap(v[gt], v[current]);
            --current;
        }

        if (L + k < eq) {
            R = eq;
            continue;
        }
        if (L + k < gt) {
            return pivot;
        }
        k -= gt - L;
        L = gt;
    }
    return 0;    // Not found
}

qsort.cpp

// Quick sort
// https://stepik.org/lesson/12564/step/4?unit=2992
#include <iostream>
#include <utility>

template <typename T>
void iSort(std::vector<T>&);

template <typename T>
void qSort(std::vector<T>&);

template <typename T>
void iSort(std::vector<T>& v) {
    for (size_t i = 1; i < v.size(); ++i) {
        if (v[i] >= v[i-1]) continue;
        auto item = v[i];
        auto j = i;
        for (; j > 0 && v[j-1] > item; --j) {
            v[j] = v[j-1];
        }
        v[j] = item;
    }
}

template <typename T>
void qSort(std::vector<T>& v) {
    const size_t minBatch = 42;
    //const size_t minBatch = 1;
    std::vector<std::pair<size_t, size_t>> stack = {{0, v.size()}};
    
    while (!stack.empty()) {
        auto L = stack.back().first;
        auto R = stack.back().second;
        stack.pop_back();
        if (R < L + minBatch) continue;
        
        auto first = v[L], pivot = v[(L + R) / 2], last = v[R - 1];
        if (first > pivot) std::swap(first, pivot);
        if (pivot > last) std::swap(pivot, last);
        if (first > pivot) std::swap(first, pivot);

        auto eq = L, gt = R;
        for (auto current = L; current < gt; ++current) {
            if (v[current] == pivot) continue;
            if (v[current] < pivot) {
                if (eq != current) {
                    std::swap(v[eq], v[current]);
                }
                ++eq;
                continue;
            }
            // v[current] > pivot
            while (--gt > current && v[gt] > pivot) {}
            if (current >= gt) break;
            std::swap(v[gt], v[current]);
            --current;
        }
        if (eq > L + minBatch) {
            stack.emplace_back(L, eq);
        }
        if (R > gt + minBatch) {
            stack.emplace_back(gt, R);
        }
    }
   
    iSort(v);
}

qsort.py

# https://habr.com/sandbox/29775/
import numpy as np 
import tqdm

def qsort(arr):

    def partition(arr, l, h, pivot):
        while l <= h:
            while arr[l] < pivot:
                l += 1
            while arr[h] > pivot:
                h -= 1
            if l >= h:
                break
            t = a[l]
            a[l] = a[h]
            a[h] = t
            l += 1
            h -= 1
        return h

    def sort(arr, l, h):
        if l >= h:
            return
        i = partition(arr, l, h, arr[(l+h)//2])
        sort(arr, l, i)
        sort(arr, i+1, h)

    sort(arr, 0, len(arr)-1)

for i in tqdm.trange(10000):
    a = list(np.random.randint(1, 9, 500))
    qsort(a)
    assert(a==sorted(a))

reverse.cpp

template <typename T>
class reverse_adaptor {
 public:
  reverse_adaptor(T& c) : container(c) {}

  using iterator = typename T::reverse_iterator;

  iterator begin() { return container.rbegin(); }
  iterator end() { return container.rend(); }

 private:
  T& container;
};

template <typename T>
reverse_adaptor<T> backword(T& c) {
  return reverse_adaptor<T>(c);
}

rsort.cpp

// Radix sort (binary)
// https://stepik.org/lesson/12565/step/11?unit=2993
#include <utility>
#include <vector>

template <typename T>
void rSort(std::vector<T>& v) {
    std::vector<T> tmp(v.size());
    for (T mask = 1; ; mask += mask) {
        size_t offset = 0, nonempty = 0, i = 0;
        for (auto& item : v) {
            tmp[i++] = item;
            if (!(item & mask)) ++offset;
            if ((item & (mask - 1)) != item) ++nonempty;
        }
        if (!nonempty) break;
        size_t i0 = 0, i1 = offset;
        for (auto& item : tmp) {
            v[item & mask ? i1++ : i0++] = item;
        }
    }
}