Sortowanie Naturalne

Wstęp

Sortowanie Naturalne pozwala na posortowanie danych metodą, której człowiek używa podczas ręcznego układania wyrażeń w kolejności. Dzięki temu posortowane dane są bardziej czytelne. W tym artykule zostanie przedstawione jak taki algorytm działa i dlaczego dane nie zawsze są tak sortowane.

Opis Problemu

Do posortowania jest 10 nazw dokumentów. Ich nazwa składa się z przedrostka "dok", pewnej liczby określającej, który to dokument z kolei, a następnie jest dodane rozszerzenie ".txt". Posortowanie danych przy pomocy typowych algorytmów da następujący wynik:

1. dok1.txt
2. dok10.txt
3. dok100.txt
4. dok11.txt
5. dok19.txt
6. dok2.txt
7. dok20.txt
8. dok3.txt
9. dok7.txt
10. dok9.txt

Dla człowieka takie sortowanie jest mało wygodne, ponieważ wolałby, żeby dokumenty był posortowane według liczb, które zostały wpisane w nazwę dokumentu czyli dok100.txt powinien być na liście ostatni. Jednym ze sposobów na rozwiązanie tego problemu jest dodanie 0 do numeru dokumentu tak, aby wszystkie liczby porządkowe składały się z tylu samo cyfr. Przykładowo nazwa dok2.txt brzmiałaby dok002.txt. Jednak nie zawsze możliwe jest określenie z góry ile będzie dokumentów, a poza tym istnieje ryzyko, że któryś dokument nie będzie miał dodatkowych zer, albo będą źle wpisane.

Dane są sortowane w sposób przedstawiony wcześniej, ponieważ porównywane są znaki ASCII. Podczas porównywania dok100 i dok11 algorytm znajduje, że początek "dok1" jest identyczny, ale potem stwierdza, że znak 0 jest mniejszy od znak 1. Nie sprawdza on dalszych znaków tylko od razu zwraca, że dok100 < dok11. Rozwiązaniem tego problemu jest zastosowanie sortowania naturalnego.

Sortowanie Naturalne podczas porównywania dzieli tekst na fragmenty. Każdy fragment to może być liczba, albo tekst. Jednak pozwola to na dokładniejszy porównywanie tekstów, ponieważ dok100.txt zostanie przeczytany jako {"dok", 100, ".txt"}, a dok11.txt jako {"dok", 11, ".txt"}. Teraz algorytm porówna elementy listy, a nie pojedyncze znaki. Dzięki temu okaże się, że 11 < 100 i dok100.txt zostanie umieszczony po dok11.txt.

Sortując przedstawionym algorytmem otrzymana lista dokumentów będzie następująca:

1. dok1.txt
2. dok2.txt
3. dok3.txt
4. dok7.txt
5. dok9.txt
6. dok10.txt
7. dok11.txt
8. dok19.txt
9. dok20.txt
10. dok100.txt

Jak można zauważyć jest ona o wiele bardziej czytelna niż lista uzyskana podczas sortowania przy pomocy kodów ASCII!

Algorytm

Technika wybierania kolejnych para danych do posortowania jest dowolna. Sortowanie Naturalne skupia się na porównywaniu elementów. W celu podzielenia elementów na listę wartości do porównania należy określić pierwszy znak pozostałego fragmentu. Jeśli znak jest cyfrą to należy wczytać kolejne cyfry i utworzyć liczbę. Jeśli jednak to nie cyfra to należy wczytać wszystkie kolejne znaki nie będące cyframi.

Może się jednak zdarzyć przypadek, że w jednym wyrażeniu znak jest liczbą, a w drugiej nie. Wtedy dla wyrażenia, które ma cyfrę wczytujemy liczbę, a dla drugiego należy przyjąć 0. Dla przypadku, gdy porównywane są dwa teksty stosujemy porządek leksykograficzny.

Implementacja

Porównywanie

Rozwiązaniem sortowania naturalnego jest funkcja porownajNaturalnie(), która porównuje dwa łańcuhowy znakowe i zwraca, który jest "większy".

1. bool porownajNaturalnie(string a, string b) {
2.   int ai = 0, bi = 0;
3.   while (ai < a.length() && bi < b.length()) {
4.     if (isdigit(a[ai]) || isdigit(b[bi])) {
5.       int al = 0;
6.       while (ai < a.length() && isdigit(a[ai]))
7.         al = al * 10 + a[ai++] - '0';
8.       int bl = 0;
9.       while (bi < b.length() && isdigit(b[bi]))
10.         bl = bl * 10 + b[bi++] - '0';
11.       if (al != bl)
12.         return al < bl;
13.     } else {
14.       string astr = "";
15.       while (ai < a.length() && !isdigit(a[ai]))
16.         astr += a[ai++];
17.       string bstr = "";
18.       while (bi < b.length() && !isdigit(b[bi]))
19.         bstr += b[bi++];
20.       for (int i = 0; i < astr.length() && i < bstr.length(); i++)
21.         if (astr[i] != bstr[i]) return astr[i] < bstr[i];
22.       if(astr.length() != bstr.length())
23.         return astr.length() < bstr.length();
24.     }
25.   }
26.   return a.length() < b.length();
27. }

(2.) Przygotuj indeksy, aby pamiętać skąd rozpocząć wybieranie kolejnego fragmentu wyrażenia. Następnie (3.) dopóki istnieje coś do wybrania z jednego i drugiego wyrażenia to (4.) sprawdź czy ma zostać wczytana liczba. Jeśli tak to (5. - 7.) wczytaj jedną i (8. - 11.) drugą liczbę, a potem (12.) jeśli okażą się różne to (13.) zwróć wynik porównania. Analogicznie (15. - 25.) należy przeprowadzić porównywanie dla tekstów. W przypadku, gdy porównywanie odpowiednich fragmentów nie zwróciło wyników to (28.) porównaj długości wyrażeń. Dzięki temu porównywanie zawsze zakończy się jakimś wynikiem.

Testowanie funkcji

Poniższy fragment kodu wczyta od użytkownika ile wyrażeń jest do posortowania, a następnie wczyta je i wypisze posortowaną liste. Kod korzysta z wbudowanego modułu do sortowania w wybranym języku programowania.

1. int main () {
2.   int n;
3.   cout << "Ile wyrazen do porownania?" << endl;
4.   cin >> n;
5.   string temp;
6.   vector<string> data;
7.   cout << "Podaj wyrazenia:" << endl;
8.   cin.ignore();
9.   while (n-- > 0) {
10.     getline(cin, temp);
11.     data.push_back(temp);
12.   }
13.   sort(data.begin(), data.end(), porownajNaturalnie);
14.   cout << "\nPo posortowaniu:" << endl;
15.   for (int i = 0; i < data.size(); i++)
16.     cout << data[i] << endl;
17.   system("pause");
18.   return 0;
19. }

• Kod źródłowy Implementacja