Thu
12
Feb 2009

Ciekawym algorytmem jest sortowanie łańcuchów w porządku naturalnym. Chodzi o to, żeby liczby traktowane były jako liczby i sortowały się według wartości. Na przykład nazwy plików posortowane normalnie alfabetycznie (leksykonograficznie) będą w takiej kolejności:

Plik.txt
Plik1.txt
Plik10.txt
Plik2.txt
Plik24.txt
Plik3.txt

Natomiast posortowane w porządku naturalnym będą w kolejności bardziej przez użytkownika pożądanej:

Plik.txt
Plik1.txt
Plik2.txt
Plik3.txt
Plik10.txt
Plik24.txt

Oczywiście każdy informatyk wie, że należałoby raczej po prostu dopełniać te liczby zerami (np. Plik01.txt), ale mimo wszystko ten algorytm jest dobry do sortowania nazw plików, serwerów itp.

Jak to działa? Całkiem prosto. Mówiąc ogólnie, trzeba porównywać kolejne znaki dwóch łańcuchów, ale kiedy napotka się cyfry, wtedy trzeba rozpatrzyć je jako całe liczby i porównać ich wartości. Implementację w C++ można znaleźć w mojej bibliotece CommonLib (zobacz pliki Base.hpp i Base.cpp, klasa StringNaturalCompare). W PHP jest standardowo taka funkcja - nazwa się strnatcmp. Opis algorytmu w Internecie można znaleźć m.in. tu: Natural Order String Comparison.

Comments | #algorithms Share

Comments