Глава 18. Сортировка

Одно из значений слова сортировка — упорядочение списка чего-либо по возрастанию (лучше сказать — по неубыванию, если в списке содержатся равные элементы).

Сортировка — очень важная задача в информатике. Данные, представленные в виде упорядоченного списка, нагляднее. И, что ещё важнее, поиск в упорядоченных списках проще: к примеру, найти фамилию ученика в классном журнале легче, если фамилии расположены по алфавиту.

Неубывание можно понимать в разных смыслах. Список государств можно упорядочить по алфавиту, можно по количеству населения, по площади, занимаемой государством, по плотности населения (отношению населения к площади), по названиям столиц, по широтам или долготам столиц, по протяжённости морской части границы, годовому ВВП… Да мало ли величин, по неубыванию которых можно расположить страны!

Для числовых величин с неубыванием всё ясно: одно число в упорядоченном (отсортированном) списке встанет раньше другого, если первое число меньше или равно второму. Такой порядок будем называть арифметическим. Упорядочение числового списка по невозрастанию можно считать частным случаем упорядочения по неубыванию: в качестве величины, которая должна неубывать, берутся числа из списка со знаком «минус».

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

Более экзотический пример упорядочения строк можно встретить в Грамматическом словаре русского языка академика А. А. Зализняка [18]. В этом словаре для слов русского языка приводятся в виде условных обозначений морфологические описания: часть речи, схема (парадигма) изменения слов — парадигма склонения для имён, парадигма спряжения для глаголов и другие морфологические особенности слов. Интересен порядок слов в словаре Зализняка: прежде идут слова, заканчивающиеся на а, затем — на б, и так далее. При совпадающих буквах сравниваются предшествующие им. Ясно, что используется лексикографический порядок, но не самих слов, а слов, в которых буквы расположены в обратной последовательности. Такой порядок называется инверсным. Зачем такой порядок принят в словаре Зализняка? Дело в том, что в русском языке информация о грамматических свойствах слова как правило содержится в конце слова, там, где окончания и суффиксы. Поэтому слова, сходные в грамматическом смысле, обычно располагаются рядом. Например, слова, заканчивающиеся на ться, почти наверняка являются возвратными глаголами.

Так или иначе при упорядочении списков нужно уметь сравнивать пары элементов, то есть устанавливать, меньше ли первый элемент второго, больше, или элементы равны. Хотя смысл слов «больше», «меньше», «равны» может быть разным, важно, чтобы при сравнении элементов реализовывалась только одна из этих трёх возможностей. Кроме того, конечно, предполагается, что понятия «больше» и «меньше» взаимно-обратны, то есть высказывание «$a$ меньше $b$» равносильно высказыванию «$b$ больше $a$». Без этого условия порядок в списке может быть недостижим.