Dlaczego sort zmienia kolejność wierszy z identycznymi kluczami sortowania?

31

Oto dane:

D 2
B 2
A 2

Po uruchomieniu tego polecenia:

sort -k2,2 file

generuje:

A 2
B 2
D 2

Moje pytanie brzmi: kiedy określam tylko drugą kolumnę -k2,2, dlaczego sortuje ona również według pierwszej kolumny? Ponieważ wszystkie wartości drugiej kolumny są takie same, należy ją pozostawić bez zmian.

dwwdw
źródło
7
[Semi-OT]: FYI, sortowanie zachowujące kolejność wprowadzania, gdy klucze sortowania pasują do siebie, znane w informatyce jako sortowanie stabilne . Często sortowania nie są stabilne, ponieważ wiele niestabilnych algorytmów sortowania jest szybszych lub prostszych. Nie w tym przypadku, ale znajomość terminu CS sprawia, że ​​dokumentacja strony podręcznika dla -sopcji jest zrozumiała i możliwa do znalezienia.
derobert

Odpowiedzi:

34

To porównanie w ostateczności . Porównując dwie linie, jeśli wszystkie klucze są równe, w ostateczności wykonuje się podstawowe porównanie ciągów wszystkich linii ( -rnadal obowiązuje, ale nie inne opcje). Takie zachowanie jest określone przez POSIX :

Z wyjątkiem sytuacji, gdy podano opcję -u, wiersze, które w innym przypadku są równe, są uporządkowane tak, jakby żadna z opcji -d, -f, -i, -n lub -k nie była obecna (ale z -r nadal obowiązuje, zostało określone) i ze wszystkimi bajtami w wierszach istotnych dla porównania. Kolejność zapisywania wierszy, które nadal są równe, jest nieokreślona.

W GNU sortto porównanie w ostateczności można wyłączyć za pomocą opcji -s(dla stabilnej ).

Stéphane Chazelas
źródło