STL Sort Algoritmaları

Giriş
STL algoritmalarını işlevlerine göre gruplamak anlamayı çok daha kolaylaştırıyor. Aşağıdaki algoritmalar sıralı dizileri yine sıralı olarak birleştirme algoritmalarını gösteriyor.

partition
Algoritma şuna benzer.

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    if (first == last) return first;
    ForwardIt part(first++);
    if (first == last) return p(*part) ? first : part;
    while (first != last) {
        if (p(*part))
            ++part;
        else if (p(*first)) {
            iter_swap(part, first);
            ++part;
        }
        ++first;
    }
    return part;
}

Açıklaması şöyle

Complexity
Exactly std::distance(first,last) applications of the predicate and at most std::distance(first,last) swaps. If ForwardIt meets the requirements of BidirectionalIterator at most std::distance(first,last)/2 swaps are done.

Yani n tane eleman varsa ForwardIterator kullanıldığı için en fazla n-1 tane swap yapılır. Eğer BidirectionalIterator kullanılırsa daha az swap yapılır.

lambda ile kullanım örneği
Elimizde şöyle bir liste olsun. hello olmayan elemanları listenin sonuna atmak isteyelim.

list<string> s;

Liste şöyle bölümlenir.

std::partition(
    std::begin(s),
    std::end(s),
    [](const string &w){return w != "hello";});

partition_point

std::partition_point yazısına taşıdım.

stable_partition

std::stable_partition yazısına taşıdım.

nth_element
std::nth_element yazısına taşıdım.

partial_sort
Örnek yaz

partial_sort_copy
Girdi olarak kullanılan veri yapısının sırasını değiştirmez. Sıralanmış veri çıktı olarak verilen veri yapısına kopyalanır.

sort
std::sort yazısına taşıdım

stable_sort
Açıklaması şöyle

O(N·log^2(N)), where N = std::distance(first, last) applications of cmp. If additional memory is available, then the complexity is O(N·log(N)).

Eğer sıralanacak elemen sayısı değeri belirtilmemiş N'den küçükse bellekten tasarruf eden bir algoritma kullanılır. Eğer N'den büyükse zamandan tasarrruf eden bir algoritma kullanılır.
İmzası şöyle

template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
  Compare comp);