алгоритм, который работает как Unix Сортировка

Question

, например, наш входной файл in.txt:

naturalistic 10 
coppering 20 
artless 30 

после команды: рода in.txt

artless 30 
coppering 20 
naturalistic 10 

после команды: рода -n -k 2 in.txt

naturalistic 10 
coppering 20 
artless 30 

Мой вопрос: как я могу управлять сохранением линий при сортировке по столбцу. Я хочу, чтобы вся строка оставалась такой же, пока ее порядок вообще меняется? Какой алгоритм или код полезны? Это о программе чтения или сортировки файлов?

Answer 1

Стандарт UNIX sort не документирует, какой алгоритм он использует. Он может даже выбрать другой алгоритм в зависимости от таких параметров, как размер ввода или параметры сортировки.

В списке Wikipedia page on sorting algorithms перечислены многие алгоритмы сортировки, которые вы можете выбрать.

Если вы хотите стабильную сортировку, существует множество опций (таблица сравнения в тех же списках страниц в Википедии, какие из них стабильны), но на самом деле любой алгоритм сортировки можно сделать стабильным, пометив каждый элемент данных его оригинальным положение на входе и разрыв связей в функции сравнения клавиш в соответствии с этой позицией.

Кроме этого, не совсем понятно, что вы просите. В своем вопросе вы продемонстрировать использование sort с и без -n и -k вариантов, но это не ясно, почему это должно влиять на фактический выбор алгоритма сортировки ...

Answer 2

Я бы просто создать хэш-таблицу строк с num как ключ и строка как значение (я предполагаю, что они уникальны), а затем для команды sort, я буду сортировать на основе значений и для -n -k 2 Я бы сортировал на основе ключей. Стандарт POSIX не определяет, какой алго использовать, поэтому различные вкусы unix могут использовать разные альго. Сорт GNU использует Merge Sort http://en.wikipedia.org/wiki/Merge_sort