Sortowanie dla zaawansowanych

2009-07-02 18:06

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 ;]

Tags: , , ,
Author: Xion, posted under Programming »


6 comments for post “Sortowanie dla zaawansowanych”.
  1. revo:
    July 2nd, 2009 o 22:00

    Warto wspomnieć, że w przypadku C# czasami całkiem ładnie wygląda podanie funkcji sortującej jako lambda wyrażenia.

  2. Aithne:
    July 2nd, 2009 o 22:43

    std.algorithm.sort!(“a > b”)(JakiśZakres);
    Ot – D.

  3. Reg:
    July 5th, 2009 o 12:40

    Obecnie skłaniam się ku opinii, że funkcja/metoda porównująca która zwraca int odpowiednio 0 to najlepsze rozwiązanie i wszelkie operatory == <= itd. warto zaimplementować właśnie z jej użyciem.

  4. Xion:
    July 6th, 2009 o 13:28

    Reg: Tak, ale IMHO jest tak tylko wtedy, jeśli możesz ją zaimplementować w postaci takiej, jak napisałem wyżej, czyli odejmowania val(x) – val(y). A to oznacza, że musisz jakoś określić liczbową wartość każdego obiektu. Najczęściej da się każdemu obiektowi przypisać jakąś sensowną liczbę, ale jeśli nie, to napisanie funkcji compare() musiałoby się oprzeć o porównania – a to już ładne nie jest ;]

  5. Aithne:
    July 8th, 2009 o 21:46

    Patrząc na liczbę komentarzy to mało interesująca notka :P

  6. TeWu:
    July 16th, 2009 o 16:48

    Prawdę mówiąc, jako, że właśnie się przymierzałem do zdobycia umiejętności zaimplementowania jakiegoś algorytmu sortowania (który nie jest sortowaniem bombelkowym :P) spodziewałem się zobaczyć jakiś ciekawy algorytm sortowania, tym bardziej ostatnie zdanie mnie dobiło :D Ale dobra.. Motyka w dłoń :)

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.