Gdy trzeba posortować jakąś kolekcję w sposób - nazwijmy to - standardowy, to zwykle nie ma z tym problemu. Chyba każdy język posiada coś na takie okazje: mamy funkcję qsort, std::sort (i std::list::sort), System.Array.Sort, java.util.Arrays.sort, i tak dalej. Zwykle wystarczy podać im tablicę lub kolekcję i już mamy ją posortowaną.
Istnieją jednak przynajmniej dwie sytuacje, gdzie taka standardowa procedura nie jest wystarczająca. Jest tak na przykład wtedy, gdy:
- zwykły sposób porównywania obiektów nie jest tym, którego chcielibyśmy używać przy sortowaniu. Ów "zwykły sposób" jest wyznaczany najczęściej przez operatory relacyjne (
<,>=, itp.), które nie muszą być zdefiniowane (np. jeśli sortujemy obiekty własnego typu złożonego) lub mogą być określone inaczej niż byśmy w danym przypadku sortowania chcieli. - życzymy sobie odwrotnego porządku sortowania, czyli np. malejącego zamiast domyślnego rosnącego
W powyższych przypadkach rozwiązanie sprowadza się zwykle do zdefiniowania własnego kryterium porównawczego obiektów, które sortujemy. Spotyka się tu najczęściej dwie formy takiego kryterium:
- W C++ możemy zdefiniować predykat binarny (funkcję przyjmującą dwa argumenty i zwracającą wartość binarny), który określa dla obiektów tzw. ścisłe uporządkowanie słabe (strict weak ordering). Mówiąc w skrócie, funkcja ta powinna mieć identyczne właściwości jak zwykły operator mniejszości
<, czyli zwracaćtrue, jeśli pierwszy obiekt jest "mniejszy" niż drugi. Jak nietrudno zauważyć, taka informacja jest wystarczająca do jednoznacznego uporządkowania dwóch obiektów. W szczególnościa == bzachodzi wtedy i tylko wtedy, gdy!(a < b) && !(b < a), zatem taki predykat może też służyć do sprawdzania, czy dwa obiekty są sobie równe.
Domyślnym predykatem sortowania w C++ jeststd::less, który działa identycznie jak operator<.std::greaterpozwala natomiast na odwrócenie porządku sortowania. -
Wynik Relacja < 0 x < y == 0 x == y > 0 x > y W C, C# i w Javie korzysta się z kolei z funkcji porządkujących, które przyjmują dwa obiekty i zwracają w wyniku liczbę całkowitą. Liczba ta określa jednoznacznie uporządkowanie tych dwóch obiektów: czy jeden jest mniejszy niż drugi, równy mu czy większy od niego - tak, jak to pokazano w tabelce obok.
Interesującą cechą takiego sposobu porządkowania jest to, że tak naprawdę używanie jakichkolwiek porównań (<=,>itp.) często nie jest w nim potrzebne. Zazwyczaj bowiem ową funkcję porównującą można zaimplementować następująco:int compare(x, y) { return val(x) - val(y); }gdzie
val(x)oznacza tutaj pewną wartość liczbową przyporządkowaną obiektowix, określającą jego miejsce w danym porządku sortowania. Wartość ta powinna być tak dobrana, aby posortowanie wszystkich takich liczb rosnąco dało nam w wyniku pożądaną kolejność uporządkowania naszych obiektów. Jeśli więc, przykładowo, chcemy posortować ciągi znaków w C# tak, by najdłuższe znalazły się na początku (czyli malejąco względem długości), toval(x)oznaczać tu będzie-x.Length().
Uff, jak widać sortowanie czasami nie jest wcale taką prostą sprawą :) Cieszmy się jednak, że nawet w bardziej skomplikowanych sytuacjach do napisania pozostają nam jedynie proste predykaty porównujące, nie zaś... całe algorytmy ;]





Do czego może przydać się takie cudo, oprócz wspomnianej już wizualizacji funkcji R2->R na płaszczyźnie? Pewnie do niewielu rzeczy :) Ja wpadłem jednak na jeszcze jedno potencjalne zastosowanie.
W vimie i jego pochodnych taką sztuczką były polecenia wpisywane od dwukropka (na czele z najbardziej przydatnym, czyli 

