Sortowanie dla zaawansowanych

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ści a == b zachodzi 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++ jest std::less, który działa identycznie jak operator <. std::greater pozwala 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:

  1. int compare(x, y) { return val(x) - val(y); }

  gdzie val(x) oznacza tutaj pewną wartość liczbową przyporządkowaną obiektowi x, 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), to val(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 ;]