std::nth_element

Giriş
std::sort() gibi veriyi sıralar ancak farklı olarak verinin tamamını değil, sadece ilk n elemanı sıralar.
İlk parametre dizinin başlangıç iteratorü,
ikinci parametre sıralamanın biteceği n. elemanın iteratörü,
üçüncü parametre ise dizinin bitiş iteratörüdür.
dördüncü parametre farklı bir overload ile geliyor. Comparator olarak kullanılır.

Örnek
En küçük ilk 4 elemanı sıralamak için şöyle yaparız.

vector<int> v = ...;
nth_element(v.begin(), v.begin()+4, v.end());

Örnek
En küçük 3. elemanı bulmak için şöyle yaparız.

std::nth_element(arr, arr + 2, arr + size);
return arr[2];

Örnek
En büyük n. elemanı bulmak için şöyle yaparız.

std::vector<double> v =...;
std::nth_element(v.begin(), v.begin() + idx, v.end(), std::greater<double>());
nth_element = v[idx];

Aslında bu algoritmanın ismi Quickselect ve  farklı dillerde gerçekleştirimleri şöyle.

Örnek - top 20
Bana en yakın mesafedeki 20 noktayı şöyle bulabilirdim.

std::vector<closest> v = ....;
nth_element(v.begin(), v.begin() + 20, v.end(), comp);

Örnek - comparator
Şöyle yaparız. Comparator biraz fazla çağrılıyor ancak median + min + max değerleri bulmak mümkün.

int min = a[0], max = a[0];
std::nth_element(a.begin(), a.begin() + n, a.end(),
    [&](int lhs, int rhs) {
        min = std::min(min, std::min(lhs, rhs));
        max = std::max(max, std::max(lhs, rhs));
        return lhs < rhs;
    });

algoritmanın basit bir gerçekleştirimi
Örnek
Çok basit bir gerçekleşimi Java'da Priority Queue ile olabilir. Şöyle yaparız.

int findKthLargest(int[] nums, int k) {
  int p = 0;
  int numElements = nums.length;
  // create priority queue where all the elements of nums will be stored
  PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

  // place all the elements of the array to this priority queue
  for (int n : nums){
    pq.add(n);
  }

  // extract the kth largest element
  while (numElements-k+1 > 0){
    p = pq.poll();
    k++;
  }

  return p;
}

Örnek
Çok basit bir gerçekleşimi C++'ta priority_queue ile olabilir. Şöyle yaparız.

template <typename T, typename Compare = std::less<T>>
std::vector<T> filter_pqueue(std::vector<T> v, 
                             typename std::vector<T>::size_type n) {
    std::vector<T> result;
    std::priority_queue<T, std::vector<T>, Compare> q;
    for (auto i: v) {
        q.push(i);
        if (q.size() > n) {
            q.pop();
        }
    }
    while (!q.empty()) {
        result.push_back(q.top());
        q.pop();
    }
    return result;
}

Eğer sonuçları sıralı istiyorsak std::set'te kullanılabilir.

template <typename T, typename Compare = std::less<T>>
std::vector<T> filter_set(std::vector<T> v, 
                          typename std::vector<T>::size_type n) {
    std::set<T, Compare> s;
    for (auto i: v) {
        s.insert(i);
        if (s.size() > n) {
            s.erase(std::prev(s.end()));
        }
    }
    return std::vector<T>(s.begin(), s.end());
}

Diğer

n tane daha küçük diziye bölen algoritma - 1

Gerçek kodda k-th order statistics kullandığı söyleniyor ama algoritmayı anlamadım. Açıklaması şöyle

1. Divide the array in to n/5 lists of 5 elements each.
2. Find the median in each sub array of 5 elements.
3. Recursively find the median of all the medians, lets call it M
4. Partition the array in to two sub array 1st sub-array contains the elements larger than M , lets say this sub-array is a1 , while other sub-array contains the elements smaller then M., lets call this sub-array a2.
5. If k <= |a1|, return selection (a1,k).
6. If k− 1 = |a1|, return M.
7. If k> |a1| + 1, return selection(a2,k −a1 − 1).

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

n tane daha küçük diziye bölen algoritma - 2
İlk algoritmaya benzer şekilde n tane küçük diziye bölen kod şöyle. Bu sefer elimizdeki liste sıralı değil. k değeri kaçın alt diziyi istediğimizi, y değeri ise alt dizinin büyüklüğünü gösteriyor.

1. k * y ile alt dizinin nerede başlayacağını lower olarak buluyoruz.
2. lower + y ile alt dizinin nerede bitmesi gerektiğini upper olarak buluyoruz.
3. std::nth_element ile lower'a kadar elemanları sıralıyoruz.
4. std::nth_element ile lower+1 , upper-1 arasındaki elemanları sıralıyoruz.
5. lower ve upper arasındaki elemanları sıralıyoruz.

std::vector<int> vec = muchData();
// Fix those bound iterators as needed
auto lower = vec.begin() + k*y;
auto upper = lower + y;

// put right element at lower and partition vector by it
std::nth_element(vec.begin(), lower, vec.end());
// Same for upper, but don't mess up lower
std::nth_element(lower + 1, upper - 1, vec.end());
// Now sort the subarray
std::sort(lower, upper);