Методы упорядочения

Одной из задач, при решении которых возникает необходимость обращения к внешним запоминающим устройствам, является задача упорядочения совокупности чисел по возрастанию. Эта задача может встать, например, в составляющих программах, где для упрощения дальнейшей обработки необходимо упорядочивать условные адреса; с другой стороны, в различных коммерческих (учетных) задачах часто требуется сравнивать дополнительный список, заранее не упорядоченный, с основным. Гольдштейн и фон Нейман провели первый теоретический и практический анализ двух основных методов упорядочения информации.

Они сравнили возможности решения этой задачи на вычислительной машине и на обычном табуляторе; сравнение показало некоторые преимущества первой. Дальнейшее исследование этого вопроса, как указано в диссертации Сиварда, подтвердило это положение, однако эти преимущества не настолько велики у существующих в настоящее время машин, чтобы вовсе отказаться от применения табуляторов.
Существует два основных метода упорядочения информации:
а) объединение, при котором берутся две (или более) возрастающие (или убывающие) упорядоченные последовательности числовой информации и эти последовательности объединяются в одну упорядоченную возрастающую (или убывающую) последовательность;
б) сортировка, при которой берется неупорядоченная последовательность (чисел) и производится реорганизация этой последовательности в порядке возрастания (убывания).
Поскольку информация, представленная в буквенной форме, кодируется в машине чаще всего с помощью чисел, упорядоченных в том же порядке, что и алфавит, то все это относится также к объединению и сортировке информации, представленной в буквенной или иной нецифровой форме. Результирующая объединенная последовательность записывается в ячейки.

Источник: delete-it