კომპარატორები და სტაბილურობა

std::sort(v.begin(), v.end(), comp) უშვებს O(n log n) ალგორითმს (introsort) და შენს მონაცემზე ერთადერთი, რაც იცის, შენი ფუნქცია comp(a, b)-ა, რომელიც პასუხობს: a უნდა იყოს b-ზე წინ?

ესე იგი ნებისმიერი წესით შეგიძლია დაალაგო:

• კლებადობით: return a > b;
• ველით: return a.score > b.score;
• რამდენიმე გასაღებით: შეადარე პირველი გასაღები; მხოლოდ ტოლობისას შეადარე შემდეგი

სხვა ენებში სხვანაირად გამოიყურება, მაგრამ ასევე მუშაობს: Python sorted(v, key=lambda p: (-p.score, p.name)), Java Comparator.comparing(...). გასაღების ფუნქცია, რომელიც კორტეჟს აბრუნებს, ხშირად ყველაზე მარტივი გზაა მრავალგასაღებიანი რიგის სწორად მისაღებად.

კომპარატორი მკაცრი „ნაკლებია“-სავით უნდა იქცეოდეს (მკაცრი სუსტი რიგი):

• comp(a, a) არის false: არაფერი დგას საკუთარ თავზე წინ
• თუ comp(a, b) true-ა, comp(b, a) false უნდა იყოს
• უნდა იყოს ტრანზიტული: a b-ზე წინ და b c-ზე წინ ნიშნავს a c-ზე წინ

კლასიკური შეცდომაა <-ის ნაცვლად <=-ის დაწერა. მაშინ comp(x, x) true-ა, ალგორითმის დაშვებები ირღვევა და std::sort შეიძლება ნაგავი დააბრუნოს ან მასივის ბოლოს იქით წაიკითხოს და ჩავარდეს. სხვა ხაფანგი: double-ების შედარება, რომლებიც შეიძლება NaN იყოს, ან „შემთხვევითი“ კომპარატორი არევისთვის.

კომპარატორი იაფიც უნდა იყოს: ის დაახლოებით n log n-ჯერ სრულდება. შეფარდებების მსგავსი მნიშვნელობები ერთხელ წინასწარ გამოთვალე და ყოველ გამოძახებაზე ნუ ითვლი თავიდან.