std::sort metodu

İmzası
sort metodu random access iterator ile çalışır. Metodun imzası şöyledir.

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

Comparator
Comparator'un imzası şöyledir. Burada a ve b parametreleri farklı tiplere sahip olabilir gibi görünüyor. Ancak bu kullanımla hiç karşılaşmadım

bool cmp(const Type1 &a, const Type2 &b);

Örnek
Elimizde hiyerarşi içeren şöyle bir kod olsun.

struct Animal {};
struct Cat : Animal {};
struct Dog : Animal {};
struct Hound : Dog {};

bool cmp(const Animal &a, const Animal &b);

Comparator hep ata sınıfa göre yazılır. Şöyle yaparız.

std::vector<Hound> hounds;
... // fill hounds
std::sort(hounds.begin(), hounds.end(), cmp);

Bazı Veri Yapıları
Bazı veri yapıları random access iterator sağlayamaz. Bu yüzden kendi sort metodlarına sahiptirler.

Örneğin list gibi. Aşağıdaki kod derlenmez.

std::list<int> lst = { 1, 7, 5, 12 };
sort(lst);

Kendi sort metoduna sahip olmayan veri yapıları için genel sort metodu kullanılabilir.

sort algoritmasının içi
Sort algoritmasının nasıl olacağı kullanılan runttime kütüphanesine göre değişir. Bir çok runtime dizinin uzunluğuna göre farklı çalışan Introsort algoritmasını kullanıyor. Bu algoritma küçük diziler için için Insertion Sort kullanır.

Insertion Sort iki elemanı yer değiştirdiği için, C++11 kullanıyorsak move constructor yazmakta fayda var. Kullanmıyorsak copy constructor ve assignment operatorlerine ihtiyaç duyar.

Microsoft sort Algoritmasının İçi
Microsoft'un sort algoritması şöyle.

const int ISORT_MAX = 32;  // maximum size for insertion sort

template<class RanIt, class Diff, class Pr>
void Sort(RanIt First, RanIt Last, Diff Ideal, Pr Pred)
{
  Diff Count;
  for (; ISORT_MAX < (Count = Last - First) && 0 < Ideal; )
  { // divide and conquer by quicksort
    pair<RanIt, RanIt> Mid = Unguarded_partition(First, Last, Pred);

    // ...
  }

  if (ISORT_MAX < Count)
  { // heap sort if too many divisions
    Make_heap(First, Last, Pred);
    Sort_heap(First, Last, Pred);
  }
  else if (1 < Count)
    Insertion_sort(First, Last, Pred);  // small
}

Açıklaması şöyle.

When the range to be sorted has 32 elements or less, Sort uses insertion sort. Insertion sort doesn't use swap in its implementation. Otherwise, divide-and-conquer quick sort is used. In the implementation it calls iter_swap (inside Unguarded_partition), which in turn calls swap:

32 elemandan uzun diziler için kullanılan Heap Sort'un içi şöyle. std::swap() metodunu çağırıyor.

template<class FwdIt1, class FwdIt2>
void iter_swap(FwdIt1 Left, FwdIt2 Right)
{   // swap *Left and *Right
  swap(*Left, *Right);
}

Elimizde şöyle bir kod olsun. Sort edilmeye çalışılan dizi 32'den büyük olduğu için swap metodumuzun çağrıldığını görebiliiriz.

class A 
{
public:
    A(int);
    A(const A&);
    A& operator=(const A&);
    ~A();
private:

    friend bool operator<(const A&, const A&);
    friend void swap(A&, A&);
};

A::A(){...}

A::A(const A& rhs){...}

A& A::operator = (const A & rhs){...}

A::~A(){...}

bool operator<(const A& lhs, const A& rhs){...}

void swap(A& lhs, A& rhs)
{
    cout << "swap(A&, A&)" << endl;
    using std::swap;
    swap(lhs.ptr_, rhs.ptr_);
}

int main()
{

  std::vector<A> v{ 33,32,31,30,29,28,27,26,25,24,23,22, 21,20,19,18,17,16,15,14,13,12,
    11,10,9,8,7,6,5, 4,3,2,1 };
  std::sort(v.begin(), v.end());

}

sort ve elemanların yer değiştirmesi
sort stable bir algoritma değildir. Eşit elemanların yerleri değişebilir.

comparator nasıl çalışır
Sıralama metodu her zaman a,b şeklinde iki tane eleman alır ve her zaman a < b'nin sonucunu true veya false olarak döndürür.

sort için strick weak ordering kullanılır.Daha detaylı bilgi için Strict Weak Ordering yazısına bakabilirsiniz.

1 Comparator
1.1 Struct comparator
Bir struct tanımlanır ve struct operator()'ü gerçekleştirilir. Kullanılması gereken metod imzası şöyle tanımlı. Metodun kendisinin const olması gerekmiyor ancak bence böyle yapılırsa daha iyi.

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function object must not modify the objects passed to it.

yani () operatörü, parametreleri const olarak almalıdır. Şöyle yaparız.

struct cmp
{
  bool operator()(const Person &K , const Person &K1)
  {
    ...
  }
}

1.2 Global Metod Comparator
Şöyle global bir metod tanımlarız.

bool compare(Foo obj1, Foo obj2) {
  ...
}

Şöyle yaparız.

std::sort(data.begin(), data.end(), compare);

1.3 Üye Metod Comparator
Şöyle yaparız.

class Foo {
public:
  bool compare(const int& a, const int& b){
    ....
  }
  void sort(){
    std::sort (data.begin() ,
               data.end() ,
               std::bind<bool>(&Foo::compare,this, _1 , _2 )
              );
  }
  std::vector<int> data;
}

Eğer üye metod static ise bind kullanmaya gerek kalmaz. Üye metod tanımlamak için şöyle yaparız.

static bool compare(Foo obj1, Foo obj2);

Şöyle yaparız.

std::sort(data.begin(), data.end(), &Foo::compare);

1.4 Lambda Comparator
C++11 ile sıralama metodu olarak lambda da kullanılabilir. Şöyle yaparız.

std::sort(test.begin(), test.end(), [](const node* pa, const node* pb) {
    return pb->frequency < pa->frequency;
});

2. Operator <

< operatörünü gerçekleştiren bir metod tanımlanır. Metod parametreleri const almalıdır. Şöyle yaparız

bool operator< (const Person & other) const
{
  ...
}

Diğer

sort ve pointer

pointer içeren veri yapıların sıralarken biraz daha dikkatli olmak lazım. Comparator veya lambda pointer ile çalışmak için kodlanmalı. Örnekte node* nesnelerinin < operatörleri çağrılarak sıralama gerçekleşiyor.

std::sort(test.begin(), test.end(), [](const node* pa, const node* pb) {
    return (*pb) < (*pa);
});

Birden fazla alana göre sıralamak

Bir çok yöntem kullanılabilir. Benim en kolay anlaşılır bulduğum kod şöyle.

if (lhs.first != rhs.first)
  return lhs.first < rhs.first;                
if (lhs.second != rhs.second)
  return lhs.second< rhs.second;
return lhs.third < rhs.third;

Ya da şöyle yazılabilir.

bool operator<(const Key& rhs) const
{
  if (a < rhs.a)
    return true;
  if (a > rhs.a)
    return false;

  if (b < rhs.b)
    return true;
  if (b > rhs.b)
    return false;

  return (c < rhs.c);
};

Şöyle kodları sevmiyorum. Bence okuması çok zor.

if (a1 < b1)
  return true;
if (b1 < a1)
  return false;

// a1==b1: continue with element 2
if (a2 < b2)
  return true;
if (b2 < a2)
  return false;

// a2 == b2: continue with element 3
if (a3 < b3)
  return true;
return false; // early out

std::tie kullanan örnekler de var. std::tie a,b,c, elemanlarını teker teker karşılaştırır. Şöyle yaparız.

bool operator<(const My_Struct& lhs, const My_Struct& rhs)
{
  return std::tie(lhs.a_, lhs.b_, lhs.c_) < std::tie(rhs.a_, rhs.b_, rhs.c_);
}

Sıralama Sonucunda Sadece İndeksi Almak
Girdi olan veri yapısını bozmadan sadece indeksleri elde etmek için şöyle yaparız.

int arr[4] = { 2, 7, 3, 4 };//Array of values

int indexofarr[4] = { 0, 1, 2, 3 };//Array indices

std::sort(indexofarr, indexofarr+ 4, [arr](int l, int r) { return arr[l] < arr[r]; });