Dlaczego niektóre metody sortowania sortują według 1, 10, 2, 3…?

30

Zauważyłem, że wiele metod sortowania numerycznego wydaje się sortować według 1, 10, 2, 3 ... zamiast oczekiwanych 1, 2, 3, 10 ... Mam problem z wymyśleniem scenariusza, w którym potrzebuję pierwszej metody, a jako użytkownik czuję się sfrustrowany za każdym razem, gdy widzę ją w praktyce. Czy istnieją uzasadnione przypadki użycia pierwszego stylu w stosunku do drugiego? Jeśli tak, jakie one są? Jeśli nie, to w jaki sposób powstał pierwszy styl sortowania? Jakie są oficjalne nazwy dla każdej metody sortowania?

VirtuosiMedia
źródło
Nie jest to odpowiedź na twoje pytanie, ale jeśli musisz posortować listę ciągów, które mogą zawierać liczby, prawdopodobnie chcesz użyć algorytmu Alphanum: davekoelle.com/alphanum.html
TehShrike
To bardzo, bardzo proste. Podczas sortowania algorytm skanuje od lewej do prawej. Tak więc, jeśli chodzi o 1 i 5, 5 jest większe i po prostu głupio idzie z tym NAWET, jeśli 1 jest faktycznie częścią większej liczby, takiej jak 134234. Aby wiedzieć, że 134234 jest większy niż 5, musimy faktycznie przeskanować za cyfrą do ostatniej cyfry (właściwie pierwszej cyfry) 4, a następnie popracuj wstecz i zobacz, że w rzeczywistości jest to 100000, która jest znacznie większa niż 5. Tak więc twój typowy ślepy rodzaj nie robi tego, ponieważ porównuje po prostu charakter znak ignoruje to, co dzieje się po (lub przed) w porównaniu.
AbstractDissonance
1
Jeśli czytasz en.wikipedia.org/wiki/Natural_sort_order , powinno to mieć sens. W naturalnym porządku łańcuchy cyfr są pogrupowane jako pojedynczy „znak”. Nie fizycznie, tylko logicznie, abyśmy nadal mogli porównywać znaki jak w pierwszym przypadku, ale będziemy mogli porównywać ciągi liczb całkowitych z ciągami liczb całkowitych zamiast znaków ze znakami, co pozwoli nam porównać pełną wartość. Wszystkie rodzaje powinny być w ten sposób, ponieważ tak ludzie czytają rzeczy (w przypadku liczb faktycznie czytamy od prawej do lewej, nawet w ciągu od lewej do prawej 1234 = 1000 + 200 + 30 + 4, a nie 4000 + 300 + 20 + 1
AbstractDissonance

Odpowiedzi:

62

to jest sortowanie leksykograficzne, co oznacza, że ​​język traktuje zmienne jak ciągi znaków i porównuje znak po znaku ( "200"jest większy niż "19999"ponieważ '2'jest większy niż '1')

aby to naprawić, możesz

  • upewnij się, że wartości są traktowane jako liczby całkowite,

  • dodawaj '0'do ciągów, aby wszystkie miały równe długości (wykonalne tylko, gdy znasz maksymalną wartość).
    Dlatego na plikach multimedialnych (S1E01) zobaczysz numerację odcinków z poprzedzonym 0, więc sortowanie leksykograficzne nie psuje rzeczy i pozwala programom po prostu odtwarzać / wyświetlać w kolejności alfabetycznej,

  • lub utwórz niestandardowy komparator, który najpierw porównuje długość ciągów (krótsze ciągi są mniejszymi liczbami całkowitymi), a gdy są one równe, porównuje leksykograficznie (ostrożnie przed wprowadzaniem '0')

maniak zapadkowy
źródło
5
+1 dla „leksykograficznego”. Nigdy nie słyszałem tego terminu, po prostu myślałem o tym jako o sortowaniu alfabetycznym - liczby są traktowane jak ciąg znaków, jak powiedziałeś.
Anonimowy
3
+1 za poprzedzające „0” ciągi. Nie programowałem tego, było to w imieniu moich folderów, a „Rozdział 10” nadchodził przed „Rozdziałem 2”. Następnie stworzyłem rozdziały 1-9 o nazwie 01-09 i teraz są one sortowane „poprawnie”.
Marvin
6

Alfabetycznie, 1 występuje przed 2. Kiedykolwiek zobaczysz pierwszą metodę, to nie dlatego, że jest pożądana, ale dlatego, że sortowanie jest ściśle alfabetyczne (i dzieje się od lewej do prawej, jeden znak na raz): 1, 2, 10 ma sens do ciebie, ale nie do komputera, który zna tylko porównanie alfabetyczne. W takim prostym porównaniu nie ma sposobu, aby wiedzieć, że jeden po 0 faktycznie pojawia się po dwóch.

Kiedy widzisz mieszane sortowanie słów i liczb, które prawidłowo traktuje liczby, dzieje się tak dlatego, że sortowanie jest bardziej inteligentne, a ponadto zwykle działa tylko na początku lub na końcu łańcucha.

Nicole
źródło
4

Taki jest wynik, gdy sortujesz ciągi liczb alfabetycznie zamiast numerycznie.

Ten styl sortowania jest domyślnym zachowaniem sortna przykład polecenia unix , chyba że użyjesz --numeric-sortopcji wiersza poleceń, która każe mu interpretować wartości liczbowe.

Jaka jest nazwa?
źródło
4

Inni znają tego rodzaju odpowiedzi, ale nikt tak naprawdę nie odpowiedział na pytanie, dlaczego je widzisz. Odpowiedź nie jest tak ekscytująca. Zwykle jest to błąd. Większość metod sortowania będzie domyślnie ustawiona na jedną lub drugą, a programowanie prawdopodobnie nieostrożnie zmieni domyślną wartość podczas sortowania liczb.

frankc
źródło
W mieszanych kontekstach alfabetycznych / numerycznych doświadczeni użytkownicy wolą sortowanie leksograficzne, ponieważ jest spójne i przewidywalne. Każda aplikacja, która próbuje „inteligentnie” połączyć sortowanie leksograficzne i numeryczne, robi to nieco inaczej, czyniąc z tego rodzaju wątpliwą użyteczność.
j__m